/*
THE SOCIAL GOLFER PROBLEM

The coordinator of a local golf club has come to you with the following problem. In her club, there are 32 social golfers, each of whom play golf once a week, and always in groups of 4. She would like you to come up with a schedule of play for these golfers, to last as many weeks as possible, such that no golfer plays in the same group as any other golfer on more than one occasion.

Possible variants of the above problem include: finding a 10-week schedule with ``maximum socialisation''; that is, as few repeated pairs as possible (this has the same solutions as the original problem if it is possible to have no repeated pairs), and finding a schedule of minimum length such that each golfer plays with every other golfer at least once (``full socialisation'').

The problem can easily be generalized to that of scheduling m groups of n golfers over p weeks, such that no golfer plays in the same group as any other golfer twice (i.e. maximum socialisation is achieved). 

*/

/*
Implementation: George Rabanca

Solution for 6 weeks using a [Week, Golfer] -> Group matrix association.
For each week, a golfer is assigned a group number.  The solution weakness consist of the great number of symmetries inherent to the model.  Since groups do not really have numbers, exchanging the group number between any 2 groups in any week gives another symmetric solution.  Simmilarly, all permutations of the order of the weeks results in symmetric solutions.  Finally, golfer's numbers may be permutted to result in numerous other symmetric solutions.

This model does not seem to extend well for 7 weeks.  Trying to break the week symmetry is slowing down the solution.
*/

go:-
    statistics(runtime,[Start|_]),
    top,
    statistics(runtime,[End|_]),
    T is End-Start,
    write('execution time is '),write(T), write(milliseconds),nl.

top:-
    golfers(X).
top.

golfers(Schedule):-
	%schedule is an array holding the group index for each player each week. 
	Schedule =[W1, W2, W3, W4, W5, W6],

	initialize(W1),
	initialize(W2),
	initialize(W3),
	initialize(W4),
	initialize(W5),
	initialize(W6),	

	%make sure that each 2 players play at most once
	make_diff(W1, W2, W3, W4, W5, W6),

	%labeling the weeks one by one leads to a faster solution...
	labeling(W1),
	labelingff(W2),
	labelingff(W3),
	labelingff(W4),
	labelingff(W5),
	labelingff(W6).

%make initial constraints for each week
initialize(Week):-
	Week = [1,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_], 
	Week in [1..8],

	%make sure that each group has exactly 4 players.
	exactly(4, Week, 1),
	exactly(4, Week, 2),
	exactly(4, Week, 3),
	exactly(4, Week, 4),
	exactly(4, Week, 5),
	exactly(4, Week, 6),
	exactly(4, Week, 7),
	exactly(4, Week, 8),

	%to break group symmetry we make sure that the lower group has smaller player
	check_groups(Week).


%checks grups are ordered right in the Nth week
%breaks group symmetry
check_groups(Week):-
	first_index_of(Week, 2, I2),
	first_index_of(Week, 3, I3),
	first_index_of(Week, 4, I4),
	first_index_of(Week, 5, I5),
	first_index_of(Week, 6, I6),
	first_index_of(Week, 7, I7),
	first_index_of(Week, 8, I8),

	I1 #= min([I1, I2, I3, I4, I5, I6, I7, I8]),
	I2 #= min([I2, I3, I4, I5, I6, I7, I8]),
	I3 #= min([I3, I4, I5, I6, I7, I8]),
	I4 #= min([I4, I5, I6, I7, I8]),
	I5 #= min([I5, I6, I7, I8]),
	I6 #= min([I6, I7, I8]),
	I7 #= min([I7, I8]).

%I is the first index of L where N appears.  If N not found return 0.	
first_index_of(List, N, I):-
	first_index_of(List, N, I, 1).
first_index_of([X|List], N, I, Acc):-
	(N #= X, I = Acc; 
	N ## X, 
	Acc1 is Acc + 1, 
	first_index_of(List, N, I, Acc1)).	
	
%Makes the constraints ensuring that any 2 players do not play more than one game
make_diff([], [], [], [], [], []).
make_diff([X1|W1], [X2|W2], [X3|W3], [X4|W4], [X5|W5], [X6|W6]):-
	%the Acc1 will have contents of Acc plus the comp list of this player with all other (greater) players
	make_diff_this_player(X1,X2,X3,X4,X5,X6, W1, W2, W3, W4, W5, W6), 
	make_diff(W1, W2, W3, W4, W5, W6).


%for a given player's group assignment (X1, X2, ...) make all constraints that ensure this player won't play more than 
%one game with any other (greater) player.
make_diff_this_player(_, _,_, _,_,_, [], [], [], [], [], []).
make_diff_this_player(X1, X2, X3, X4, X5,X6, [Y1|W1], [Y2|W2], [Y3|W3], [Y4|W4], [Y5|W5],[Y6|W6]):-
	D = [D1, D2, D3, D4, D5, D6],
	D1 #= X1 - Y1, 
	D2 #= X2 - Y2, 
	D3 #= X3 - Y3, 
	D4 #= X4 - Y4, 
	D5 #= X5 - Y5, 	
	D6 #= X6 - Y6,

	atmost(1, D, 0), 
       	make_diff_this_player(X1, X2, X3, X4, X5, X6, W1, W2, W3, W4, W5, W6).