The Calendar Puzzle

The Calendar Puzzle is the physical puzzle of fitting eight pieces around a date. A $7 \times 7$ wooden board is laid out with the twelve months on its top two rows, the days $1$ through $31$ on its lower five rows, and six permanently blocked cells at the corners. Every morning, the user chooses a month and a day, sets those two cells aside, and tiles the remaining $41$ cells with eight polyominoes (seven pentominoes and one hexomino) to leave only the chosen month and day showing. The puzzle ships under the brand name A-Puzzle-A-Day; other calendar puzzles with minor variations (pentomino sets, day arrangements) are sold under DragonFjord and Calendarium. Our target is the original $7 \times 7$ layout.

The puzzle is simple to describe and striking to solve. Every one of the $366$ possible (month, day) combinations is solvable: an exhaustive run of the model in this chapter finds at least one tiling for each date (indeed for all $12 \times 31 = 372$ month-day cells, including the six that are not real dates). What varies widely is the number of solutions per date: some dates have dozens of tilings, others only one or two, with the boundary dates the most tightly constrained. The puzzle rewards both manual search (useful when solving once a day, by hand, with the physical pieces) and constraint programming (useful for auditing the board, counting solutions per date, or generating a printable picture).

Among the puzzles in this volume, the Calendar Puzzle is the cleanest example of an exact cover problem in disguise. The board is a fixed region, two cells are subtracted per day, and the eight polyominoes must cover the remaining cells exactly. No numeric clues, no adjacency rules, no colour constraints: only the geometry of the pieces and the geometry of the board. This makes the CP-SAT encoding extremely compact and the solver extremely fast.

The board and the pieces

The physical board is a $7 \times 7$ array of cells, of which six positions are permanently blocked: cells $(0, 6)$ and $(1, 6)$ on the top two rows (which carry the twelve months) and cells $(6, 3)$ through $(6, 6)$ on the bottom row (which carries days $29$, $30$, $31$ and then tails off). The remaining $43$ cells carry labels: the twelve months $\{$Jan, …, Dec$\}$ and the thirty-one days $\{1, \ldots, 31\}$. A date is chosen by designating one month cell and one day cell as the “reveal”, leaving $41$ cells to be covered.

The eight pieces are seven pentominoes (five cells each) and one hexomino (six cells), totalling $7 \cdot 5 + 6 = 41$ cells. This is exactly the number of cells to cover, no cells to spare. Each piece may be rotated by $0^\circ$, $90^\circ$, $180^\circ$, $270^\circ$ and reflected (flipped over), giving up to eight orientations per piece; some pieces with internal symmetry have fewer distinct orientations.

Figure 2.1 is the Calendar Puzzle for 24 April, and Figure 2.2 shows a valid tiling.

The programming model

The exact-cover formulation is direct. For each piece $P_i$ ($i = 1, 2, \ldots, 8$), enumerate all orientations (rotations and reflections) and, for each orientation, all translations that fit inside the $7 \times 7$ board. Each (piece, orientation, translation) triple defines a placement: a set of cells on the board that the piece would cover if the solver selects it.

Placement variables

For each placement $p$ associated with piece $P_i$, introduce a Boolean variable $x_p \in \{0, 1\}$ with $x_p = 1$ meaning “this placement of piece $P_i$ is selected.”

One placement per piece

For every piece $P_i$, exactly one of its placements is selected: $$\sum_{p \,:\, \text{placement of } P_i} x_p \;=\; 1.$$

Exact cover per cell

For every cell $(r, c)$ of the board with $(r, c)$ in the set of cells to be covered (i.e. not blocked and not equal to the chosen month or day), exactly one placement covers it: $$\sum_{p \,:\, (r, c) \in \text{cells}(p)} x_p \;=\; 1.$$ For every cell that must not be covered (the chosen month, the chosen day, and the six blocked positions), the same sum is required to be zero: $$\sum_{p \,:\, (r, c) \in \text{cells}(p)} x_p \;=\; 0.$$

The two families can be unified as a single constraint $$\sum_{p} x_p \cdot \mathbb{1}\bigl[(r, c) \in \text{cells}(p)\bigr] \;=\; B_{r, c},$$ where $B_{r, c}$ is $1$ for a must-cover cell and $0$ otherwise.

A solver in sixty lines

import numpy as np
from ortools.sat.python import cp_model

PIECES = [
    [(0,0),(0,1),(0,2),(1,2),(0,3)],
    [(0,0),(0,1),(0,2),(1,2),(2,2)],
    [(0,0),(0,1),(1,0),(2,0),(2,1)],
    [(0,2),(1,0),(1,1),(1,2),(2,0)],
    [(0,0),(1,0),(2,0),(0,1),(1,1),(2,1)],  # hexomino
    [(0,0),(1,0),(2,0),(2,1),(3,1)],
    [(0,0),(0,1),(0,2),(0,3),(1,0)],
    [(0,1),(1,0),(1,1),(2,0),(2,1)],
]

def rotations(p):
    out = [p]
    for _ in range(3):
        q = [(c, -r) for r, c in out[-1]]
        mr = min(r for r, _ in q)
        mc = min(c for _, c in q)
        out.append([(r - mr, c - mc) for r, c in q])
    return out

def reflections(p):
    mir = [(r, -c) for r, c in p]
    mc = min(c for _, c in mir)
    return [(r, c - mc) for r, c in mir]

def placements(piece, H=7, W=7):
    """All placements fitting the board."""
    seen, out = set(), []
    orients = (rotations(piece)
               + [reflections(r)
                  for r in rotations(piece)])
    for o in orients:
        for dr in range(H):
            for dc in range(W):
                pl = [(r + dr, c + dc) for r, c in o]
                if any(r >= H or c >= W for r, c in pl):
                    continue
                k = frozenset(pl)
                if k in seen: continue
                seen.add(k); out.append(pl)
    return out

BLOCKED = ((0, 6), (1, 6),
           (6, 3), (6, 4), (6, 5), (6, 6))

def solve_calendar(month_cell, day_cell):
    m = cp_model.CpModel()
    B = np.ones((7, 7), dtype=int)
    for r, c in BLOCKED:
        B[r, c] = 0
    B[month_cell] = 0
    B[day_cell] = 0
    all_pl, pv = [], []
    for piece in PIECES:
        pc = []
        for pl in placements(piece):
            v = m.NewBoolVar("")
            pc.append((v, pl))
            all_pl.append((v, pl))
        m.Add(sum(v for v, _ in pc) == 1)
        pv.append(pc)
    for r in range(7):
        for c in range(7):
            cov = [v for v, pl in all_pl
                     if (r, c) in pl]
            m.Add(sum(cov) == int(B[r, c]))
    s = cp_model.CpSolver()
    s.Solve(m)
    return [(pl, i)
            for i, pc in enumerate(pv)
            for v, pl in pc if s.Value(v)]

Each date solves in about $90$ milliseconds on a standard laptop. A nightly batch that emits the solution for every one of the $366$ possible dates completes in under a minute.

A hard instance: 29 February

The leap-day date 29 February is interesting because it brings together two boundary cells: February in the top row and the $29$ cell in the bottom-left corner of the day block, diagonally far apart. Both cells are near the board’s geometric extremes, which constrains the tiling more than an interior choice would.

Sources. A-Puzzle-A-Day is a commercial wooden puzzle sold by DragonFjord Puzzles and several independent manufacturers, with $7 \times 7$ variants dating from approximately $2018$. The puzzle reduces to classical polyomino packing, a topic with a long history in recreational mathematics running from Solomon Golomb’s 1954 pentomino coinage through Dana Scott’s exhaustive enumeration of pentomino tilings of an $8 \times 8$ square minus the centre $2 \times 2$ in 1958. Our solver enumerates about $1\,200$ placements per board (the product of eight pieces, up to eight orientations, and several dozen translations) and CP-SAT handles the resulting $\text{exact cover}$ in a fraction of a second.