[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionThis program implements the generation, user play, and program solving of Square Word Grids. Background & TechniquesSquare 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. 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". 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:
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:
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
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |