Word Square Search

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

 

Search

 

Search DelphiForFun.org only

Support DFF

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

In Association with Amazon.com

 

Support DFF

 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

 

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 

bullet Download source
bullet Download  executable

Suggestions for Further Explorations

Add a search for solutions based on random starting words of a given length.  My failure to find an unpublished 8x8 word square after trying a dozen or so words prompted this idea.  At 6 letters, probably 20 or 30% of the words have solutions using this dictionary.  For longer words, I believe that the probabilities decrease rapidly.  

 

Original Date: February 4, 2010

Modified: February 04, 2010

 

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