Question One

Consider a scheduling problem, where there are six variables A, B, C, D, E and F, each with domain {1,2,3,4}. Suppose the constraints are: A<B, |A-C|=1, B-C is even, B != D, D>A, D != C, E != C, E<D-1, E != B-2, A != F, B != F, C != F, D != F, |E-F| is odd.

A CIspace representation for this graph is at:
http://www.cs.ubc.ca/spider/poole/cs502/2006/cspexample.xml

1. Show how backtracking can be used to solve this problem, using the variable ordering A,B,C,D,E. To do this you should draw the search tree generated to find all answers. Indicate clearly the satisfying assignments.

   To indicate the search tree, write it in text form with each branch on one line. For example, suppose we had variables X, Y and Z with domains t, f, and constraints X != Y, Y != Z. The corresponding search, with the order X, Y, Z, tree can be written as:

   X=t Y=t failure
       Y=f Z=t solution
           Z=f failure
   X=f Y=t Z=t failure
           Z=f solution
       Y=f failure
   

   Hint: the easiest way to solve this problem may be to write a program to generate the tree (using whatever programming language you like).

2. Is there a smaller tree? Give a node selection heuristic that results in as small a tree as you can find. Show the tree, and say how many leaves there are. Explain why you expect the tree resulting from this heuristic to be good. (A good explanation as to why your ordering is expected to be good is more important than the right answer.)

Question Two

1. Draw the constraint graph,
2. For the first 5 instances of arc consistency, show which elements of a domain are deleted at each step, and which arc is responsible for removing the element.
3. Show explicitly the constraint graph after arc consistency has stopped.
4. Show how splitting domains can be used to solve this problem. Draw the tree of splits and show the solutions.
5. Based on this experience, discuss how much arc consistency saves over the backtracking for this problem (even for the best tree that you found).

Question Three

1. For one particular run, where you select any variable that is involved in an unsatisfied constraint, and select a value that results in the minimum number of unsatisfied arcs, explain which element is changed at each step and what was the resulting number of unsatisfied arcs (You only need to do this for 5 steps).
2. Compare and explain the result of the following settings:
   1. select a variable with the maximum number of unsatisfied constraints, and the best value
   2. select any variable which is involved in unsatisfied constraints, and the best value
   3. select a variable at random, and the best value.
3. How important is to choose the value that results in the fewest unsatisfied arcs as opposed to choosing a value at random? Explain.
4. Based on this experience suggest what good settings for the parameters are. Explain your choice.

Question Four