Artificial Intelligence Assignment 2

CS C 421 Artificial Intelligence
Assignment 2

(e-submission only: submit code (zip file), results, and a scan/photo of solution to Q2)
1. (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. (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:
A. Courses might have prerequisite courses that need to be taken before.
B. Some courses are offered in certain terms only.
C. We want to take not more than 4 courses per term.
D. 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-termslottimeslot) triples as the values. Now write a sample of the domains and formalize the
constraints.
3. (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.