Question 2

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:

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}

1. This is not arc consistent. Give one domain value that can be pruned. Explain which arc can be used to prune it any why.
2. Give the domains where arc consistency stops (without domain splitting).
3. 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).
   1. 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.
   2. Suppose Alex suggested using the domains pruned by arc consistency, but otherwise the same. Is this a good idea? Explain. Does it work well?
   3. 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?