EarthDay Puzzle

[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

Place five copies of  the letters EARTH in a 5x5 grid, one letter per cell so that the same letter never occurs more than once in any row, column, or diagonal - even the short diagonals.  Four letters are pre-placed get get you started.

Background & Techniques

         
  T      
        E
    H    
R        

Saturday, April 22 was "Earth Day" and this was the puzzle of the day in our Mensa Puzzle Calendar.  Writing a program to solve it took a few hours on a rainy Sunday.

Users may enter characters to solve the puzzle on their own, however only ""guided" mode is available for now.  Attempts to place an invalid character or to place a valid character it wrong cell will be rejected with a "beep".   There is a "Solve it"  button to trigger a solution search by the program which should succeed in a second or two.

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:

My initial strategy for implementing a solution search in puzzle solver typically requires significant revision.  Surprisingly, the initial data structure worked this time.   l decided to preplaced the given letters and create a string (Letters) of the remaining 21 to pllace.  I used an interlaced version (AEARTHEARTHEARTHEARTH)  of the letters and processed it from left to right using a recursive AddLetter function passing it the next letter to place and a "Level" parameter indicating the ordinal value of the letter being placed.

For speed and ease of processing, I create an internal array of characters (Grid) representing the displayed StringGrid1.   For each call, if Level is beyond the end of the Letters string, we have found a solution, so copy Grid values to the StringGrid1 and display a "Solved!" message. If Level still points to a letter to place, we process all Grid cells looking for one that is empty, doesn't match a letter already placed in this row or column (UniqueInColAndRow function), and has no match in either diagonal (UniqueInDiagonals function).  If location is valid, we'll insert the character, and call AddLetter with the next letter in the string and the next Level value.  If the returned  Result from the call is False, this letter is in the wrong place so we'll remove it from the Grid and continue searching.    If the Result is True, we just exit passing True value back to the guy who called us. 

When Addletter Result gets passed back to the SolveBtnCllick routine that started the search, we're done. A False result here would produce a "No solution found" message.

Running/Exploring the Program 

Suggestions for Further Explorations

It seems that the letter "A" could be left out of the search letter string.  Result should be a completed grid with 5 empty cells where the fA's should go. 
.How would run time be affected if we placed all copies of a single letter value first?
The program currently solves the puzzle silently at startup time and saves the result in a "Solution" grid for checking user play entries.  Alternatively, we could do validity checking by row, column, and diagonal for each character entered in the same way as the program search does it.  This would make it considerably more difficult  for users to solve the puzzle manually.
 
   
   

 

Original:  April 23, 2017

Modified:  April 24, 2017

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