Question 2

Consider the following crossword puzzle.
Horizontal: DIE, DRY, OAK
Vertical: AIR, KEY, ODD

All six words must fit into the grid, horizontally and vertically, as indicated. Design a state representation for this crossword puzzle. This representation should capture the arrangement of words in the grid, the words and all the information needed to facilitate solving the puzzle using AI algorithms. Use mathematical notation or a programmatic representation (Python or pseudocode are obvious choices). Show the variables you will use, as well as the domain(s) and restrictions that show how you would make sure that only the given words will be allowed.

a. Using your notation, show the start state of the grid.
b. Design an algorithm to solve this problem, using your state representation. You can write your answer in pseudocode or a detailed discussion, from which someone should be able to implement a solution in code.