Question 1

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

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. How many leaves are in the search tree generated?

   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: this may be large! It may be easier to write a program to generate it (but then again, it may not be easier; try it by hand first).
2. Is there a different variable ordering that results in a smaller tree? Give a variable ordering that results in the smallest tree. How many leaves are on this tree? Explain why you think this is the optimal ordering. (A good explanation is more important than actually finding the optimal ordering).
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. Assume we split the alphabetically first variable that has more than one element in its domain for any arc-consistent network. Include all arc consistency steps.