Question

Consider the problem of constructing (not solving) crossword puzzles: fitting words into a rectangular grid. the grid, which is given as part of the problem, specifies which squares are blank and which are shaded. assume that a list of words (i.e., a dictionary) is provided and that the task is to fill in the blank squares by using any subset of the list. formulate this problem precisely in two ways:
a. as a general search problem. choose an appropriate search algorithm and specify a heuristic function. is it better to fill in the blanks one letter at a time or one word at a time?
b. as a constraint satisfaction problem. should the variables be words or letters?

Answer 1

a) The problem of crossword has a number of ways to solve. In these, Depth-first-search is the best way to solve the problem.

For this problem, the words which are crossing to each other must have same letters at the cross position. These problem are also known as constraint satisfaction problem.

The table to show the crossword game is as given below.

The hints of words according to the locations in the game are as given:

AFT        LASER

ALE         LEE

EEL         LINE

HEEL      SAIL

HIKE       SAIL

HIKE       SHEET

HOSES   STEER

KEEL       TIE

KNOT

The numbers 1, 2, 3, 4, 5, 6, 7, and 8 are the positions in the crossword game for the locations of words.

b) For the problem of constraint satisfaction, the value of variable should be letter. This is because, each letter in the game is stored in a separate box and word is made by the collection of letters. This is heuristic approach for solving the game. The diagram to show the flow of process for the completion of word is given in the second image below.