Jim Blackler

I saw this puzzle for sale visiting a local exhibition.

It’s a clever variation on the type of puzzle where you have to slot pieces of various shapes together to occupy an empty grid. This one has all the month names and the numbers 1 to 31 marked onto the game grid. The aim is to place the pieces to cover every grid square apart from the ones that indicate a selected date. That way there’s a fresh challenge for every day of the year.

I wondered how the designers of this clever puzzle had made sure that it was indeed possible to solve the puzzle for every day of the year. I guessed that a computer had been used to check this fact, and wondered how such a checker would be written.

So, for fun, I completed this task myself. I’ve made a solver written in TypeScript to run on a node.js compatible platform, such as Google App Engine.

Here’s how I wrote the program, and what I found.

I typed in the grid layout, and the puzzle piece layout, as two-dimensional arrays of ones and zeroes.

The program begins by marking out the grid to find solutions for the chosen date; blocking out the date squares that will need to be left uncovered.

To account for the fact that each piece can be rotated into one of four positions, and also flipped into another four, the program begins by calculating all the unique forms each shape can take.

Then the puzzle solving begins. The algorithm simply attempts to place every shape (in one of its valid rotation/flip variations) until the grid is full. Each step involves identifying the first empty cell when cells are ordered top-to-bottom, then left-to-right. Then, considering each variation of each unplaced piece in turn, it sees if it can be slotted with the first cell of the piece (ordered top to bottom, left to right) occupying that slot. If it can, it uses recursion to begin a new search considering the grid, and remaining pieces, as they are now. Whenever no pieces remain, the board state is added to the list of known valid solutions.

It could be described as a brute-force search, but as the grid is fairly small, it completes quickly enough to be practical.

I added a simple grid visualizer to show each solution, and selectors to allow the solutions of any date to be shown.

One thing that surprised me was how many solutions existed. It’s typical for the solver to find 100+ different solutions for any date. November 5th has 178 solutions. Although some, like October 6th, have just seven solutions. Nonetheless it made me think that computer verification might not have been needed. An experienced puzzler could find at least a single solution for each date.

You can find the program online at https://solve-annual.appspot.com/ and the source, licensed as free software, is on GitHub at https://github.com/jimblackler/solve-annual.