Documentation

Given an empty, or almost empty, crossword puzzle grid and a set of words, the problem is to place the words on the grid.

Words are strings of at least two characters. A horizontal or vertical sequence of spots in the crossword puzzle grid is called a site. Our problem is to find a compatible way of placing words onto sites. Each word should be placed at most once at a site.

Try to solve the \(25 \times 25\) crossword puzzle in crosswordPuzzle'.

Examples

>>> :{
crosswordPuzzle == Crossword
  { word = ["ALPHA", "ARES", "POPPY"]
  , grid = [ [ Left False, Left False, Left True,  Left False, Left False ]
           , [ Left False, Left False, Left True,  Left False, Left False ]
           , [ Left True,  Left True,  Left True,  Left True,  Left True  ]
           , [ Left False, Left False, Left True,  Left False, Left True  ]
           , [ Left False, Left False, Left True,  Left False, Left True  ]
           , [ Left False, Left False, Left False, Left False, Left True  ]
           ]
  }
:}
True

>>> head $ fromJust $ solveCrossword crosswordPuzzle
[Nothing,Nothing,Just 'P',Nothing,Nothing]

>>> printCrossword $ solveCrossword crosswordPuzzle
■ ■ P ■ ■
■ ■ O ■ ■
A L P H A
■ ■ P ■ R
■ ■ Y ■ E
■ ■ ■ ■ S

A crossword puzzle.

A list of words to fill the puzzle with is given along the grid to fill. The crossword puzzle grid is represented with a list of sublists. Each sublist denotes a row, and each value in the sublists denotes a spot. For each value in a spot:

• True denotes a blank spot that needs a character to be filled in.
• False denotes a spot that cannot be filled in.
• A character value denotes a spot pre-filled with the character.

A crossword puzzle of size \(5 \times 6\).

This is the puzzle used as the example for solveCrossword.

A crossword puzzle of size \(25 \times 25\).

This is the puzzle in file p99d.dat included with problem 99 in the original list of problems.