The goal of this assignment is to give you practice in using different methods to represent and solve CSPs.
On page 231 of your text, Exercise 6.7, is a classic logic problem, reproduced below:
Consider the following logic puzzle: In five houses, each with a different color, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and a different pet.
Given the following facts, the questions to answer are "Where does the zebra live, and in which house do they drink water?"
The Englishman lives in the red house.
The Spaniard owns the dog.
The Norwegian lives in the first house on the left.
The green house is immediately to the right of the ivory house.
The man who eats Hershey bars lives in the house next to the man with the fox.
Kit Kats are eaten in the yellow house.
The Norwegian lives next to the blue house.
The Smarties eater owns snails.
The Snickers eater drinks orange juice.
The Ukrainian drinks tea.
The Japanese eats Milky Ways.
Kit Kats are eaten in a house next to the house where the horse is kept.
Coffee is drunk in the green house.
Milk is drunk in the middle house.
Please note, the objective here is not to solve the logic problem, but to investigate how well different approaches work.
Also, there is not one "right" solution (to the assignment - there is one right solution to the logic problem).
Your work will be graded based on whether you implemented the concepts in the book correctly, not in the representation that you choose to use.
In fact, for discussion in class, it will be more fun if everyone has a different approach.
Part 1: Arc Consistency
On page 209 of your book is an algorithm called AC-3, which checks arcs in a binary constraint graph for consistency.
You are to walk through this algorithm (by hand) to solve the above logic problem.
1) Start by defining the problem.
What are the variables you will use?
What are their domains?
What are the constraints?
Record these in the notation used in the book.
2) Draw the constraint graph based on your formulation of the problem above.
You may find (that's a hint - you are doing it right if you run into problems) that the constraint graph is actually a hypergraph, in which not all constraints are binary.
You need not represent the AllDiff constraints, but keep them in mind as you walk through the next step.
As we saw in the map coloring video in class, you may want to put a shorthand notation of each variable's domain values within the node.
3) Use the AC-3 algorithm to propagate constraints through the graph until the graph is consistent - that is, the values in the domains of each variable are consistent.
As you eliminate domain values based on constraints, cross them off on the graph.
4) Answer the following:
Were you able to completely solve the problem using arc consistency?
If not, have you reduced the state space to something that would be more easily searchable by traditional search methods?
How well do you think arc consistency works for this problem?
Part 2: Min Conflicts
Recall that min conflicts is a local search method.
Rather than propagating constraints through the graph, this time you will start with a fully assigned, though conflicted, solution.
1) Redefine the problem.
This time, the variables are the houses, 1 through 5.
"Randomly" assign a nationality, a color, a pet, a candy and a drink to each house.
(My random assignment was to simply assign things to houses in the order that they occurred in the problem.
A more interesting result across the class would be if you all used a different "random" assignment.)
2) Evaluate your assignment of variables.
Count the number of constraints that are violated in your "random" assignment.
I found it helpful to create a table with constraints listed down the side and iterations listed across the top.
On the first count I placed an x in column 0 for each constraint that was violated and put the total below.
3) Walk through each violated constraint in your list and "fix" it by swapping the values of one of the variables creating the constraint.
If you violate a previously resolved constraint by doing the swapping, you can propagate backwards (that is, swap values backwards) to fix the violation.
Iterate through this process until you have resolved as many constraints as possible.
4) Answer the following:
Were you able to completely solve the problem using min conflicts?
If so, how many iterations did it take?
If not, did you reach a point where the same amount of constraints were violated on each iteration no matter what you did?
Or did you keep bouncing back and forth between a set of violated constraints?
Conceptually, what does this behavior mean?
Submission.
Submit your work, both problems and all parts, via Moodle.
