Constraint Programming example

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).
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s