How Many Squares?

[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

There are 30 squares of all sizes in a 4x4 grid of 40 matchsticks. "What is the minimum number of matchsticks that need to be removed  to leave no squares of any size?"

Background & Techniques

Here's an investigation from the latest addition to my library of math & puzzle books: Challenging Math Problems, Terry Stickels, Dover Publications, 2015, 

Problem #12 in the book shows 24 matchsticks formed into a 3x3 grid and asks about the fewest sticks that can be removed to eliminate all complete squares of any size. Actually one solution is given and the real question is   "What is the minimum number of matchsticks that need to be removed  to leave no squares of any size?".  This program will not tell you directly, but will let you play around by adding and removing sticks from the grid with feedback at each step about the number of squares remaining.

As regular viewers know, mathematics is among my interests thus I decided to look into the properties of integer sequences formed by increasing grid sizes. An excellent resource for this is the Online Encyclopedia of Integer Sequences. I tracked Number of matchsticks, Number of squares of all sizes, and Minimum
# of matchsticks removed for a zero square solution
. It's easy to get values for 1x1, 2x2, and 3x3 grids and the program will provide values for the Matchstick and Square counts for larger sizes. Surprisingly, all three sequences exist and have names in the OEIS library. A search on the first few terms will find them with an large amount of additional detail.

Check it out and have fun!


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:

There were several interesting problems to solve in coding this program:

  • Data Structure was tough design because most of the referencing is the edges of the grid but most of them share a vertex one, two or three other "matchsticks".  I ended up with an array (Vertices) of TVertext records  representing top left corner of a cell.  Each TVertext record contains two TEdge records, labeled  H for horizontal and V for vertical direction.  Each TEdge record has a TLine record with the start and end coordinates of the matchstick, a direction field (East or South), and a Boolean Exists flag to tell whether the stick is present.   The rightmost H record and the bottommost V record have direction set to Unknown to prevent checking nonexistent edges. 
  • Detecting matchstick clicks uses the  MouseDown event exit  which scans all edges using the NearestEdge function to return the intended edge.  A simple Exists:= not Exists; statement then reverses the edge state and a call to DrawEdge redisplays it.
  • Drawing matchsticks instead of just red or gray lines was a late addition and required  lots of time to get the scaling even close to correct over multiple  grid sizes.   A Cellsize value is calculated based on image size and specified number of grid rows and columns.  The length of each matchstick is based on Cellsize value, allowing a little space at each end of the stick.  Matchstick width (MsW, match head width (MhW,) and match head length (MhL) are all trial and error values based on cell size.  Each match is drawn as a red ellipse for the head and a rectangle for the stick, overlapping the head slightly. 
  • Counting and reporting matchsticks removed  is trivial; check edges in all vertices and count those with Exists=False.  Counting all remaining squares was not so simple.  A IsSquare function checks the perimeter of each passed top left vertex and size from current column and row to the right and bottom edges If any is missing a matchstick, that combination is not a square.   
  • For Version 2, it took a while to figure out the best way to view remaining squares in larger grids.  Highlighting matchstick was not useful for large grids (with small matchsticks).  Solution was to use the TCanvas Copyrect method to save the grid image to a bitmap before highlighting a square whith a solde rectangle and then restoring from the bitmap after a 1.5 second delay.
  • Save and Restore were implemented as dialog units which save and restore grid configurations in configuration  file HowManySquares.ini.   Grid names are used as Section names, Two digit strings contain vertex column and row as Key names, and two character Value strings:  __, H_,  _V, and  HV.  to identify presence or absence of matchsticks from that corner.  It works fine and saves creating a file for each grid saved.              

January 28, 2016:  It did not take long to recognize the need for for the first two enhancement suggestions.  Version 2.0 adds the ability to view remaining squares after each move or on request. Also grids can now be saved and restored in configuration file "HowManySquares.ini" Both features are helpful when working on larger grids.

Incidentally, I didn't get to documented it within the program, but the optimal solution for an N x N grid  removes  N*(N+1)/2  matchsticks.

Running/Exploring the Program 

Suggestions for Further Explorations

      Implemented Jan 28,2016:  Add ability to show remaining squares.  Count of squares is currently displayed but finding them is not always easy. 
Implemented Jan 28,2016: Add ability to save and restore grid configurations.
Check non-square grids.  The capability exists but has not yet tested.

 

Original:  January 19, 2016

Modified:  February 18, 2016

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