Module 6 (Constraint Satisfaction Problems)

Assignment 6

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*.

- 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:

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).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

- 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).
- Show how arc consistency can be used to solve this problem.
To do this you need to:
- draw the constraint graph,
- show which elements of a domain are deleted at each step, and which arc is responsible for removing the element,
- show explicitly the constraint graph after arc consistency has stopped.
- 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.

Suppose that each word position is a variable, with domain a set of words. The value of the word position is the word that goes into that position.

Suppose we have the following variables and domains:

The constraints are that the intersecting words have to have the same letter in the intersecting positions.

Variable Domain 1-across {ant, big, bus, car, has}3-across {book, buys, hold, lane, year}4-across {ant, big, bus, car, has}1-down {book, buys, hold, lane, year}2-down {beast, ginger, search, symbol, syntax}

- This is not arc consistent. Give one domain value that can be pruned. Explain which arc can be used to prune it any why.
- Give the domains where arc consistency stops (without domain splitting).
- Show how hill climbing can be used for this problem. Suppose a
neighbour is obtained by changing the value of one of
the variables to the alphabetically next or previous domain element. The heuristic function to be maximized is the
number of satisfied constraints, and you always choose a neighbour
with the maximal heuristic value (even if it is the same as the
current node).
- Show the sequence of assignments and corresponding heuristic values when we start with
the assignment:
*1-across=ant, 3-across=book, 4-across=ant, 1-down=book, 2-down=brown.* - Suppose Alex suggested using the domains pruned by arc consistency, but otherwise the same. Is this a good idea? Explain. Does it work well?
- Suppose Joe suggested picking any domain element as long as it improves the heuristic value. Why might this be better or worse than the original solution? Does it work well?

- Show the sequence of assignments and corresponding heuristic values when we start with
the assignment:

David Poole