Polyhex Puzzle-a-Day
“How do you solve the date/calendar puzzle in your lobby?” — Zach, age 46
Last summer, someone asked how we know there is a solution to each date for the calendar puzzle donated to SUMM by our friends at MathHappens. The idea is to position the 8 tiles so that only the current month and date are revealed. The puzzle below has been solved for January 18th.
Photo: MathHappens
I didn’t see a cute analytic way to find solutions, so I wrote a program to brute force every possible solution and looked at some statistics. Each date indeed had a solution, but it turned out some dates had far more solutions than others. January 25th clocked in with the most solutions, a whopping 216, while October clocked in with the fewest solutions, a meager 7.
Steven Stadnicki’s Polyhex Puzzle
Since then, SUMM Advisory Board member Steven Stadnicki has given his own spin on the puzzle-a-day calendar format. The basic premise is the same: the pieces have to be arranged in the frame so that the only two spaces remaining uncovered are the current month and day. However, Steven has made his pieces polyhexes (tiles made from regular hexagons joined edge-to-edge) instead of polyominoes (tiles made from squares joined edge-to-edge) and engineered his frame accordingly.
If you’ve been to our Kent Station location, this puzzle is typically out on the tables by the entrance, so I suspect it’s the one Zach is asking about.
While I typically solve the MathHappens puzzle in about 10 minutes or so, I often find myself working on Steven’s puzzle for 20-30 minutes before finding a solution — if I find one at all! I have my suspicions that Steven’s is the harder of the two puzzles, but how could we make that assessment more precise?
Try these puzzles
Before I spoil some elements of strategy and the solution for July 14, you might want to give the puzzle a try! You can try these virtual versions I’ve made in Polypad:
If you haven’t used Polypad before, you can drag and rotate pieces with your mouse. When you click a piece, an interface will come up giving you the option to flip a piece. It also lets you cut them, but that’s not in the spirit of the puzzle — we’re on the honor system here!
Some Data
As with MathHappens’ puzzle, I didn’t see an analytic approach to solving Steven’s puzzle or proving each date has a solution, so I started by tweaking my program to work with his hex grid. After deciding how to store the grid and pieces (I pretty quickly settled on thinking of the hexagon as part of a rhombus that could be stored as a standard rectangular array), I got it working and was able to brute force all solutions.
If we look at all 366 legal dates (including February 29th), the average (mean) number of daily solutions for MathHappens’ puzzle is 66.7 while it’s 42.8 for Steven’s.
Here’s the solution breakdown by month:
And here it is by day:
For the most part, purple stays higher than green, indicating there are typically more solutions to the MathHappens puzzle than Steven’s, so perhaps they’re easier to find. I first played with the puzzle in late February, after our Kent Station exhibit space’s soft open. It looks like the number of solutions to Steven’s puzzle is pretty low throughout that period, often having about 1/3 as many solutions as the MathHappens puzzle, tending to hover under 25:
Perhaps I’d have had an easier time if I’d waited until May to play with it, when the number of solutions were often double or triple that!
Getting started
I think these statistics are interesting, since whether there are more or fewer solutions tells us something about the likelihood of randomly stumbling upon one. Do we ever really solve puzzles randomly, though? It might feel like it sometimes, since there is a lot of trial and error in solving a puzzle like these, but we often have strategies we build around.
One of my strategies for MathHappens’ puzzle is to try to box in the month and day first, building around those. For instance, on July 14 we need to cover JAN in a way that leaves JUL uncovered. I count 10 ways to do that:
It turns out there are 48 solutions to July 14, and they can start with all of these except for one! Here are sample solutions based on 9 of the above 10 starting moves:
So even though my instinctual first move would have been to guess, there was a 90% chance that I could work from that guess toward a solution. In fact, that light green U-pentomino boxing in JUL occurs in 24 of the 48 solutions, and that was my (lucky) first choice!
If I were trying to solve Steven’s puzzle, my instinct would similarly be to start by covering MAR in a way that leaves JUL uncovered. While JAN had only one non-JUL neighbor in the previous puzzle, MAR has two non-JUL neighbors in this puzzle, leaving more wiggle room for pieces to snake.
There are a couple ways to start off that we can rule out:
Nine ways to start this that we wouldn’t immediately rule out do indeed lead to solutions:
However, five plausible ways to start don’t lead to a solution:
There are 68 solutions to July 14. While that’s more than the 48 solutions to the MathHappens puzzle, my particular strategy has a higher chance of a false start. While I likely would have started by boxing in JUL with the yellow U-tetrahex, which can lead to a solution, it only leads to 5 of the possible 68 unlike the green U-pentomino leading to 24 of the 48 solutions to the MathHappens puzzle.
So, while it seems there are more solutions for July 14 to stumble upon in Steven’s puzzle, perhaps my particular instinct for getting started doesn’t give me the same edge it did with MathHappens’ puzzle.
Ruling out bad regions
I asked Steven if he had any insights for solving his puzzle. He noted that he also wrote a brute force algorithm to verify every date has solutions, but one thing he stumbled upon that sped his algorithm up was to look at the number of hexagons in each empty region.
When I ruled out those two starting maneuvers for July 14, for example, it was based on the fact that they left islands of 1 or 2 hexagons that needed to be filled. Since there are no pieces with just 1 or 2 hexagons, however, we know a solution also wouldn’t be in the cards. Similarly an island of 3 hexagons can’t be filled. Since all pieces have 4 or 5 hexagons, empty regions of those those sizes can be ok, depending on their shapes.
There is no way to put 4-hex and 5-hex pieces together to fill a 6-hex region, so any partial solution with an unfilled 6-hex island also can’t lead to a full solution. If a number cannot be written as a sum of 4’s and 5’s, a region of that size is bad, regardless of its shape. Finding such numbers (in particular, the biggest such number) and related problems are usually referred to as Frobenius coin problems, a popular example of which is framed in terms of McNugget numbers and non-McNugget numbers.
In this case, Steven notes that regions with 1, 2, 3, 6, 7, or 11 hexagons are bad, regardless of their shapes. So if you are solving his puzzle and find yourself leaving an uncovered region of one of those sizes, you’ve made a misstep!
