### Problem Description

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.

### Running/Exploring the Program