Calendar Puzzle

Arrange the puzzle pieces to reveal the current date.

Forked from https://github.com/bsoule/CalendarPuzzle

Hosted at https://calpuz.dreev.es

Notes for the solver

Below is a small subset of the things I wrote down while coaxing the robots to write code...

1. Every piece has from the beginning a list of ORIENT/POS pairs indicating how/where it can potentially be placed. Call that the piece's potential placings. For a piece p we write p.pp for p's potential placings.
2. Sort the pieces in the queue by length(pp). The heuristic is to place the most constrained pieces first.
3. Take a piece p from the queue and try every placing i in p.pp.
4. If i yields no unfillable regions, place p according to i and recurse for the next piece in the queue. But before doing so, filter the pp of every other piece q in the queue: for each placing j in q.pp, if j overlaps i, remove j from q.pp.
5. If i does yield unfillable regions, continue to the next element of p.pp.
6. If i yields a region that forces placement of another piece, q, remove everything from q.pp except that placement.

Regions of unfillable size:

Given the grid with some pieces placed so far, use flood-fill to get a list of all the connected regions of vacant cells on the grid. If any region has a number of cells that not a subset-sum of the sizes of the pieces in the queue, that region is unfillable.

Special case that's pretty much always the case in this puzzle: all the pieces in the queue have size 5 (since they're all pentominoes except for 1 hexomino which we generally place first) so every region's size must be a multiple of 5 to be fillable.

Regions of unfillable shape:

If a region has fewer cells than the sum of the smallest two pieces in the queue, that region must have the same shape as one of the pieces in the queue. We test if a piece and a region have the same shape by picking a canonical orientation and position and seeing if all their cells coincide.

(Current code actually only checks the shape if the size exactly equals one of the sizes in the queue of pieces. i guess the problem with the current code is that we could (in theory) have a piece that's as big as 2 other pieces combined. say we have a size-2 piece, a size-4 piece, and a size-6 piece in the queue. and supposed there's a size-6 region. it may be that no single piece fits in that region but the size-2 and size-4 piece together do fit.)

Old Cave Detection Algorithm:

1. If there is more than one distinct piece size in the queue of pieces to place, do nothing. (For this puzzle there will often be only pieces of size 5 in the queue. How to generalize this to more than one distinct piece size in the queue is an interesting problem we're setting aside.)
2. Let uq (for "uniform queue") be that size. (Again, typically that's 5 for us.)
3. Call a cell on the grid vacant if it's available to be covered by a piece and is not marked as a cavity (see next).
4. Call a cell on the grid a cavity if it's vacant and has at most 1 vacant neighbor. (Another name for a cavity could be a dead-end but we're defining "cavity" recursively; read on.)
5. Find all cavities. (Finding a cavity may make new cells become cavities but in this step we just find the current cavities.)
6. Call a connected set of cavities a cave. (Notice how the deep end or nadir of a cave is a cavity and marking it as such makes the second-from-the-end a cavity. Iterating, we would mark the whole cave as cavity cells.)
7. If a cavity cell has exactly one vacant neighbor, mark that cell as a cavity. (This means we actually also count as part of the cave the cell you might think of as just in front of the entrance to the cave. The idea is that any piece that will fill this cave will, if we haven't hit size uq yet, have to spill out onto this cell as well.)
8. Repeat step 7 only until there exists a cave with uq cells. (Note that it's possible for two distinct caves to merge while doing this.)
9. If we run out of cavities without finding a uq-sized cave, do nothing -- caves of size less than uq don't count.
10. If we do find a cave of size uq, treat that cave as a size-uq region the same way we do for size-5 and size-6 regions.
11. If the cave is not fillable by one of the pieces in the queue, mark the cells of the cave as unfillable and backtrack.
12. If the cave is fillable by a piece, immediately place the piece coincident with the cave.

New Cave Detection Algorithm:

1. If there is more than one distinct piece size in the queue of pieces to place, do nothing. (For this puzzle there will often be only pieces of size 5 in the queue. How to generalize this to more than one distinct piece size in the queue is an interesting problem we're setting aside.)
2. Let uq (for "uniform queue") be that size. (Again, typically that's 5 for us.)
3. Label every vacant cell with its neighbor count: the number of vacant neighbors it has.
4. For each cell c that has a neighbor count of 2 (think of c as a bottleneck) call those 2 vacant neighbors nbr1 and nbr2 and do steps 5-10.
5. Do a flood-fill from nbr1, excluding c.
6. If the flood-fill includes nbr2, it is not a valid cave. (In this case c was not really a bottleneck.)
7. If the flood-fill is less than size uq, add cell c to it.
8. If it's still less than size uq, add cell nbr2 to it.
9. It's a cave if it now has size uq.
10. Repeat steps 5-10 but with nbr1 and nbr2 swapped (nbr2 in step 5, nbr1 in step 8).

PS: When cave detection from two different nadirs (a nadir is a vacant cell with only one vacant neighbor, like a dead-end) overlap, I think there are additional pruning opportunities we could be taking advantage of. Like in the following diagram, we have nadirs at a and b. There's a 3-cell cave from a to c and a 4-cell cave from b to c. Say there are only 5-cell pieces left to place. Notice that there are 6 cells total in the combined overlapping caves. So no single piece can fill it. But also any piece that fills one of the caves will make it impossible to fill the other. I'm not sure yet how to codify that as a pruning criterion in general.

XXaX
XXoX
XXco
booX
XXXX

Additional pruning by not considering piece placements that block tunnels:

Tunnels are when you find a deadend (cell with 0 or 1 vacant neighbor; aka nadir) and follow it until there's more than one possible neighbor to move to (and stopping if you hit uq cells, as in cave detection above).

When considering a possible placement of a piece, no tunnels can be partially covered. I.e., each tunnel that the piece overlaps with must be completely covered by the piece. If that's not the case, it's not a valid placement.

Said yet another way, to be part of a valid solution, a piece placement that covers some cells of a tunnel must cover all cells of that tunnel. (The piece may cover additional cells not part of the tunnel.)

Proof:

1. Note that by construction the tunnel is at most uq cells and the piece is exactly uq cells.
2. Suppose a piece placement covers some of the cells of the tunnel but there's a particular cell c it leaves uncovered.
3. By construction, if you start at the nadir and find uq connected cells, you will cover every cell of the tunnel.
4. That means every cell in the tunnel in between the nadir and (let's call it) the mouth separates the nadir from the mouth.
5. So c can't be one of those cells. If it were, it would leave less than uq cells connected to the nadir.
6. For the same reason, c can't be the mouth.
7. Can c be the nadir? No, that would leave the nadir as an isolated and unfillable vacant cell.

(I think I could improve that exposition by combining some of those latter points.)

Pruning by non-coverable cells:

1. Before placing a piece in the queue, cache every possible placement for every piece in the queue.
2. While doing so, keep a tally for every vacant cell of the number of possible placements that cover that cell.
3. If any cell has a tally of zero, backtrack.

Musing (I haven't tried this yet):

There are 8 pieces to place on a grid of 12+31-2=41 initially vacant cells. Suppose we consider each of those 41 cells to have one of 8 possible colors, initially. We set the first cell to the first color and then branch to the next cell, also initially the first possible color, and so on. Each time we pick a color c (and call the piece with color c, p) for a cell, we consider all the ways to place p to cover that cell. Every cell untouched by any such placement gets c removed from its list of possible colors.

Notes for the UI

Via Faire:

An annoying thing in this implementation is that sometimes when you click to rotate a shape, it rotates in such a way that it's no longer under the mouse cursor. That means you can't click, say, 3 times in a row to get 270 degrees of rotation. Please make it so rotation happens exactly around the point that's clicked on. Also, snap-to-grid should not happen when rotating, only when dragging.

Wishlist

1. Pull-to-refresh doesn't work but maybe it shouldn't since that would interfere with panning?
2. The solver code is a disaster after endlessly coaxing the robots along.
3. I think the hint feature is a little buggy.
4. Replace the hint popup with a little floating box similar to the solver progress box that shows a mini vesrion of placements you have so far and the number of solutions that exist with those placements.

Quals (this section by GPT-5.2)

This repo includes Playwright quals that check the invariant that a piece rotates around the point you click/tap.

• Install deps: npm install
• Run quals: npm run qual (alias: npm test)

Playwright runs a local static server (see playwright.config.js) and uses Chromium.