steiner1.pl

PRl教学程序 PRl教学程序 PRl教学程序

/*
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,