Prolog combinatorial exercise

Question

I want to write a Prolog program for the following problem: From a set X = {1 ... 24} determine 8 numbers y1..y8 , such that for every n, 0 < n < 24 there are two numbers yi and yj with n = yi - yj, yi > yj.

Up to now I tried the following:

gen(A, B, C, D, E, F, G, H) :-
   permutation([A, B, C, D, E, F, G, H, _, _, _,     
_, _, _, _, _, _, _, _, _, _, _, _, _],
      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]). 

distance(D, L) :-
   random_member(X, L),
   random_member(Y, L),
   X - Y =:= D.

solution(A, B, C, D, E, F, G, H) :-
   gen(A, B, C, D, E, F, G, H),
   distance(1, [A, B, C, D, E, F, G, H]),
   distance(2, [A, B, C, D, E, F, G, H]),
   distance(3, [A, B, C, D, E, F, G, H]),
   distance(4, [A, B, C, D, E, F, G, H]),
   distance(5, [A, B, C, D, E, F, G, H]),
   distance(6, [A, B, C, D, E, F, G, H]),
   distance(7, [A, B, C, D, E, F, G, H]),
   distance(8, [A, B, C, D, E, F, G, H]),
   distance(9, [A, B, C, D, E, F, G, H]),
   distance(10, [A, B, C, D, E, F, G, H]),
   distance(11, [A, B, C, D, E, F, G, H]),
   distance(12, [A, B, C, D, E, F, G, H]),
   distance(13, [A, B, C, D, E, F, G, H]),
   distance(14, [A, B, C, D, E, F, G, H]),
   distance(15, [A, B, C, D, E, F, G, H]),
   distance(16, [A, B, C, D, E, F, G, H]),
   distance(17, [A, B, C, D, E, F, G, H]),
   distance(18, [A, B, C, D, E, F, G, H]),
   distance(19, [A, B, C, D, E, F, G, H]),
   distance(20, [A, B, C, D, E, F, G, H]),
   distance(21, [A, B, C, D, E, F, G, H]),
   distance(22, [A, B, C, D, E, F, G, H]),
   distance(23, [A, B, C, D, E, F, G, H]),
   distance(24, [A, B, C, D, E, F, G, H]).

Can someone help me with that?

Have you considered using the CLPFD ("constraint logic programming over finite domains") library? — lurker
Provided that I have only numbers from 1 to 24 available, how can I satisfy the required condition for n=24? — dlask

fferri fferri · Accepted Answer · 2015-07-04T22:18:12

I changed your gen/1 predicate, because the way you wrote it would generate lot of backtracking with repeated solutions. In this other way, it will backtrack sooner, and be more efficient.

I also used a list to represent your solution (to write less variable names).

Finally, I used forall/2 instead of writing 22 times (almost) the same thing.

gen([X|Xs],Min,Max,Length) :-
    Length>0,
    between(Min,Max,X),
    Min1 is X+1,
    Length1 is Length-1,
    gen(Xs,Min1,Max,Length1).
gen([],_,_,0).

gen(X) :- gen(X,1,24,8).

distance(D,L) :-
    member(Y1,L),
    member(Y2,L),
    D =:= Y1 - Y2,
    Y1 > Y2.

solution(X) :-
    gen(X),
    forall(between(2,23,D), once(distance(D,X))).

Result: (hower with mouse to see it)

There are 4 solutions (I considered the correction in your comment, so that 1 < N < 24)
?- solution(X).
X = [1, 2, 3, 12, 16, 19, 22, 24] ;
X = [1, 2, 5, 11, 17, 19, 22, 24] ;
X = [1, 3, 6, 8, 14, 20, 23, 24] ;
X = [1, 3, 6, 9, 13, 22, 23, 24] ;
false.

Prolog combinatorial exercise

1 Answers