[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
A program which demonstrates another depth-first dictionary search; this one to find all words of a given length from a grid of letters by moving from each cell to any of the neighboring letters.
Background & Techniques
This program was prompted by a puzzle from our 2011 Mensa 365 Brain Puzzlers Calendar. It uses our TDic dictionary class to validate word candidates as valid words. Users can specify target word length and additional grid sizes. Other grids to search can be randomly generated or entered manually. Save and Load buttons can be used save and reload grids.
The program clearly does not know which words meet the given definitions, but it did find enough words to allow me to solve the puzzle completely.
From the Delphi Techniques side, three areas of potential interest to programmers are:
The search: The SearchBtnClick event exit starts the search. CheckWordsFrom is the recursive search procedure and SearchBtnClick passes it then letters from each cell in the grid to start the search. CheckWordsFrom first checks to see if the passed string is equal to WordSize, the specified word search length. If so, add it to ListBox1 along with the Tinteger representation of the path that got us here. The integers in the path list represent locations on the grid as 256*Column number + Row number. Later on we can extract the Column and and Row again by dividing by 256. (Using logical operators SHR, shrift right, and "AND": Col = N SHR 8 and Row = N AND 255.)
If the string passed to CheckWordsFrom is not yet of the desired length, we'll loop through each of the 8 neighboring direction from the passed cell location and, for those that are not out of bounds, adding that neighbor to the string and do the recursive part (call ourselves with the new location and length). Upon return return, we'll delete that letter and continue looking for other neighbors to check. By the way, for 5 letter words on the 5x5 grid, I calculate that this checking neighbors operation occurs about 26 billion times! No wonder it takes a minute or so to complete. See the "Suggestion for Further Explorations" below for my idea to reduce search times.
Tracing the word paths: TStringGrid has an OnDrawCell event exit, GridDrawCell, which is called for each cell drawn and tailors the appearance of the display. This is the technique used to draw the word path when a word in ListBox1 is clicked. The path associated with the clicked word (in the Objects property of the Listbox entry), is saved as TIntList CurrPath. I found that some redundant drawing is required to ensure that complete paths are drawn. GridDrawCell is passed the column and row of the cell being redrawn, The row and column are used to construct the integer that lets us find where that letter is in CurrPath. From there a line is drawn to the center of the cells containing the preceding (except the first) and following (except the last) letters. GridDrawCell passes the canvas rectangle for the letter being drawn, but we must use the TStringGrid method CellRect to obtain the drawing location for the preceding and following letters.
Generating random letter grids: I originally generated letters for the Generate Random Grid button by using only the Random function; Ch := char(ord('A')+random(26)) will make the same number of each letter, e.g. as many "X"s as "E"s which didn't seem to be the best way to do the job. I went to Wikipedia and found a table of typical letter distributions in English text. About 12% of the letters are "E"s, but only 0.2% are "X"s. There is an established way to convert from a Uniform distribution to another arbitrary distribution. First we'll make a cumulative distribution table that for each X contains a Y value which is the probability that a random sample is less than X. Now if we take a random number N between 0 and 1 and find the last Y value in the table that is greater N, that X is the output value. As a simple example, assume that we only have 4 letters and the probabilities are A: 10% , B:20%, C:50%, DL 20%, then we could make a cumulative distribution table with values (10, 30, 80, 100) for ("A", "B", "C", "D"). Now it's easy to see that if we generate uniform random numbers from 0 to 100, 10% of them would be less than 10 (an "A"), 20% would be between 10 and 30 ("B"), 50% would be between 30 and 80 ("C") and the other 20% would be between 80 and 100 ("D"). This is the basis for generating the letters in the grid with relative frequencies matching their occurrence in English text.
April 17, 2011: Version 2 was posted today implementing the partial words lookup suggestion. A new "LookupPartial" function was added to theTDic class in our UDict unit. It returns true of there is at word within the specified word length range which begins with the passed letters. This truncates most of the search without following all possible paths to the full word length. It seems to work because the search time for the default puzzle was reduced from 35 seconds to 4 seconds!
Other changes were made and partially tested to handle the dictionary operations under Delphi XE where string formats have changed. Alphabetgrid will now compile and run OK under either D7 or D_XE Starter.
The DFFLIB library file has not yet been updated to include the new UDict changes, but I did temporarily add UDict to the source code download below as an interim measure.
September 1, 2011: Version 3 adds a new Mensa calendar puzzle and includes a critical piece that was missing from the previous versions: saving and restoring the clues! The new puzzle is included in the download as file Mensa_AlphaGrid_Puzzle_08_30_2011.txt.
In another small change the Search button now returns words that are candidates for being part of the solution in alphabetical order.
Suggestions for Further Explorations
Copyright © 2000-2017, Gary Darby All rights reserved.