About a month ago I was watching a YouTube video where YouTuber Drew Gooden was struggling with a “weird” puzzle:

This is what the puzzle looks like:

It has 10 pieces that can be flipped/rotated and placed on a calendar. They claim there is a solution for each day/month/weekday combination. In the YouTube video Drew is struggling and says:

The problem is, I’ll never be able to prove that

But… what if we can?

As a programmer this sounds like a perfect little puzzle to solve.

Solving the puzzle

To solve this, I first encoded all the puzzle pieces, this is relatively easy to do because it’s just a 2D grid.

Next I wrote the code to generate all the possible rotations of a certain puzzle piece (and eliminated duplicates). Some pieces have more rotations than others because some are the same after a 180 degree rotation, others are not.

Next I blocked the target puzzle solutions on the board, for example “2nd June Monday”, placing three markers.

After that I just go through all possible piece/location combinations, placing the first puzzle piece in the top position and continuing down.

This was fast enough to solve the first puzzle after a couple of minutes.

But… not fast enough to generate all: 12 (months) x 31 (days) x 7 (weekdays) = 2.604 solutions

Example output: The image above has a solution for Thursday 8th of April. The code outputs this as:

Solution for: 8/4 [5]:
0 0 0 X 1 1 X 
2 2 0 0 4 1 X 
2 2 3 3 4 1 1 
X 2 3 4 4 5 5 
7 6 3 3 5 5 9 
7 6 6 6 6 8 9 
7 7 7 8 8 8 9 
X X X X X 8 9 

Each number 0-9 stands for a certain puzzle piece. The X’s are blocked off (solution and edge).

Improve solving speed

To improve the speed of the solver I decided to do a small flood fill after placing each puzzle piece. If we’ve created a spot where there are just 4 places left (a small island) I stopped looking further, because no puzzle piece will ever fill this spot.

This small algorithmic improvement was enough to make it fast enough to generate a puzzle solution for every single combination.

Links

Solutions: If you’re just looking for all the solutions: solutions.txt.

Code: If you want to take a look at the (Java) code, check out PuzzleADaySolver.java.