[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
In this puzzle, insert the letters A through J, one per square, so that no
two letters in alphabetical order are in squares that touch in any way, even at
the corners. Three letters have been placed to get you started.
Background & Techniques
Here' another entry from our Mensa Puzzle Calendar, April 17, 2016 this time.
You can enter letters yourself into the blank cells to find a solution.
As usual, the most fun part is implementing the algorithms to solve the
puzzle. Anticipating user
A 4x4 TStringGrid with some of the cells eliminated is good enough for the three puzzles of this type I have run across so far. Rather than try to eliminate grid lines, I chose to just to blackout unavailable cells. This happens in the OnDrawGrid event exit for cells containing a period (.) character .
The OnKeyPress routine to handle user inputs has about the same amount of code as the two search routines combined! In Play mode, it must ensure that the user key is in the allowed range, is not a duplicate of a key already entered, is not one of the pre-filled letters. Also its location ,must not be on a blacked out cell or on a pre-filled cell. I chose not to validate the "no close neighbors" condition until all letters had been filled and either declare success or display detail of the first violation found.
"Build" mode has a another set of problems. I finally decided to require that the definition of blacked out cells precede entering the pre-filled letters since the range of pre-fill letters is determined by the number of black-out cells.
The first solution search button uses the TCombos unit to generate all 5040 permutations of the 7 letters in the original problem (7!= 7*6*5*4*3*2*1=5040). It only takes a fraction of a second to find the solution but if we start with an empty 4x4 grid, there are 16! ( about 20 quadrillion possibilities) to check - I might not live long enough to find a solution! The second, the Recursive, solution method finds the first solution of an empty grid in less than a millisecond! Both search types hopefully have enough comments in the code to make it understandable.
December 6, 2016: The December 4th Mensa Puzzle Calendar
contained the first version of this puzzle type that I've found that is not
based on a 4x4 grid; This one is 5x3 and motivated me to update the
program to allow multiple puzzle sizes. I also added the ability to name,
save, and restore puzzles. (After reentering this one the first dozen
so times while testing, I decided that saving/restoring was a good feature to
Suggestions for Further Explorations
Copyright © 2000-2017, Gary Darby All rights reserved.