No Close Neighbors

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]




Search WWW


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 feedback 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.  Thanks


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.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)


Feedback:  Send an e-mail with your comments about this program (or anything else).

Search only




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 

bulletDownload  executable
bulletDownload source  (Note: the UComboV2 unit used to generate the permutations in the first search method resides in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile this program )
bulletDownload current library file (DFFLibV15).


Suggestions for Further Explorations

Dec. 2016: Done! Add code to generate additional puzzles with unique solutions
Dec 2016: Done! Save and reload puzzles in a .ini file.
Original:  April 24, 2016

Modified:  June 18, 2018

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2018, Gary Darby    All rights reserved.