The Gurobi Solver
Gurobi offer a high performance solver with Linear Programming capabilities and a nice Python interface here. This page contains a number of examples of how it can be used to solve some of the puzzles published by the Sunday Times and the New Scientist in the UK.
Example 1 – Love Hearts
This puzzle was published in the Sunday Times in 2004 and is notable because the answer given was incorrect. The puzzle is repeated here for convenience:
Sunday Times Teaser Number 2161 – Love Hearts
by Hugh Bradley and Christopher Higgens
Bobby has made a Valentine card for his girlfriend Chin-We. He drew rows of identical touching circles in a triangular formation as shown below but with more rows.
He then placed a red heart in as many circles as possible without any of these forming equilateral triangles. He continued by placing pink hearts in some of the other circles and white circles in the remainder.
When he counted the number of hearts of different colours (in no particular order) he obtained three consecutive integers.
How many red hearts are on the card?
The following program solves this problem for n rows. It creates a binary variable for each circle and then seeks to maximise the number of such circles included subject to constraints that prevent the included circles forming any equilateral triangles.
The performance of the Gurobi solver allows us to find the maximum number of red hearts we can add without forming equilateral triangles for up to 14 rows.
The ‘consecutive integer’ condition on the three colours of hearts limits which of these solutions solves the teaser and gives the answer as 22 red hearts. The ‘official’ answer given by the Sunday Times was 16!
Example 2 – Quad Spoiling
New Scientist Enigma Number 82 – Quad Spoiling
by Stephen Ainley
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.
Here is a solution using the Python interface to the Gurobi solver. It creates a binary variable for each individual match, enumerates every quadrilateral and establishes a list of the matches on the boundary of each of them. The aim is to minimise the number variables that are true (missing matches) whilst ensuring that the sum of the variables for each quadrilateral is greater than zero (every quadrilateral has at least one missing match). This type of problem is often referred to as a Minimum Hitting Sum.
Here are the results for varying numbers of rows, the answer to the enigma itself being that 20 matches need to be removed.
Jim Randell poostulates here that the number of matches needed to spoil all quadrilaterals follows A000096 at the The On-Line Encyclopedia of Integer Sequences (OEIS).