7 Solving a CSP via backtracking, arc consistency, hillclimbing

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 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 is to write a program to generate the tree (using whatever programming language you like).
2. Is there a different variable ordering that results in a smaller tree? Give the variable ordering that results in the smallest tree (or a small tree). Explain how you determined this was the optimal ordering. (E.g., what was the search strategy through the space of orderings that you used to solve this. A good explanation as to why your ordering is good is more important than the right answer.)
3. Show how arc consistency can be used to solve this problem. To do this you need to
   1. Draw the constraint graph,
   2. 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. Include all arc consistency steps.
4. Show how hill climbing can be used for the problem. Suppose a neighbor is obtained by increasing or decreasing the value of one of the variables by 1, the heuristic function to be maximized is the number of satisfied constraints, and you always choose a neighbor with the maximal heuristic value.
   1. Show what happens when we start with the assignment A=1, B=1, C=1, D=1, E=1.
   2. Show what happens when we start with A=3, B=3, C=2, D=1, E=4.
   3. Can you think of a better heuristic function? Explain why or why not.