December 1997 Programmer's Challenge
Clueless Crosswords
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm EDT, Monday, 1 December 1997
Clueless Crosswords
A couple of months ago, Bob Noll sent me a Challenge
suggestion involving a crossword puzzle variant published by one of
his local newspapers. The difficulty in using that suggestion was
deciding how to provide the clues to the puzzle in a usable form. I
thought about providing some sort of thesaurus, but giving simple
synonyms as clues didn't seem to capture the crossword spirit. Then
it occurred to me that clues serve only to make the crossword easy to
solve, an advantage that certainly wouldn't be needed by our skilled
Challenge readers or by the code they write. So the Challenge this
month is to write code that will solve a crossword puzzle without
clues.
The prototype for the code you should write is:
#define kMaxSize 32
typedef char Puzzle[kMaxSize][kMaxSize];
void Crossword(
Puzzle thePuzzle, /* return solved
puzzle here */
char *dictionary, /* array of words to choose from */
long puzzleSize, /* number of rows/cols in
puzzle */
long dictSize /* number of
words in dictionary */
);
Your Crossword routine will be provided with thePuzzle, where cell
thePuzzle[row][col] will be initialized to a zero if you are to fill
in that cell, or initialized to 0xFF if the cell is blacked out. The
first puzzleSize rows and columns constitute the puzzle; the
remaining cells in thePuzzle array are padding and should be ignored.
You are to fill in the empty cells of thePuzzle with words from the
dictionary provided, such that each uninterrupted sequence of blank
cells, both horizontal and vertical, forms a word from the
dictionary. The dictionary will contain all of the words needed to
solve thePuzzle, but, to make things more interesting, it will also
contain extra words not needed to solve thePuzzle. The dictionary may
contain only a few extra words, or it may contain as many as 10 extra
words for each word used in thePuzzle. Words in the dictionary are
not guaranteed to be in any order, and any word might be used more
than once in thePuzzle.
Each puzzle is guaranteed to have at least one solution using the
dictionary provided. You will be guaranteed 20MB of memory for your
code, static data, and any dynamically allocated memory. You may use
more memory if it is available, but your code should detect and
respond to memory allocation failures if you ask for more than the
guaranteed amount of memory. As always, you must deallocate any
dynamically allocated memory before returning.
This will be a native PowerPC Challenge, using the latest
CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.
The Challenge winner will be the entry that provides a correct
solution to a set of crossword puzzles in the minimum time. Thanks to
Bob Noll for suggesting a crossword puzzle problem, he wins two
Challenge points for the suggestion.
|