I ran across BitTorrent’s developer challenge, which poses the following problem:
You have 40 bowls, all placed in a line at exact intervals of 1 meter. You also have 9 oranges. You wish to place all the oranges in the bowls, no more than one orange in each bowl, so that there are no three oranges A, B, and C such that the distance between A and B is equal to the distance between B and C. How many ways can you arrange the oranges in the bowls?
This is the kind of problem where Prolog’s constraint solver shines. You just generate a list of 9 variables and establish a bunch of constraints. The first constraint is that the variables should be in ascending order, e.g. [1,2,4,5,10,11,13,14,28]. This will remove all duplicate solutions. The second constraint is, as the problem states, that for all combinations of 3 bowls A, B and C, the distance between A & B is not equal to B & C.
The problem I ran into is that the Prolog runtime crashed when I asked for all the solutions because there are many millions of them. So I had to use a global variable to keep count of all the solution, without saving any of the solutions. The Prolog standard library doesn’t appear to have a predicate that does that. Anyway, here’s the code for GNU Prolog. I also tweaked this code to run in B-Prolog, which ran 4 times faster (37 sec vs 155 sec).
go :- g_assign(counter,0), oranges(40,9,L), g_inc(counter), fail. oranges(B,O,L) :- length(L,O), fd_domain(L,1,B), fd_all_different(L), ascending(L), constrain(L), fd_labeling(L). ascending(). ascending([_]). ascending([X,Y|Xs]) :- X #< Y, ascending([Y|Xs]) . constrain(L) :- bagof(P, P^combination(3,L,P), Ps), not_equal(Ps). not_equal(). not_equal([P|Ps]) :- [A,B,C] = P, B-A #\= C-B, not_equal(Ps). combination(0,_,). combination(N,[X|T],[X|Comb]) :- N>0, N1 is N - 1, combination(N1,T,Comb). combination(N,[_|T],Comb) :- N>0, combination(N,T,Comb).