Assignment Two: Variables and Constraints
Due: 12:30pm, Wednesday 4 October 2006

In the first three questions you will look at backtracking, arc consistency, and hill climbing for solving the same CSP problem. These problems will be easier if you use the CIspace applets at
http://www.cs.ubc.ca/labs/lci/CIspace/

# 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

Show how arc consistency can be used to solve this problem. To do this you need to
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

Show how hill climbing can be used for the problem of question 1. (You can use the CIspace hill climbing applet for this).
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

In the SLS applet, it is difficult to compare simulated annealing with the other algorithms. Explain why. What would you recommend to do to make the comparison fair?