[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 & 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.

Also, two Search buttons implement different methods for the program to find the solution. The first inserts all 7! (7x6x5...x1=5040)  arrangements of the seven unused letters into the board until one meeting the "no close neighbors'" requirement is found. The second, faster, method applies letters one at a time and validates that the requirement is
met after each insertion. If there is an adjacent letter in an adjacent cell, that path is abandoned and the program "backtracks" trying the next unused letter until a path to success is found. The technical name for this kind of search "Depth first with backtracking" and is much faster than method 1, especially with many cells to fill.

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

As usual, the most fun part is implementing the algorithms to solve the puzzle.  Anticipating user screw-ups unanticipated actions when we let them interact with the program provide a different kind of challenge.  Kind of like real lifeJ.  

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!) 

 

March 26, 2018:

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.