Problem Description
Here's a program to randomly generate a prototypical
crossword puzzle from a given list of words.
Background & Techniques
A viewer inquiry prompted this exercise. I suspect that it was a
college class assignment, so I only hope that my slow response in
generating this code removed the temptation to plagiarize.
It did require several days of brain exercise and debugging practice to
get this far - which is still far from a complete Crossword Generator
product.
The program does attempt to generate a puzzle with the specified number
of words within a specified range of word lengths on a board of specified
size. There is no backtracking to try multiple
solutions, so the puzzle is successfully generated or not. If fewer
than the desired number of words are generated, just click the
"Generate" button to try again. Unlike
commercial crossword puzzles, all words generated usually intersect with only a
single word running in the other
direction. It also does not generate clues or number the words
or print the resulting puzzle, so lots more work would be required to make
a real puzzle. But it's a start.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
Notes for Programmers
When generation is started, a word list, Words is loaded,
currently only from a file named named "Small.txt", into a
stringlist and "shuffled" into random sequence. This lets
us simply choose the first suitable unused word when
searching. Procedure LoadList accomplishes
this.
Words that have been added to the puzzle are kept in a stringlist named
UsedWords. A TUsed object specifying the starting
location and the the direction of the word in the puzzle is associated
with each list entry.
Function GetNextWord is the recursive routine which locates a position
for the next word to be placed. Horizontal and vertical
words are generated alternately to the extent possible. Execution
stops when the requested number of words have been generated or no more
words can be found to fit in either direction. Board is
an 2 dimensional array of characters which holds the letters.
Checking locations is simplified by making a one space border all the way around
the board so and N x N board is actually (N+2) x (N+2) cells. GetNextWord
processes the UsedWords list from bottom to top, looking for words
running in the other direction from the word we are trying to add.
When it finds one, it looks for a letter position within that word
where we could extend a word in either direction without abutting another
word. We then calculate the range the new word could extend and call
function FindAWord, passing it the maximum word length, and the
value and the position of the intersecting letter. FindAWord
searches Words for a word that meets the passed criteria and is not
on the UsedWords list. If it finds one and passes it
back, GetNextWord calls AddWord to add the word
to the board and to the UsedWords list and update the puzzle
display stringgrid.
That's about it - doesn't seem like it should have taken several days
and 400+ lines of code, but it did. And ,as usual, this is probably
less than than 20% of the code that would be required to make complete
commercial product. But I'm pretty sure that it was the most
fun 20%!
Enjoy.
Addendum August 1, 2004: Viewer Dahlia found a
bug! Non-square puzzle boards filled words only to the size of
the smaller dimension. Sure enough, one of the limit checks
interchanged "Hsize" and "VSize", It's now
fixed.
Addendum September 21, 2004: Very sharp programmer
and regular viewer, Charles Doumar added a "WordSearch"
puzzle option to my basic "Crosswords" generator.
That prompted me to make my part more useful, or at least more
usable. I added word numbers, clues, and a Print option,
making either type of puzzle one that can actually be printed and
solved. I've included a "starter" set of
topical word files, (birds,txt, skeleton.txt, elements,txt, and
time.txt), a couple with sample clues
included. Clues can be added "piecemeal" whenever
you want a complete printable puzzle that may have clues missing.
I hope that the program will be useful to teachers. I
encourage any viewer who develops a word list and is willing to
share it to send it to me and I'll update the distribution
package.
Addendum October 7, 2004: I updated the program today to
add a Print Preview feature which also allows titles to be added and
puzzled to be saved for later reprinting. The solution page
for Word Search puzzles is now available. Two addition
files with definitions have been added - German.txt contains words
in German with the English translations as the definitions, and FieldsOfStudy.txt
with more fields of study than you would have imagined exist (about
600!). Makes a tough puzzle!
Addendum October 12, 2007: After 3 years, time for an
update! Version 3 enhances puzzle generation in several ways.
It was motivated by a viewer who wanted to generate crossword
puzzles that would include all words from his daughter's weekly spelling
word list. The new version has these changes:
 |
Done Sept 21, 2004.
The source should probably be a data base that
includes text for clues. And possibly categories of words to
allow puzzles to be generated for a specific subject area. |
|
Puzzles could be more dense if words could
deliberately intersect
with more than one other word. Currently, this may occur by
coincidence, several words may cross the same words, but at the
time words were added, each new word intersects exactly one
word. |
|
Once clues are available, custom cell drawing will
be required to place word numbers in the cell with the first letter
of each word. |
|
Done Sept 21, 2004. Even before the database version, it might be
helpful to allow the user to select the text file to serve as the
source for words to be used. |
|
The code in GetNextWord routine is
essentially duplicated with the roles of horizontal and vertical
interchanged depending on which direction we are currently
creating. If I were doing it again, I would consider
maintaining two boards internally, one a 90 degree rotation of the
other and using common logic with the appropriate version depending
on the direction currently being created. |
|
Partially
done Oct 7, 2004: A print preview, printable puzzle title,
and online playable option would all be nice. |
|
Partially
Done Oct 7, 2004: (Print preview now allows puzzle images to be
saved and reloaded, which at least eliminates the need to run to the
Xerox machine for extra copies. ) The ability to save and reload puzzles would
allow more copies to be printed or minor changes made to existing
puzzles. I worked on this for a week, but haven't figured out
to interface with wordlists. What if the word list has changed
at reload time? A word in the puzzle might not even being in
the wordlist file at reload time. If a puzzle is reloaded and
changes are then made to clues, should the original wordlist
be updated or only a copy? I guess I would make a copy
of the wordlist to go with each puzzle. |
