Combinatorial Prolog Exercises
I want to write a Prolog program for the following problem: From the set X = {1 ... 24} define 8 numbers y1..y8 such that for each n, 0 <n <24 there are two numbers yi and yj with n = yi - yj, yi> yj.
So far I have 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 anyone help me?
source to share
I changed the predicate gen/1
because the way you wrote it will result in multiple returns with repeated solutions. In other words, it will come back faster and be more efficient.
I also used a list to represent your solution (to write fewer 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: (hover your mouse to see it)
There are 4 solutions (I reviewed the fix in your comment, so what
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.
source to share