Acrostic Variation

[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

This program implements a solver for the above puzzle.

Background & Techniques

An  "Acrostic" is a puzzle device whose solution reveals the answer to another question.   This fill-in puzzle reveals a 13th unspecified form of transport in the grayed areas when the puzzle is completed.  I'm sure it can be solved with pencil and paper and either a good eraser or lots of blank puzzle templates.   The computer can solve it the same way but way faster.  In many years of Mensa puzzling, this the first of this type I recall so I haven't generalized the program, but it won't be difficult to do so if a second example shows up.   There is a print button provided in case you want to work on it the old fashioned way.  

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:

The problem was modeled by introducing "Intersection Rule"; records for each pair of words which cross each other.  Word positions are numbered H1 through H6 and V1 through V6 from left to right and  top to bottom.  So H1(2),V1(2) indicates that horizontal word H1 and vertical word  V1 intersect at the 2nd letter of each word.  The program attaches a string list of "Candidate" word pairs which could fill the requirements of the rule. 

A TRulerec record is defined which breaks the text of each rule into individual fields and adds a Candidates string list to hold pairs of words which have matching letters in the specified intersection positions.  The SearchBtn click procedure first builds a Rules array of TRuleRec based on the displayed intersection rules and builds the Candidate list for each rule.  Once this Rules array is built, we then call function  CheckCandidates for each rule to recursively process the candidate word pairs.  AssignedList is a Name=Value type of string list with "Word=Assigned location" for all words with a indication of which word position has been assigned that word with a special indicator (the letter "N") is set if the word is available.   CheckCandidates processes the Candidates list looking for a pair of available words that it can assign.  If it finds a pair, it assigns them and calls itself with the next rule number.  If no candidates can be assigned for the current rule, the function returns "False" to the caller (the previous rule) which then un-assigns its latest assignments and tries the next candidate pair, etc.  The process continues until all rules have been satisfied and we have a solution or all rules have exhausted all of their candidates in which case no solution exists.  This is a classic "depth-first search with recursion" which still seems like magic to me when it works!  

Other program features worth mentioning:

  • Use of the Print Dialog to and the TForm.Print method as a simple way to allow the user to print the puzzle.
  • Use of TPageControl with  TTabsheet pages to place the puzzle description and the program solving options on separate pages.
  • Use of  the TPageControl OnChange event exit to enhance the tab display characteristics for the currently active page, a big deficiency of the default tab displays.  I chose to set the Highlighted and BorderWidth properties for for the new active page after resetting those properties for all other tabs.    
  • A destructive GetWord function provides a simple way to retrieve text words parsing the Rules and AssignedList entries.  I call it "destructive" because each call  returns the next word and removes that word and its delimiter from the input string.  This makes it easy for the caller to retrieve all words from a string without keeping track of where the next word resides; it is always the first word of the string!      

I added a feature to sort the Rules array before solving in an attempt to reduce search path length.  Initial order is by Horizontal word number but I added options to sort by increasing Candidates word list length (runs much faster) or by descending number of intersections for the horizontal word (moderately faster).  The idea for the Candidates list size sort was that fewer candidates will get the proper words placed quicker and it appear that it does.  For the descending number of intersections the idea was to get words with most intersections placed first, but there appears to be more to it.    Whether there are better ways to preselect the rules order for efficiency remains an open question.   Processing the rules with words intersecting the last words placed might be more "human-like" and be even more efficient.  

In any event, it has been a satisfying 10 days of coding and problem solving.    

    

Running/Exploring the Program 

Suggestions for Further Explorations

Fill the grid with solution words
.Allow user selection of words for interactive solving
Explore alternative ways to reduce search time for solving.
   
Original:  June 28, 2015

Modified:  February 18, 2016

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