[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem Description
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 & TechniquesHere' 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.
Programmer's Notes: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
have!) Here's the February 23 Mensa puzzle that resulted in program Version 3.0 posted today. Two added features for this puzzle make it several times more difficult that the original. It's only slightly more difficult for the for the computer program, but much harder for the humans trying to solve it manually or the programmer trying to tell the program how to do it. The complicating factors are: Letters can occur more than once with the added constraint that identical letters may not appear in the same column, row, or diagonal. Also, fewer letters than available cells are given, so the placement of extra unused cells must be determined by the solver. This puzzle is available as Mensa Feb 13, 2018 in the program list of available cases. For human solvers, I included a "Hint" option to help place the cells that must remain empty (only discovered after the program solved it for meJ). The program now has over 1000 lines of code so there may still be bugs, especially in the manual solving mode. If you find one, please use the feedback link below to let me know. And Have fun! June 18, 2018: Version 3.1 adds one more variant of the "no-duplicates" type. "Place 5 copies of the letters in the word FRUIT in a 5x5 grid with no letter appearing more than once in any row, column, or diagonal. Four letters have been pre-placed to get you started." This is puzzle "5x5 Fruit" in the saved puzzles list.
Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |