Logic Programming
What
versus
How
 

Tournament


Problem

This assignment concerns the scheduling of matches in a bridge tournament. Each match in the tournament features four players - one pair of players pitted against a second pair of players. A round consists of n matches - one on each of n available tables. A schedule is a list of rounds in which (1) each player pairs with each other player at least once, (2) no player is scheduled twice in the same round, (3) every table is busy on every round (i.e. there are n simultaneous matches). A schedule is minimal if and only if there is no other schedule with fewer rounds. Your mission is to write a logic program that that produces a minimal schedule for eight players on two tables. Hint: You will probably need to increase the unification limit for queries to 2000000 or more to get an answer.

Extra credit for writing a logic program that produces a good schedule for any number of players greater than eight. Even more extra credit for producing a logic program in which the number of tables can be varied as well (subject to the constraint that there are more than 4n players, where n is the number of tables). The general case would also make a good final project.

Solution

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% tournament %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% schedule(R1,R2,R3,R4,R5,R6,R7) :- isround(R1) & isround(R2) & diff(R2,R1) & isround(R3) & diff(R3,R1) & diff(R3,R2) & isround(R4) & diff(R4,R1) & diff(R4,R2) & diff(R4,R3) & isround(R5) & diff(R5,R1) & diff(R5,R2) & diff(R5,R3) & diff(R5,R4) & isround(R6) & diff(R6,R1) & diff(R6,R2) & diff(R6,R3) & diff(R6,R4) & diff(R6,R5) & isround(R7) & diff(R7,R1) & diff(R7,R2) & diff(R7,R3) & diff(R7,R4) & diff(R7,R5) & diff(R7,R6) isround(round(M1,M2)) :- ismatch(M1) & ismatch(M2) & dismatch(M1,M2) ismatch(match(P,Q)) :- ispair(P) & ispair(Q) & dispair(P,Q) diff(round(match(P1,P2),match(P3,P4)),round(match(P5,P6),match(P7,P8))) :- mutex(P1,P2,P3,P4,P5,P6,P7,P8) ispair(pair(X,Y)) :- player(X) & player(Y) & distinct(X,Y) & evaluate(min(X,Y),X) dismatch(match(pair(X1,X2),pair(X3,X4)),match(pair(X5,X6),pair(X7,X8))) :- mutex(X1,X2,X3,X4,X5,X6,X7,X8) dispair(pair(U,V),pair(X,Y)) :- distinct(U,X) & distinct(U,Y) & distinct(V,X) & distinct(V,Y) player(1) player(2) player(3) player(4) player(5) player(6) player(7) player(8) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Query schedule(R1,R2,R3,R4,R5,R6,R7) %%% Result after ~ 2 seconds %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% schedule(round(match(pair(1,2),pair(3,4)),match(pair(5,6),pair(7,8))), round(match(pair(1,3),pair(2,4)),match(pair(5,7),pair(6,8))), round(match(pair(1,4),pair(2,3)),match(pair(5,8),pair(6,7))), round(match(pair(1,5),pair(2,6)),match(pair(3,7),pair(4,8))), round(match(pair(1,6),pair(2,5)),match(pair(3,8),pair(4,7))), round(match(pair(1,7),pair(2,8)),match(pair(3,5),pair(4,6))), round(match(pair(1,8),pair(2,7)),match(pair(3,6),pair(4,5)))) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%