Problems.P99

Description

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P99.

Synopsis

# 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


data Crossword Source #

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.

Constructors

 Crossword Fieldsword :: [String]List of words to fill crossword puzzle withgrid :: [[Either Bool Char]]Grid for the crossword puzzle

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Crosswords MethodsshowList :: [Crossword] -> ShowS # Source # Instance detailsDefined in Problems.Crosswords Methods

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.