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 {browns, 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