Matchstick 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

"Burn" the match sticks to get the specified total number of burned segments in each column and row.

Background & Techniques

We're back to the Mensa Calendar this year and it didn't take long to recognize the quality over last year's
from another company. This puzzle deserved a program just to help solve it manually. A future version
may add program search for the solution and additional randomly generated puzzles.

The January 2nd puzzle has these instructions: "The grid contains matches of different sizes, any of which can be completely unburned, or completely burnt,  Matches burn from the head (rounded end) to the tail, without skipping segments. The numbers outside the grid indicate the number of burnt segments in the corresponding row or column.  Can you shade the in the burnt segments to :match" the numbers?

 

 

For my program version, click an unburned stick to "burn" all segments from the click point through the match head. Clicking a burnt segment will restore it to unburned state along with all segments from there through the tail segment. The inner column and upper row of numbers show current burnt segment row and column counts and the outer/lower numbers are the target sums.  When all burnt sums match target values, you are a winner! Enjoy.

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:

Defining the puzzle:

Step 1 of most projects is defining data structures to model the puzzle.   In this case I defined two record types.  TMatchStick specifies the column and row of the match head, the number of segments (grid cells) occupied my this match, and the direction from the head to the tail  (L,R,U,D) for left, Right, Up, and Down.  An array of these records, Matchsticks, contains an entry for each match.    Two additional arrays, ColSums and RowSums hold the target number of burnt segment sums in each direction.     A LoadDefault  procedure is called initially to fill the arrays with data constants embedded in the program. 

The second record type. TMatchsegs, defines the match segments  in a two dimensional array corresponding to the the display grid.  The MatchSticks array data provides the data to Create a TMatchSegs record for each segment of each match.  Each record contains the TDir direction value, and 3 Boolean (True/False) fields: Burned is true if this segment has been burned, HeadSeg and LastSeg identify the first and last segment of this match.

Drawing the Matchsticks

I decided to draw the matches on  the Canvas of a TImage control.  There turned out to be more to that than I initially thought. The Ellipse method draws the match head  with the major axis a few pixels wider than the minor axis.  Of course the orientation of the major axis depends on the orientation of the match.  We then need to draw two parallel lines for the portion of the match stick between the match head and the edge of the cell.  The interior segments are drawn as parallel lines for the full width  or height of each cell.  The final segment has the edges lines shortened and and another closing line across the end.  All lines are drawn using Moveto and Lineto methods of  the canvas.  I use the Floodfill method to color the segments as burned or unburned so it was important to have the cell boundaries remain visible to mark the segment ends. That also meant erasing a little piece of the match head where it meets the stick so that Floodfill could fill both parts.    If I were starting over, I would try drawing entire matches first and then drawing the grid lines over them to demark the segments.

Processing User Clicks

Actions taken when the user clicks a cell depend on whether the segment is burned.  If not burned, I use Floodfill to "burn" all the segments back to the match head (Headseg = True) using a shade of brown.  If  Burned, I "unburn" all segments between the current cell and the LastSeg of the match using a white brush color.   A TImage OnMouseUp event exit gives us the X and Y mouse coordinates in pixels relative to the top left corner of the grid.  Dividing the X and Y values by the Cellsize variable calculated initially gives  Column and Row coordinates for indexing into the MatchSegs array.   This gives us the Burned status of that cell.  From there, the actual incrementing/decrementing of Column or Row depends on match direction and whether burning or un-burning the match.  It took a few hours to get all of that working correctly.     

Scoring

After each change of a match, I recount all of the burned segments by row and column.  I made the ColSums and Rowsums arrays to contain TPoint record types.  X values of each entry hold the current column or row sum of burned matches  and the Y values hold the target values. The initial image gets extended by 2 cells in each direction when the puzzle is loaded and there cells hold the current and target sums.  Current sum text is colored Gray when less than the target, Green if equal, and Red if too high.  I considered making the current counts displays optional only offering them after some number of user clicks but haven't done so yet.  Having that display is very helpful in arriving at the solution.

Other possible future enhancements include additional puzzles, perhaps generated by the program, and making the program smart enough to find solutions on its own. 

About 400 lines of code probably put this in the advanced Intermediate difficulty level.  No really hard-to-solve problems, but lots of code to solve them.     

Addendum January 15, 2013: It only took 1 day for a viewer to find a scaling problem with the program.  I happen to have a high resolution screen on my laptop (1920x1200) which can cause scaling problems on lower resolution screens, particularly for program, such as this one, with graphics drawn by the program.   A reposting today  works well down to 1024x768 resolution and should be usable down to 800x600.  

   

Running/Exploring the Program 

bulletDownload  executable
bulletDownload source  (Note: the program uses units residing in our library zip file of commonly used units.  Library file DFFVLIB13 or later is required to recompile. program )
bulletDownload current library file (DFFLibV15)

Suggestions for Further Explorations

Make user burned counts optional
Implement programmed solution search feature
Generate additional random puzzles, preferably with unique solutions 
   

 

Original:  January 11, 2014

Modified:  February 18, 2016

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