Square Word Grids

[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

This program implements the generation, user play, and program solving of Square Word Grids. 

Background & Techniques

Square Word Grids are an extension of our Word Squares program previously explored. "Word Squares" are square grids filled the same set of words in both the horizontal and vertical directions; 1st row matches 1st column, 2nd row matches 2nd column, etc.

"Square Word Grids" still have words in every row and column, but not necessarily the same words. These are harder to build and to solve because the search space for possible words is much larger. In fact, Word Squares are so common that most grids produced by this program will of that variety!

Click for solution

The program provides your choice of two dictionary sizes. Grids can be 3x3, 4x4, or 5x5 letters in size. An initial 3x3 default puzzle with one letter pre-filled is presented.  Users are given the set of unplaced letters  to complete the grid by selecting a grid cell with Mouse clicks or arrow keys. Pressing the "Del" or "Space" keys or typing over an already placed letter will return it to the "Unused" string. If you get stuck, you can see more letters by increasing the "Prefilled Letters" box value. 

For the 5x5 size, I usually need to see at least 7 letters to find the solution manually.  Above a typical sample screenshot.  If you want to try it with pencil & paper, the missing 17 letters are ACCEEEEHNNRSSTTUU.   Hint: It is a "Word Square".   

The "Generate" button  will create a new random puzzle using current parameters. Larger puzzles with the large dictionary may take a minute or two. The "Let program solve" button may take a very long time to solve a large puzzle. Once every minute it will offer to "cheat" and display the solution found by the Generate button. After finding a solution, the search will continue looking for additional solutions and offer to display them in the text are if found.  The search for either Generate or Solve operations may be interrupted by clicking on the "Stop" button.  
 

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

The program has 750 or so lines of code, but much of it is user interface stuff;  managing user keyed entries, allowing searches to be interrupted, handling parameter changes, etc.  The interesting parts are the Generate (GenBtnClick, 140 lines of code) and Search (SearchBtnClick, 170 lines of code) methods.  

""Generate" builds a list (List) of all possible words by scanning  the dictionary for words of the proper length, the recursive GetNextRow  function starts at a random location within List and proceeds sequentially looping back to the beginning if necessary until all words have been checked.  For each potential row, the PossibleSolution method is called to see the the partial columns built so far are the starting letters of words in List.   If so a recursive call to GetNextRow tries to fill the next row.  If no possible next row word exists, we just continue on to the next word.  When all rows have been filled, we save the solution and a FillLetters string with all of letters used in a CurrentCase record and exit.

For Searching, the approach is slightly different.  We know all of the letters, just not where to put them.  So first we will build List with words of the required length and which only contain  letters  in the FillLetters string of the CurrentCase record.  The solution must be some arrangement  of 3, 4, or 5 of these words which contain all 9, 16, or 25 letters depending of grid size.  The TCombos unit selecting  "Combinations with repeats" will find sets of words meeting that requirement and some permutation of one (or more) of these sets will form a solution (or solutions).  The two requirements which must be met are 1. Letter positions must match the pre-filled grid letters fwords and 2.) When a row word is added, each of the columns must be compatible with completing a valid word.  When grid is full and these conditions are met, we have found a solution.

Version 3  takes advantage of preplaced "hint" letters to build two arrays of  lists of possible words for each row and column.  Each of these list arrays is sorted by increasing list length the the two array merged into a singe array with alternating row and column word lists. This array it processed recursively, so the the rows and columns get filled alternately with the ones with the fewest word choices processed first. This can quickly fill the grid  with the proper words and minimize time spent "backtracking"

   

August 15, 2014:  A recent Mensa calendar puzzle provided the 2nd example of this puzzle type and prompted me to create Version 2 allowing puzzles to be manually entered.  (The original puzzle was hard coded to produce the default puzzle.)

Version 2 of the program also adds the ability to save and restore puzzles.


 

October 19, 2015: 

Complete this grid with 10 different words using the given letters

I recently discovered the was a perfectly good name already defined (Double Word Squares) for  what I had been calling "Square Word Grids" to distinguish them from the symmetrical "Word Squares" puzzles.    Version 3.0 posted today has several major enhancements and has occupied my spare time for the past 8 weeks!  I will admit that the "fun level" decreased during the period and I reverted to "never give mode" several times.  The resulting product still needs polishing, but I'm convinced that it mostly works.  The changed and new features include a revised search algorithm and revised user interface.  Briefly:

  • The search for solutions uses an improved algorithm  that solves the above 5x5 grid in less than a second.  The previous version ran for more than 10 hours without success. on this August 10 Mensa Calendar puzzle.   

  • User options now include Load, Generate, Manual Entry, and Modify Current Puzzle.

  • User can specify whether duplicate words are allowed in solutions.  

  • One new Hint is now given for each Hint button click.  Clicks will remove invalid characters placed by the user .  If all characters in the grid are correct, one additional correct character will be added for each click.  If the solution is not known to the program, hint requests are ignored.

  • The color letters placed on the grid reflect its status: Green for correct, Red for incorrect, Black for unknown solution.

  • A Score is calculated as characters are placed.  2 point for placing a Green or Black letter.  -1 point for removing a Red or Black letter.   Historical high score is saved with the saved puzzle.

  • All saved puzzles are saved in a file named "Puzzles.ini" in the same folder as the program.  A dozen or so of my testing puzzles are included.  The file is a Windows "init" file in plain text and readable by mere mortals if you are curious.  Feel free to delete any cases not of interest.  Edit cases here with caution since formats are assumed to have been generated by the program and therefore correct. 

February 2, 2017:  One of the shortcomings of prior versions was their inability to solve 5x5  problems except when it generated them.  I'm embarrassed to admit that i had forgotten that I rewrote the program in October 2015, and renamed it to "Double Word Squares".   The good news is that that the October version could not solve a recent Mensa Calendar puzzle that today's posting does.  Version 3 is a major rewrite of the solution search algorithm. Solutions for 5x5 puzzles with hint letters can now found in a few seconds. Previous versions could only solve puzzles generated by the program.  Mensa puzzle "Mensa_Dec 27, 2016" is now included and is solved quickly. A new checkbox allows intermediate results to be displayed as the search progresses; very useful for debugging while the program was being developed. There is also an "Allow duplicate words" checkbox which will allow or deny those symmetric Word Squares being returned as solutions.   I have reverted the program name back to Square Word Grids because, according to Wikipedia, all words in Double Word Squares must be unique.  This "Allow duplicate words" version will return "mixed" solutions in which only some words appear more than once.    

Running/Exploring the Program 

  • Download  executable
  • Download source  (Note: Several routines used in the program are contained in our DFFUtils unit which resides in the library zip file of commonly used units.  Library file DFFLIBV13 or later is required to recompile this program )
  • Download current library file (DFFLibV14_12Nov2016) required to recompile.

Suggestions for Further Explorations

There is no real reason for the grids to be square!
 
   
   

 

Original:  March 22,2014

Modified:  February 03, 2017

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