ACM
In certain entertainment magazines there is a type of crossword puzzle where, instead of clues for words, the cells contain positive integers. There is a hidden one-to-one correspondence with numbers and letters, and the goal of the puzzle is to assign alphabet letters to these positive numbers so that sequences of two or more letters (across the rows and down the columns) form valid words. Your task is to write a program to help solve this type of puzzles.
Input
The input will consist of a series of games. Each game will have a valid dictionary of words (preceded by a size) that can be used, followed by a puzzle grid (preceded by r and c, the number of rows and columns). Each word will be at least 2 and at most 10 characters in length from the set `a'-`z'. The dictionary size will be at most 1000 words; the dictionary entries are unique but not necessarily sorted. Each puzzle grid consists of c columns, 1 c 10, and r rows, 1 r 10, of cell numbers in the range 0-26. A positive cell number denotes a letter and a cell number of `0' denotes a ` ' (blank character). The numbers form a continuous range, thus one can expect numbers such as 0, 1, 2, 3, 4, 5 but not 0, 1, 12, 13, 24, 25. The series of games is terminated by a ``game'' with dictionary size `0' and should not be processed.
Output
The output should consist of the guaranteed uniquely solved puzzle for each game, where the cell numbers are replaced with characters `a'-`z', ` '. A blank line should separate output solutions.
Sample Input
3
max
min
nix
3 4
1 2 3 0
4 0 0 0
5 4 3 0
12
boon
boonbar
boony
foobar
foorag
goon
goony
rannoo
ranoon
toon
toonbar
toony
6 6
1 2 2 3 4 5
2 0 0 2 0 0
2 0 0 2 0 6
5 4 7 7 2 2
4 0 0 8 0 2
9 0 0 0 0 7
0
Sample Output
max
i
nix
foobar
o o
o o t
rannoo
a y o
g n
Solution
Please refer the files def.h and main.cpp for solution. matrix.txt, words.txt and matrix1.txt, words1.txt are examples.
Download: puzzle.zip
02/28/2008
No comments:
Post a Comment