Crossword Generator

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

bulletAn extended search option will try up to 1000 puzzles trying to generate the specified number of words. 
bulletThe initial puzzle word is now offset near the center of the puzzle to allow more possibilities for fitting words.
bulletThe final puzzle is centered on the board
bulletThe primary word is displayed and may be modified by the user from within the puzzle.  (I haven't yet checked the effect of this on any clues which may have been defined though.) 

Addendum March 8, 2008:  Version 3.1 adapts ideas from grandson Luke to insert partial versions of words used in WordSearch puzzles to make the words harder to find. He also preferred backwards and inverted diagonal locations.   He's a fiendish little devil!  Works best with longer search words such as the newly included LukesPuzzle.txt with words from his homework assignment .  Manually construct a search word puzzle using the given words from our current reading project, 'The Odyssey'.   In the 6th grade yet!

As usual, bug reports appreciated.  

Running/Exploring the Program 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Whew!  Lots of room for improvement to turn this into a real Crossword Puzzle Generator:

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.

 

Original Date: April 28, 2003 

Modified: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.