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

 

Search

Search WWW

Search DelphiForFun.org

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.

Contact

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

Search DelphiForFun.org 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!) 
 

Running/Exploring the Program 

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:  December 06, 2016

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