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

solveCount.py code

# Search for finding a solution to CSP X !=Y and Y != Z dom = ["t","f"]

fails = 0 expanded = 1 # for root node

print(" Solutions: X Y Z") for X in dom: expanded += 1 for Y in dom: expanded += 1 if X != Y: for Z in dom: expanded += 1 if Y != Z: print(X,Y,Z) else: fails +=1 else: fails += 1 print("Search: number of failures:",fails) print("Number of nodes expanded:",expanded)

# Or using generate and test:

dom = ["t","f"] gtfails = 0 gtexpanded = 1 for X in dom: gtexpanded += 1 for Y in dom: gtexpanded += 1 for Z in dom: gtexpanded += 1 if X !=Y and Y != Z: print(X,Y,Z) else: gtfails +=1

print("Generate and test: number of failures:",gtfails) print("Generate and test: number nodes expanded:",gtexpanded)

# Without statistics for X in dom: for Y in dom: for Z in dom: if X !=Y and Y != Z: print(X,Y,Z)

(a) Show how search can be used to solve this problem, using the variable ordering A, B, C, D, E, F, G, H. To do this, write a program to print out all answers and count the number of nodes expanded and the number failing consistency checks. You can use whatever programming language you like. We don't want a general program; just one for this example. Sample Python code that produces the answer for variables X, Y and Z each with domains {t, f}, and constraints X 6= Y , Y 6= Z is at solveCount.py

(b) Is there a smaller tree? Give a node ordering that results in as small a tree as you can nd. Show both how many failing consistency checks there are, and how many nodes are expanded. Explain how you found this ordering and why you would expect the tree resulting from this ordering to be good. (A good explanation as to why your ordering is expected to be good is more important than the perfect ordering.)

(c) How many failures would there be for generate-and-test? It may either be computed in a straightforward manner if you know the number of variables, the size of the domains, and the number of solutions; or to write a program like the second part of solveCount.py.

(d) For the first 5 instances of arc consistency, explain which elements of a domain are deleted at each step, and which arc is responsible for removing the element. You need to explain it at a level for one of your peers to understand if this is the first time they have seen arc consistency.

(e) Show explicitly the constraint graph (arc consistent domains) after arc consistency has stopped.