Assignment 2 Solution

(2.5 points) Nim is a kind of game in which players take turn to removing objects from some initial configuration. A particular version of the Nim is: there is a pile of 13 coins on the table, on each turn, players take either 1, 2, or 3 coins from the pile and put them aside. The objective of the game is to avoid being forced to take the last coin. Using the framework provided in connex, and seeing the TicTacToe game as an example, implement the Nim game.












(2 points) Formulate as CSP the following scheduling problem. You are given n courses (E.g. CSC110, CSC115, …, CSC421,…), which are needed for one to graduate, and are asked to create a schedule for taking the courses, subject to the following constraints:



Courses might have prerequisite courses that need to be taken before.
Some courses are offered in certain terms only.



We want to take not more than 4 courses per term.
Time conflicts should be avoided.



Only the formulation is required for this question (no program required).




Hint. For example, we might pick the terms as the variables. In that case, the values are combinations of four courses that are consistent, meaning that they are offered in the same term and whose times don't conflict. The prerequisite constraint would relate every pair of terms and would require that no course appear in a term before that of any of its prerequisite course. This perfectly valid formulation has the practical weakness that the domains for the variables are huge, which has a dramatic effect on the running time of the algorithms. One way of avoiding the combinatorics of using 4-course schedules as the values of the variables is to break up each term into "term slots." Then, we can turn things around and use the courses themselves as variables and use (term-termslot-timeslot) triples as the values. Now write a sample of the domains and formalize the constraints.




(3 points) Consider the following puzzle: In five houses, each with a different color, live 5 persons of different nationalities, each of whom prefer a different brand of cigarette, a different drink, and a different pet. Given the following facts, the question to answer is “Where does the zebra live, and in which house do they drink water?”



1.The Englishman lives in the red house.

2.The Spaniard owns a dog.

3.Coffee is drunk in the green house.




4.The Ukrainian drinks tea.

5.The green house is directly to the right of the ivory house.

6.The Old-Gold smoker owns snails.

7.Kools are being smoked in the yellow house.

8.Milk is drunk in the middle house.

9.The Norwegian lives in the first house on the left.




10.The Chesterfield smoker lives next to the fox owner.

11.Kools are smoked in the house next to the house where the horse is kept.

12.The Lucky-Strike smoker drinks orange juice.

13.The Japanese smokes Parliament.

14.The Norwegian lives next to the blue house.




Formulate the problem as CSP, code it, and find the solution. (partial code provided)




Hint. Use the last formulation discussed in class and slides. Do not forget the uniqueness constraints, e.g. red should be different from green, blue, etc, milk should be different from coffee, tea, etc, and so on, for each group of variables. Use loops wherever possible to avoid specifying everything by hand.