/*
By Neng-Fa Zhou
The ternary Steiner problem of order n is to find n(n-1)/6 sets of elements in {1,2,...,n} such that
each set contains three elements and any two sets have at most one element in common. For example,
the following shows a solution for size n=7:
{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}
Problem taken from:
C. Gervet: Interval Propagation to Reason about Sets: Definition and Implementation of a Practical
Language, Constraints, An International Journal, vol.1, pp.191-246, 1997.
*/
:-write('you need clpset.pl (www.probp.com/libraryplus/clpset.pl) to run this program.'),nl.
main:-
cputime(Start),
top,
cputime(End),
(retract(backtracks(B))->true;B=0),
T is End-Start,
write('cputime='),write(T),nl,
write('backtracks='),write(B),nl.
top:-
steiner(9).
top.
steiner(N):-
NoSets is N*(N-1)//6,
createSetDomains(NoSets,N,Lsets),
intersect_atmost_1(Lsets),
clpset_labeling(Lsets),
clpset_write(Lsets),nl.
createSetDomains(N,Max,Lsets):-
N=:=0,!,Lsets=[].
createSetDomains(N,Max,Lsets):-
Lsets = [X|Lsets1],
clpset_domain(X,1,Max),
clpset_card(X,3),
N1 is N-1,
createSetDomains(N1,Max,Lsets1).
intersect_atmost_1([]).
intersect_atmost_1([X|Xs]):-
intersect_atmost_1(X,Xs),
intersect_atmost_1(Xs).
intersect_atmost_1(X,[]).
intersect_atmost_1(X,[Y|Ys]):-
intersect_atmost_1_var_var(X,Y),
intersect_atmost_1(X,Ys).
intersect_atmost_1_var_var(X,Y):-
clpset_intersection(X,Y,XY),
clpset_card(XY,Card),
Card #=< 1,