Problem Description
Word Squares are square letter grids in the rows are words and the same
words also occur if read vertically. Give a starting word, we
want to find one or more Word Squares which have that word in the
first row and column.
Background & Techniques
|
C |
I |
R |
C |
L |
E |
|
I |
N |
U |
R |
E |
S |
|
R |
U |
D |
E |
S |
T |
|
C |
R |
E |
A |
S |
E |
|
L |
E |
S |
S |
E |
R |
|
E |
S |
T |
E |
R |
S |
Several years ago, I created a
Word Squares program which
displays the first word and letters required for the word square puzzles it
generates and challenges the user to complete.
Today's word square search program was prompted by
a Martin Gardner article in his book "6th Book of Mathematical Diversions
from Scientific American" first published in the 1960's. Those were my
college days when I was buying the magazine or visiting the library each
month just to read his "Mathematical Diversions" column. In the
"Word Squares" reprint he closes the section with the comment "To my
knowledge, no one has yet succeeded in squaring the circle"; a word-play
on the impossible geometry problem of constructing a square whose area is
equal to a given circle. I had to see if I could write a program to
accomplish the task for word squares. This program finds nine
solutions for "CIRCLE". If I had read to the addendums at the end of
the chapter, I would have seen that some time after the initial article
appeared, Martin received 250 different solutions!
The words used here are based on our
dictionary unit and uses our "Full.dic" dictionary file which contains
62,000 words. The dictionary is included with the downloads
below. The dictionary maintenance program, Dicmaint, which
can be used to add words to the dictionary is available from our
WordStuff 2 page.
To use the Word Squares Search program, just enter
an initial word and click the Search button. Longer words, 7 or
more letters, may take a few minutes. Click the Stop button at any
time to abort the search.
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
The UDict unit defines the default Pubdic instance of the
TDic class which is used in this program. The large dictionary,
Full.dic is loaded by calling the PubDic.LoadlargeDic
procedure at startup in the FormActivate method. We define an
array of TStringLists, Lists, to hold words beginning
with each of letters 2 through N of the N-letter input word.
The lists are loaded using PubDic.Setrange to restrict the
search range and PubDic.GetNextWord to retrieve N-letter words
beginning with the each of the letters of the input word (except the first).
After the lists are loaded, function TryWord(2) is called to
start the recursive search with word number 2 in the square. A string
array, Square, is initialized with the input word. Each call to
tryword(k) searches its list (Lists[k-2] ) for words which
meet criteria that the first K letters of row K match the
first K letters of column K of Square. Functions
Col and Row extract the letters from Square for the test.
If Col(K)=Row(K) the word is added to Square and then,
if K<N then a recursive call is made to TryWord(K+1) to search
for the next word. Otherwise K=N and we have a solution.
Procedure ShowSolution displays the completed square.
All-in-all, the coding took a couple of days with only one restart after
I realized that my original search attempt without the Row=Col test
would take impossibly long time for words longer than 5 letters and my first
approach at pruning the search space failed.
Running/Exploring the Program
