$2$ Game Puzzle $[30$ marks$]$ PROLOG

There was a tournament of $5$ teams, where each team played with every other team exactly

once. In total, the tournament had $10$ matches. In each match, two teams played against

each other. The teams are from Oakville, Pickering, Richmond Hill, Scarborough, and Toronto

$($downtown$).$ The games are scheduled over $5$ rounds. In each round, one of the teams did not

participate, while the other four teams played two matches once. The outcome for each match

is either a draw d for both teams, or a win w for one team and a loss l for another team.

Your task is to write a Prolog program that nds the outcome of each match for each

team, based on the clues provided below. You have to write a Prolog program that implements

precisely not only the given constraints, but also constraints that remain implicit. Never try

to guess part of solution by yourself: all reasoning should be done by your program. You have

to demonstrate whether you learned well a program design technique. Your implementation

should follow exactly one of the design patterns explained in class. You will lose marks, if the

TA sees that you embedded your own reasoning into your program. Points per match must

satisfy all of the following constraints.

$1.$ Pickering lost to Scarborough in the rst round, but won over Oakville in the second

round.

$2.$ Toronto did not play in the third round; they had one win and one loss in the previous

two rounds.

$3.$ Oakville did not participate in the fourth round, but they already won twice in the pre$-$

ceding three matches.

$4.$ All matches in the fourth and in the fth round nished with a draw.

$5.$ Before the fourth round, Richmond Hill won only once and lost once.

$6.$ None of the matches in the rst$,$ in the second and in the third rounds nished with a

draw.

a$.[25$ marks$]$ Write a Prolog program q$2\_$game.pl that solves this problem using in$-$

terleaving of generate and test technique considered in class. In your programs, the variables

should range over the following nite domain of characters: n $($a team did not participate in a

round$),$ l $($loss$),$ d $($draw$),$ w $($win$).$

You will need to be careful in your program regarding the order of constraints. Also, provide

comments where in your program which constraint is implemented. Explain brie

y the ordering

you have chosen $($write comments in you program le$).$ You should implement both a solve and

solve and print as described in question $1.$ Make sure that solve and print has no arguments

and prints the answers returned by your program in an easy to read format: you will lose marks

if output is obscure. Arrange your output similar to the predicate print solution$($List$)$ discussed

in class. The TA should be able to call both your predicate solve$($List$)$ and your predicate

solve and print to see the solution.

Before, you write a program that solves this CSP$,$ implement the $2-$argument predicate

fourExactly$($X$,$List$)$ and use it in your program. Speci cally, this predicate can be useful when

you implement the $4$th constraint: the list of points awarded to the teams has exactly $4$ oc$-$

currences of $\backslash$d$".$ This predicate is true, if X occurs exactly four times in the given List.

In your implementation, do not make assumptions about the number or kind of elements in

List. This is because we will test your predicate independently of your solution. For example,

$3$

fourExactly$($q$,[$q$,$a$,$b$,$q$,$q$,$b$,$q$,$a$,$c$,$b$,$c$]$ should succeed. You might wish to introduce ad$-$

ditional helping predicates to implement constraints. In any case, you have to implement all

your helping predicates yourself. You cannot use any of the library predicates, unless they were

discussed in class.

b$.[5$ marks$]$ We should be able to query your program using both solve$($List$)$ and

solve and print $($no arguments$).$ Make sure it is obvious from your output what the solution is$.$

Find also how much time your program takes to compute an answer using the process described

in the previous Part $1$ of this assignment. Your Prolog session should be included in the le

q$2\_$game$\_$session.txt

Thus, your submission should include both q$2\_$game.pl and q$2\_$game$\_$session.txt