Programming Problem #8
"Crossword Puzzles"

Given a word list and a description of a crossword puzzle grid, your job is to display the grid with all of the words filled in.

The input consists of one or more data sets. Each data set begins with a line containing a single positive integer N. After this are one or more lines containing word regions. Each word region is on a line by itself and consists of four integers R, C, O and L beginning in the first column and separated by spaces: R and C are the row and column numbers at which the word appears 1 <= R,C <= N, O is the orientation (0=across, 1=down), and L is the length of the word. Immediately following the word regions will be a list of words, one per line beginning in the first column. The number of word regions and words will be equal.

The output is an NxN grid of characters with all of the word regions filled in with words from the list. Note that the words and word regions need not correspond, e.g., the first word doesn't necessarily go in the first region. You must compute which word goes in each region based on word length and region intersections. At least one solution will always exist; if there are multiple solutions just display any one of them. Consecutive output grids must be separated by exactly one blank line.

Input must be read from the file "prob8.in", and output must be written to the file "prob8.out". All output to the screen will be ignored.

Example Input

<BOF>
5
1 1 0 4
1 1 1 3
5 1 0 4
1 4 1 5
3 1 0 5
BEST
TIC
EVENT
CONES
TUNE
2
2 1 0 2
1 2 1 2
1 1 1 2
1 1 0 2
AT
TO
AN
NO
<EOF>

Example Output

TUNE
I  V
CONES
   N
BEST

AT
NO
A version of this problem originally appeared in the 1984 North Central Regionals.

Also check out the Crossword Generator.

Dr. Eric Shade