Double Word Squares

[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.  (Now more properly referred to as "Double Word Squares".  See October 19, 2015 update below.)

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 slight 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 do not contain any letters not 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 and 2.) Each of the columns must be valid words.  When these conditions are met, we have found a solution.

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 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. 

Running/Exploring the Program 

Suggestions for Further Explorations

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

 

Original:  March 22,2014

Modified:  February 18, 2016

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