Wordsquare generators - source code

This is a resource of the wordgame-programmers@egroups.com mailing list.



Click to subscribe to wordgame-programmers

SATOR
AREPO
TENET
OPERA
ROTAS

• 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.
• wordsquare/
  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 found 59284 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)
• laeuter/
  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.
• jean-charles/
  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 significant speedup.
• patrickn/
  Patrick Niesink's code to generate word squares and word rectangles. I believe this is fairly efficient code.
• eppstein/
  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
• facto.c
  Old wordsquare generator from DEC Gatekeeper archives

• potm/crozzle/
  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 Scrabble^TM layouts.
• potm/old-problems/scrabblesquare.txt
  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.

• French magic square site
  No code, just squares (maybe some javascript display code).
• Chris Long's papers
  "Why Johnny Can't Construct a 10-Square"