Solution

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.

   ant can be pruned from the domain of 1-across using the arc <1-across,1-down> as there is no element of the domain of 1-down that starts with "a".

2. Give the domains where arc consistency stops (without domain splitting).

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

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=browns.

      Here is one possible sequence:

      1-across	3-across	4-across	1-down	2-down	h-value
      ant	book	ant	book	browns	1
      big	book	ant	book	browns	2
      big	book	ant	book	ginger	2
      big	book	ant	buys	ginger	2
      big	book	big	buys	ginger	2
      big	buys	big	buys	ginger	2
      big	hold	big	buys	ginger	2
      big	lane	big	buys	ginger	2
      big	lane	big	hold	ginger	3

      This reaches a foothill, and never solves the goal.
   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?

      Yes. In fact it seems stupid not to do this. This works much better, if only because the search space is smaller, the plateaus seem smaller, and it more quickly finds better foothills. For example:

      1-across	3-across	4-across	1-down	2-down	h-value
      bus	lane	ant	buys	search	2
      bus	lane	ant	buys	syntax	4
      bus	lane	ant	hold	syntax	4
      has	lane	ant	hold	syntax	5

   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?

      This again works better, but the cost of each iteration (finding the neighbours) is more. It isn't obvious that the extra time would be better spent trying different starting points.

      Here is one possible sequence:

      1-across	3-across	4-across	1-down	2-down	h-value
      ant	book	ant	book	browns	1
      big	book	ant	book	browns	2
      big	book	ant	buys	browns	2
      big	year	ant	buys	browns	2
      big	year	ant	buys	ginger	3
      big	year	ant	buys	search	3
      bus	year	ant	buys	search	4
      bus	year	car	buys	search	5