% Social Golfer problem
% http://4c.ucc.ie/~tw/csplib//prob/prob010/index.html
% Copyright (C) 2003 INRIA Sylvain Soliman

% file socgolf01.pl
% January 23 2003:

golf(G,S,W,R) :-     % G groups of S golfers play for W weeks
	M is G*S,
	length(R,W),      % R, the result, is a list of weeks, each being a list...
	init_weeks(M,G,S,R,Vars), % ... of group numbers attributed to each player
	not_twice_rec(R),
	randomize,
	fd_labeling(Vars,[value_method(random)]).
   
instantiate_week1([],0,_).
instantiate_week1(W,G,S) :-
	G>0,
	GG is G-1,
	length(L,S),
	fd_domain(L,G,G),
	instantiate_week1(LL,GG,S),
	append(LL,L,W).
	
% Initialization
init_weeks(_,_,_,[],[]).
init_weeks(M,G,S,[GL|WL],V) :-
	length(GL,M),           % M players in the list
	fd_domain(GL,1,G),      % each player gets a group number
	fd_exactly_rec(GL,G,S), % exactly S golfers in each group
	init_weeks(M,G,S,WL,V1),
	append(GL,V1,V).

fd_exactly_rec(_,0,_).
fd_exactly_rec(L,G,S) :-
   G > 0,
   GG is G-1,
   fd_exactly(S,L,G),      % exactly S golfers in group G
   fd_exactly_rec(L,GG,S).

not_twice_rec([]).
not_twice_rec([W|WL]) :-
   not_twice(W,WL),
   not_twice_rec(WL).

not_twice(_,[]).
not_twice(W,[H|T]) :-
   no_common_rec(W,H),
   not_twice(W,T).

no_common_rec([],[]).
no_common_rec([H1|T1],[H2|T2]) :-
   no_common(H1,T1,H2,T2),
   no_common_rec(T1,T2).

no_common(_,[],_,[]).
no_common(G1,[H1|T1],G2,[H2|T2]) :-
   (H1 #= G1) #==> (G2 #\= H2),
   (H2 #= G2) #==> (G1 #\= H1),
   no_common(G1,T1,G2,T2).