From New Scientist #1225, 30th October 1980 [link] [link]
There are a lot of quadrilaterals in the figure; 492 in fact, I reckon. I do not count “crossed” quadrilaterals, like ABCD; only simple ones, like ABED, ABFD, and so on.
Now imagine the figure composed of 63 matches. My question is: what is the smallest number of matches you need to remove so as to spoil all 492 quadrilaterals? A quadrilateral is spoilt, of course, when one or more matches is missing from its boundary.
Interestingly, on the same page of New Scientist that this puzzle was originally published there is a review of the “sick, brutal and depraved” game – Missile Command.
[enigma82]
I found this a challenging problem to solve programatically, so I’ve added it to the list of Notable Enigmas.
My programmatic solution consists of two parts. The first identifies all the simple quadrilaterals in the array, and associates them with the set of matchsticks that make up the perimeter of each quad. It’s not particularly elegant, but I wanted to make sure it found the right set of quads (and it turns out this isn’t the time consuming part of the program).
The second part of the program involves finding a minimum set of matchsticks such that every quad is “spoit” by the removal of those matchsticks. This is a problem known as the Minimum Hitting Set problem, and is NP-hard, which means there is no easy shortcut to finding a solution.
I have used a simple recursive depth-first-search to find one of the minimum hitting sets. The only optimisation it uses is that it skips sets that are not smaller than the smallest it has already found. This is OK for a 5×5 array – it finds the solution in just under 4 minutes, but for the 6×6 array it takes a lot longer. I left it running overnight and it hadn’t even found a minimum solution.
However I wrote an augmented version of the algorithm, that represents the inclusion matrix of the quads and the matchsticks (matchsticks are columns and quads are rows) using bit vectors. This is coupled with the observations that any column that is a subset of another column can be removed and any row that is a superset of another row can be removed to reduce the problem at each step. This yields a solution to the 5×5 array in 30 seconds, but took nearly 22 hours to run to completion on the the 6×6 array (although it finds the solution much faster than that).
Solution: The smallest number of matches that can be removed to spoil all quadrilaterals is 20.
Here is a diagram of one possible arrangement of the 20 matches (or, rather, the arrangement of the remaining 43 matches).
Note: The solution originally published with Enigma 85 gives an answer of 21 matches, but as can be seen above this can be improved upon. A corrected solution to this problem was published with Enigma 144 (although the diagram still shows 21 matches removed) and in the 1982 book Enigmas by Robert Eastaway (with a correct diagram).
The number of quadrilaterals in the n×n triangular arrangement of matchsticks is given by:
(see sequence A204185 in OEIS).
The number of matches that need to be removed to spoil all such quadrilaterals appears to be following sequence A000096 in OEIS, which has a general term of:
(which is a lot quicker to calculate than solving the Minimum Hitting Set problem).
The number of matchsticks in the arrangement with side n is 3n(n + 1)/2, three times the nth triangular number. No great surprise, as each right-way-up unit triangle has three sides, and the upside-down unit triangles contribute no additional matches.
The number of the latter is the (n – 1)th triangular number, n(n – 1)/2,
so the total number of unit triangles is n².
The number of triangles of all sizes (including the large bounding triangle) is
[n(n + 2)(2n + 1) – n mod 2]/8, or int[n(n + 2)(2n + 1)] if you prefer.
I modified my code that determines the quads to produce a data file for a simple GLPK model to find a Minimum Hitting Set, and glpsol solves the 6×6 case in 32.6s, so I might look at some of the Python/GLPK linkages to get a fully automated solution.
In the meantime here’s my GLPK model, and the data for the 2×2 case.
I installed PyMathProg, and once you’ve made a list of the quadrilaterals you can use this code to solve the Minimum Hitting Set problem over it. For the 6×6 case it runs in 52s, which is slower than using GLPK directly, but you do get the list of edges out of it in a more useful format.
Running this GLPK model over the 7×7 case does indeed give a Minimum Hitting Set of size 27 (as predicted by A000096). glpsol ran for 3h57m, and found this solution.
As a precusor to using the fast Gurobi LP solver for this problem, I coded it for GLPK as follows. This requires my interface to GLPK which I make available here: http://cgi.gladman.plus.com/wp/glpk.py
I have also coded this for the Gurobi solver and verified the values of 35 and 44 for 8 and 9 rows.
The LP tools I used to solve this puzzle 10 years ago have all succumbed to bit-rot and no longer work on my machine. But I tend to find myself using MiniZinc now when I want to make a declarative model to solve a puzzle, so here is the Minimum Hitting Set problem using MiniZinc (via my minizinc.py library).
I put the following code in the file utils_mzn.py:
And I wrote neater code to generate the quadrilaterals.
So here is a complete program to solve the puzzle using MiniZinc.
I found the
highs
solver performed well (although it will only produce single answers, but in this case we only need one example of a minimum hitting set). For the size 6 grid it finds a solution in 3.8 seconds, and is able to run the size 7 grid in 23 seconds, the size 8 grid in 3 minutes, and the size 9 grid in 40 minutes.The
scip
solver performs better though. For the size 6 grid it finds a solution in 2.3 seconds, the size 7 grid takes 17.9 seconds, the size 8 grid takes 1 minute 39 seconds, the size 9 grid takes 11 minutes, and the size 10 grid takes 6 hours, 37 minutes.Solution: The smallest number of matches that can be removed to spoil all quadrilaterals is 20.