Wordsquare generators - source code
This is a resource of the
Click to subscribe to wordgame-programmers
These programs generically fit words (in straight lines, not wrapped
around odd paths as in Boggle) into rectangles.
The epitome of these form perfect squares, in the tradition of
However other variants are allowed to leave some blank spaces
(if the blank spaces are givens, the code is similar to a crossword
generator in spirit but usually not in implementation).
- Doug McIlroy's Wordsquare
This may be possibly the earliest wordsquare program, written by Doug
McIlroy (early Unix pioneer) in 1975. Cleanly written, could have been
written yesterday. Still works. Says a lot about good programming
practices and the longevity of the C language.
This is my own word square generator and the only one I know of
on the net (except Patrick Niesink's below) that has enough
optimisation to be able to compute a 10-square within a reasonable
time, given a word list large enough. People particularly interested
in word squares should read some of the archives of the
wordgame-programmers mailing list. This is a very CPU intensive
task and to do an exhaustive search needs a good algorithm. In October 2007 I ran this code - modified slightly to support a parallel
decomposition - on an array of 512 CPUs. With this program I
multi-lingual tensquares. Unfortunately I was unable to find any
11-squares at all, and it is unlikely that I will be able to expand the size
of the wordlist sufficiently to make any greater likelihood of ever finding
any (without cheats such as compound words or phrases, or leaving blank squares)
Martin Laeuter took my wordsquare package and ran with it!
He has done good work on the dawg code to speed it up,
and he tries some novel approaches to ordering of tests
in order to speed up the generation of the first successful
wordsquare. He has recently (April 2001) released an update
to this code which extends the code to solving crosswords as well.
Three things here:
- Maxiscore: a French newspaper puzzle to fit as many words in a
crossword-like grid as possible. There
is a scoring scheme to be optimised, and the words which may be fit
are constrained in several ways.
- In "mail.txt", he discusses a variant of word squares where one
or two (or the minimum number possible) squares may be left blank.
- This directory also contains his modifications to my wordsquare
program - he uses bit vectors instead of strings, for a low level, but
Patrick Niesink's code to generate word squares and word rectangles. I believe this is fairly efficient code.
David Eppstein writes: "The algorithm is a little different from the one-word-at-a-time searches
sketched above -- instead I keep a
data structure in the form of an n*n square, where each cell of the square
holds a set of letters. I then repeatedly run through the dictionary to
determine which words are possible in each row and column, using only the
allowed letters in each position, and use those sets of words to prune the
sets of allowed letters.
If this procedure stabilizes while there is still ambiguity in the choices
for some positions, I pick the position that has the fewest choices and
branch, either taking the first choice or continuing with the remaining
choices. So this eventually degenerates to a brute force backtracking search
but the intention is to make as much progress as possible with the dictionary
between each branching step.
As noted above, the quality of the word list is important to the quality of
the results. My program defaults to /usr/dict/words, but that's not a great
choice because it only has the stemmed form of each word. I've been running
it with my cryptogram dictionary instead, but you have to carefully check the
output because that dictionary has a lot of non-words."
- John Walker's squaring/
John Walker is the sort of programmer we all aspire to be - a techie's techie
who made it big in business but never gave up programming. It's just now he
can afford to do it for fun... and one of his fun programs is a word-square
generator, which he was inspired to write following a challenge from Charles
Babbage to find a word square starting with the word Bishop. Walker's site,
Fourmilab, is well worth a visit.
- Kragen Sitaker's program in Python
Old wordsquare generator from DEC Gatekeeper archives
Also included here are programs which squeeze as many words as possible
into an area, even if they leave some empty squares. Some of these
are variants of crossword generators.
Fit a list of words into a 20x20 area, with as much overlap as
possible. Note this code could easily be adapted to generate
highly criss-crossed ScrabbleTM layouts.
This is about fitting words into small spaces. It is not quite about
wordsquares as not all rows and columns have to be exact words; it is not
quite a Boggle generator as the words it does fit must be in a straight
line. Actually it's pretty damn similar to the wordsearch generators
except it tries real hard to squeeze them in tight. And it
uses a Scrabble-like scoring system.
Closely related to this field are Crossword generators,
and wordsearch generators.
Return to the Archive overview.
Boggle is a trademark of Hasbro Inc. (formerly Parker Brothers).
Scrabble is a trademark of Hasbro Inc in the US (formerly Selchow
and Righter) and Mattel (formerly J.W. Spears) elsewhere.