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
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.
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.
e-mail with your comments about this program (or anything else).
Place one of A, B, C, D into each of the 25 empty cells so that the number of
letters in each row and column areas is as indicated by the numbers. Identical
letters cannot be next to each other in the grid either horizontally or
Background & Techniques
This puzzle is based on the August 11, 2016 daily Mensa Calendar Puzzle
and aids solving by automatically updating the available letter
counts as letters are entered. To play, enter one letter per cell. Change
a letter by typing over it which update counts appropriately.
Remove a letter by selecting it an using the "Del" key or entering a space
character. The puzzle is solved when all count cells are zero.
A hint which may help in solving: The "Identical letters cannot be placed next
to each other" rule mandates a fixed placement for any row (or column) with
a count value of 3 for that letter. And of course, that also restricts where the
same letter can be place in the adjacent rows (or columns).
The "Solve" button will display moves made at a rate selected by the user. The
"Debug" radio button shows all placements attempted as well as the successful
There is currently only one puzzle available, but more may be added in the
future if I locate them or figure how to generate them.
Non-programmers are welcome to read on, but you may want to jump to bottom of
this page to download the executable program now.
Like many programs on DFF, I started his project because I didn't hhave
enough patience to solve it manually. Letting the program do the
"grunt work" made sense, but I decided to also allow users with a lot of
persistence to solve the puzzle by entering cell values. At least
the program will update the counts of required characters after each
Users can enter keys in cells, and delete or replace them as desired in
A StringGrid1KeyPress procedure for each key:
- Validates that the key can be placed without violating the "no
adjacent duplicates" rule
- Creates the Pathlist entry and appends it to the list.
- Decrements the character count column and row fields for this cell, and
- Enters the keyed character in the selected cell.
- Checks if all 40 count cells have '0' value and shows a
Contratulations" message if so.
The "Undo" button required keeping track of the previous character as
letters are entered. A "PathList" stringlist does this with 2
character keys; the new character end the replaced character. A simple
TPathObj object in each list entry contains the column and row information
required when multiple "Undos" are requested.
The auto-solve section of the project was a logical candidate for some sort of exhaustive search with
backtracking. However , with 4 letter choices for each of the 25 cells to
fill, the upper limit of tests is 425 (420 if we exclude the 4 adjacent cells
which cannot contain the same letter), That smaller number is still more than a
trillion tests and led me to the "solve by column" strategy. The algorithm
first checks for any count of 3 letters in a row or column. The 3 Bs in
row 5 allows to fill cells [4,5] [6,5], and [8,5] with Bs immediately.
Similarly, the 2 Bs specified for row 6 must be placed in [5,6] ad [7,6].
So we now have only 4 letters to place in each column. The bad news is
that we must also now keep track of which 4 rows need to be filled. I used
an "Indices" array to hold the locations built by examining the rows in the
current column and entering those with blanks into the Indices array.
The required number of occurrences of each of letter must match the number or of
blanks found in the column they will allows us to build and initial "PermutedLetters"
The Combos class will let us generate all permutations of the required
letters and one of them must be correct if a solution exists. The
function does the grunt work for each column. Because of the
recursive nature, we need an array of Combos controls, one for each column.
Here's an outline of the jobs performed:
- Building the Indices array giving the rows where the letter will
- Building the PermutedLetters
- Generating and validating each permutation to ensure both the "no duplicate
neighbors", and positive available letter counts for the cell column and
- Duplicate letters in ithe PermutedLetters
will produce duplicate permutations so the first occurrence of each set will be saved in the "TryList"
stringllist and further duplicates are skipped if already in the list.
Again, because of the recursion activity, we need a unique Trylist
for each column, so we actually have an array of these lists.
- When a column has been successfully placed, FillNext calls itself
passing the next column number if there are more columns fill.
If the last column has been filled, we have a solution and the user is given
the choice of stopping or continuing the search. If the function call
returns a False Result, we continue in the loop generating the
next permutation. If we run out of permutations without a True
Result, we pass False result back to the guy that called us (the
previous column loop), so he can do the same thing.
That's a brief summary of all that happens in finding a solution. The
code is semi-generalized to handle other puzzle sizes, but since none are known
to me, I have depended on four letter choices in a 5x5 array in some of the code
I'm sure. That will leave something to work on when the time comesJ.
Running/Exploring the Program
Suggestions for Further Explorations
||Generate new random puzzles. (Generating
should be easy, generating puzzles with a only one solution might be harder.)
|Original: August 28, 2016
August 29, 2016