Assignment 4

For more information on crossword puzzles, see the page for the Duke University course on AI and crosswords. Or you can read Ginsberg's paper on search and crosswords.

AIMA 4.3 (Crossword puzzles)
- Goal: Every white square contains a letter, and every word slot (horizontal and vertical series) contains a word from the dictionary. Most crossword puzzle makers also include the constraint that no word appears more than once in the puzzle.
- Initial state: Grid of all empty squares and a dictionary of words.
- Operators: Many to choose from, but basically either you can go a word at a time or a letter at a time. If you choose word at a time, then an operator fills a word slot without violating the constraints imposed by the letters already appearing in the word slot and that length(wordSlot) = length(word). The new state has the word slot filled in and one fewer word in the dictionary (if we go with the "No word appears more than once" rule.)
- Path cost: Don't care, because we can't have cycles or infinite paths.
  
  Search strategy: A constraint-satisfaction approach is a good one. Word slots are the variables, and words are the values. The domain of each variable is the set of all words in the dictionary that are the same length as the slot. Constraints include the "No word appears more than once" rule and that at word slot intersections, the two words must have the same letter.
  
  Heuristic: Once again, lots of choices. Most constrained variable is important, but its costly with a large dictionary, because you would have go through every word to see how many fit into a slot. Least-constraining variable is workable too. Of the n words that could fill a slot choose the one that imposes the fewest constraints on intersecting word slots (i.e., use the most common letters at those slots).
AIMA 4.17 Comparing search algorithms

The hard part here was not running the algorithms, but analyzing the results. You could run the code with:
```
(compare-search-algorithms
   #'8-puzzle-problem
   '(A*-search SMA*-search IDA*-search))
```
We would expect that IDA* would do well on the 8-puzzle and poorly on TSP, because the solutions have real-valued, distinct costs and so IDA* adds only node per iteration. IDA* will perform poorly on the puzzle when a small (< 1) random number is added to the heuristic values.