Seventy-one games, and this is the first whose engine returns a count rather than a move. Domino tiling hands you a board with holes punched in it and 2×1 tiles to cover the rest, and every question a player has is a comparison of two counts: a move is fatal when the ways to finish drop to zero, forced when that number does not change at all, and its odds in a random finish are its share of the total.
The count cannot be enumerated. An 8×8 board has 12,988,816 tilings; a 12×14 has 43,242,613,716,069,407,953. So the engine is a broken-profile dynamic program that sweeps the cells in reading order carrying a W-bit frontier:
if ((m & 1) || free[p] === 0){ nd[m >> 1] += v; continue; } // covered from behind, or a hole
if (canR && !(m & 2)) nd[(m | 2) >> 1] += v; // lay it rightwards
if (canD) nd[(m >> 1) | TOP] += v; // lay it downwards
256 states on an 8×8 instead of 18,446,744,073,709,551,616 subsets. Play it, with the count live: https://dev48.infy.uk/game/day71-domino-tiling.html
The one fact everybody knows is constant along every edge of the game graph
Colour the board like a chessboard; a domino covers one dark and one light square; unequal counts cannot be tiled. That is the mutilated-chessboard argument, and the first thing anybody says about this subject.
Measured over three board configurations it found 0 of 4,461 fatal moves — and it never can, because a domino removes one square of each colour by construction. I checked the invariant directly: of 22,211 legal dominoes, the number it watches changed 0 times. Perfectly true, and useless to a player.
As a tileability test it also degrades as the board grows:
| test | right about the boards it passes, 4×4 | 4×5 |
|---|---|---|
| equal colour counts | 44.3% | 31.8% |
| every component balanced | 97.6% | 94.3% |
| bipartite matching | 100% | 100% |
The DP is checked against brute force, a matching that cannot count, a permanent, the Aztec diamond and Kasteleyn's eigenvalue product (worst relative error 1.8e-14) — on all 65,536 boards of a 4×4 and all 262,144 of a 3×6, 0 disagreements.
What the measurement contradicted
The page I set out to build was a board where every domino is forced and no local rule can see one. Those boards do not exist and cannot. Swept exhaustively: 17,817 connected uniquely-tileable boards, the number with no cell of degree one to start from is 0, and the number where repeated degree-one forcing failed to finish is 0.
It is structural rather than lucky. Orient every domino of a unique tiling one way and every other adjacency the other; a directed cycle would be an alternating cycle and hence a second tiling, so the orientation is acyclic, an acyclic digraph has a sink, and a sink is a cell with exactly one free neighbour. The step that does the work needs bipartite, and the page carries the control that proves it: two triangles joined by a bridge have exactly one perfect matching and minimum degree 2.
One last number that is not what it looks like. A 12×12 board has 53,060,477,521,960,000 tilings — 5.9× past 2⁵³ — and the Float64 DP returns it exactly. The first rectangle it gets wrong is 10×14, three times smaller, off by one.
Part of a from-scratch series — one game a day, vanilla JS, one file, inline CSS, no external asset of any kind: https://dev48.infy.uk/gamefromzero.php
