Solving Dominosa: the puzzle where nothing is hidden, and the rule I measured into irrelevance

Dominosa in the browser with a two-sided exact-cover solver
inside. The complete double-n domino set was laid flat on a grid and
the borders rubbed out — put them back. Every number is visible from
the first second, so the unknown is not a cell but a placement, and
the board is an exact cover with two tight sides. Two dual exactly
one rules and their two intersection duals subsume the human trick
list. Then there is the beautiful geometric rule — an exact dimer count
over the surviving edges — which I built, measured, and switched off.
Solver-backed puzzle #20.

🌐 Live demo: https://sen.ltd/portfolio/dominosa/
📦 GitHub: https://github.com/sen-ltd/dominosa

A puzzle with no hidden information

Nineteen puzzles into this series, every one of them has worked the same
way: some cells are given, most are blank, and solving means filling the
blanks. Dominosa doesn't have blanks.

The complete double-n domino set — every unordered pair (a,b) with
a ≤ b, exactly once — is laid flat on an (n+1)×(n+2) grid, and then
the borders between tiles are rubbed out. What you get is a full grid of
numbers. Nothing is hidden. Nothing is missing.

The unknown is the cut.

That single observation decides the entire design, because it means the
solver's variable cannot be a cell. Every cell already has its value.
What is undetermined is which of its neighbours it is joined to.

The variable is a placement

So the variable is a placement: one adjacency of the grid, carrying
whichever domino of the set its two numbers spell.

export interface Placement {
  id: number;
  pair: number;   // index into the double-n set
  a: number;      // the two cells, a < b
  b: number;
}

Build one per adjacency and the whole puzzle becomes an exact cover with
two tight sides:

• every pair is used by exactly one chosen placement — P constraints;
• every square is covered by exactly one chosen placement — 2P constraints.

Tight because the counts match exactly. A double-six board is 7×8 = 56
squares, and the double-six set has 28 dominoes. 56 = 2 × 28. There is no
slack on either side — no spare square, no spare tile — and that is what
makes the rules below bite.

The whole solver state is then one bit per placement: is it still
possible?

export type State = Uint8Array;  // alive[id]

Which pairs are placed, which squares are decided, where the board falls
apart — all of it is read back off that bitset.

Four rules, and they are all the same rule twice

Propagation is two dual exactly one rules:

• pair singleton — the 3-5 has one spot left on the board, so lay it;
• square singleton — this square has one neighbour left, so lay it.

plus their two intersection duals, which settle nothing and delete a lot:

• shared square — every remaining spot for the 3-5 covers this square, so whatever else wanted that square can't have it;
• forced pair — every way to cover this square spells 3-5, so the 3-5 is spent here, and its spots elsewhere die.

export function ruleSharedCell(m: Model, alive: State): Step {
  for (let pair = 0; pair < m.pairs; pair++) {
    const cands = survivors(m.byPair[pair], alive);
    if (cands.length === 0) return -1;
    if (cands.length < 2) continue;
    for (const cell of sharedCells(m, cands)) {
      for (const id of m.byCell[cell]) {
        if (alive[id] && m.placements[id].pair !== pair) alive[id] = 0;
      }
    }
  }
  ...
}

Note what the last two are: an intersection over a domain's supports.
That is exactly the move that turns a naked single into a naked set, and
it is the same shape in both directions because the two sides of the
cover are symmetric. Four rules on paper; one idea, applied to pairs and
to squares.

Between them they cover the published human trick list. The demo's
Hint button just names whichever one fires next — "the 0-3 domino has
only one place left on the board", "every way to cover this square spells
2-4, so the 2-4 is spent here" — which is a pleasant way to check that
the rule set really does match how people play.

How big was the space, anyway?

Now forget the pips entirely. The surviving placements are just edges on
the squares, and a solution has to perfectly match every square using
those edges. That is the dimer problem — the thing Kasteleyn solved
in 1961 — and on a grid an exact broken-profile DP answers it in one
sweep: march through the cells row-major carrying a cols-bit frontier
mask of which upcoming cells are already covered from behind.

export function countTilings(m: Model, alive: State): number {
  const width = 1 << m.cols;
  let cur = new Float64Array(width), next = new Float64Array(width);
  cur[0] = 1;
  for (let cell = 0; cell < m.cells; cell++) {
    next.fill(0);
    const canRight = m.right[cell] >= 0 && alive[m.right[cell]] === 1;
    const canDown  = m.down[cell]  >= 0 && alive[m.down[cell]]  === 1;
    for (let mask = 0; mask < width; mask++) {
      const ways = cur[mask];
      if (ways === 0) continue;
      if (mask & 1) { next[mask >> 1] += ways; continue; }
      if (canRight && !(mask & 2)) next[(mask | 2) >> 1] += ways;
      if (canDown) next[(mask >> 1) | (1 << (m.cols - 1))] += ways;
    }
    [cur, next] = [next, cur];
  }
  return cur[0];
}

Point it at a bare grid with every edge alive and it tells you what the
pips are up against:

board	grid	tilings
Double-Three	4×5	95
Double-Four	5×6	1,183
Double-Five	6×7	31,529
Double-Six	7×8	1,292,697
Double-Seven	8×9	108,435,745

A hundred and eight million ways to cut up an 8×9 grid. The pips take
that to one.

The rule I measured into irrelevance

That same DP is a propagator, and a lovely one. It is a relaxation of
Dominosa that respects the geometry and ignores the pairs — the exact
complement of the placement algebra, which respects the pairs and is
blind to geometry. So anything it calls impossible really is:

• if countTilings is zero, the state is dead;
• if a placement appears in no tiling, delete it.

There is a cheap shadow of it too: a connected component of squares with
an odd number of squares can never be tiled, so any odd component
kills the state. No domain is empty, no pair is short, the algebra is
perfectly happy — the board is simply cut into a piece that cannot be
covered.

I wrote both, and then I measured them, because "this rule is beautiful"
and "this rule fires" are different claims. Over 24,000 random states
across the six bundled boards, I committed a few random placements, ran
the pair algebra to a fixpoint, and asked whether the geometry then found
a contradiction the algebra had missed.

It did. Once.

Double-Three   algebra kills 3500 | parity then kills    0 | survives 500
Double-Four    algebra kills 3560 | parity then kills    0 | survives 440
Double-Five    algebra kills 3652 | parity then kills    0 | survives 348
Double-Six     algebra kills 3592 | parity then kills    1 | survives 407
Double-Six II  algebra kills 3678 | parity then kills    0 | survives 322
Double-Seven   algebra kills 3651 | parity then kills    0 | survives 349

The reason is structural, and obvious in hindsight: deciding a domino
kills edges on both of its squares. By the time a pocket of the board
is stranded badly enough for a parity argument to see it, some square
inside that pocket has already lost every neighbour but one — and the
square-singleton rule got there first, several deductions ago. Geometry
and algebra are looking at the same collapse; the algebra just looks
earlier.

So: the exact dimer filter costs a full DP sweep per surviving edge — 26
ms against 0.1 ms on Double-Seven — and buys nothing. It stays exported,
documented and tested; it is not in the default rule set. The free
shadow, ruleParity, stays in, because it is one linear pass and it did
fire that once.

The one case it caught is now a test fixture, which is my favourite kind
of test: the single state in twenty-four thousand where the expensive
idea earned its place.

it('catches a dead board the pair algebra is happy with', () => {
  const m = buildModel(BOARDS[3].puzzle);
  const alive = initialState(m);
  commit(m, alive, 63);   // the 3-5, down the middle-left
  commit(m, alive, 72);   // the 2-1, across the right
  expect(propagate(m, alive.slice(), ALGEBRAIC_RULES)).toBe(true);
  expect(ruleParity(m, alive.slice())).toBe(-1);
  expect(countTilings(m, alive.slice())).toBe(0);
});

There is a nice safety net under all of this. Every rule is sound —
it only ever deletes possibilities that genuinely have none — so which
rules you enable can change the runtime but never the answer. That is
directly asserted:

it.each(BOARDS)('$name: counts the same solutions under every rule set', (board) => {
  const counts = [ALGEBRAIC_RULES, ALL_RULES, DIMER_RULES].map(
    (rules) => solveAll(board.puzzle, 3, { model, rules }).length,
  );
  expect(counts).toEqual([1, 1, 1]);
});

Turning an expensive propagator off is a performance decision, not a
correctness one. That is worth knowing before you agonise over it.

Dominosa resists propagation

Here is the other measurement, and it is the one that genuinely surprised
me. In every earlier puzzle in this series, propagation does the heavy
lifting and the search is a formality. Dominosa is not like that:

Double-Three  fixpoint settles 20/20 squares → 1 node
Double-Four   fixpoint settles 30/30 squares → 1 node
Double-Five   fixpoint settles 42/42 squares → 1 node
Double-Six    fixpoint settles  6/56 squares → 5 nodes
Double-Six II fixpoint settles 56/56 squares → 1 node
Double-Seven  fixpoint settles  6/72 squares → 5 nodes

Four boards fall to the fixpoint outright. The other two settle six
squares out of fifty-six — barely more than nothing — and then collapse
entirely after a single guess. Five search nodes.

That bimodality is Dominosa's own. The constraint graph is loose: pairs
only interact through squares, and a square has at most four neighbours,
so there is very little for the fixpoint to chew on until something
gets decided. Once one domino is fixed, the tightness of the cover does
the rest in an avalanche.

When the fixpoint stalls, the search branches on the variable with the
fewest candidates — pair or square, whichever is narrower — and counts
solutions with a cutoff at two, proving every bundled board has
exactly one.

Authoring: the board with no clues to delete

Every other puzzle in this series is authored the same way: build a full
solution, then greedily delete givens while uniqueness survives. Dominosa
has nothing to delete. The full grid of pips is the board.

So generation is: tile the grid at random, deal the complete set onto
that tiling as a random bijection, write each pair's two numbers into its
two squares, rub the borders out — and keep the deal only if the engine
proves the pips admit exactly one tiling. Otherwise reroll. Difficulty is
a property of the deal, not of how much was hidden.

Rerolls needed, in practice: 25 for double-three, 3 for double-four, 43
for double-six, 64 for double-seven. Uniqueness is common enough that
rejection sampling is the whole algorithm.

One thing this bit me on, and it is worth flagging. My first parity rule
was subtly unsound: it ran on the still-undecided squares and forgot
that an undecided square can be matched to an already-decided one, so it
pruned states that had real solutions. The generator dutifully certified
two boards as unique that had two solutions each. Nothing in the puzzle
looked wrong — the boards rendered fine, the solver returned an answer.
It surfaced only because I had a diagnostic that solved every board under
several rule sets and printed the counts side by side, and two of them
disagreed. Sound rules must agree; disagreement is a bug, and it is much
easier to see than a wrong answer. The fix was to run the component
count over all squares and the surviving edges, where a perfect
matching can never cross between components.

Takeaways

• When a puzzle hands you all the data, look for the variable that isn't a cell. Placement, not position — and the constraint structure falls out immediately.
• An exact cover with two tight sides gives you every rule twice, in dual pairs. Write one direction, transpose it, and you have the trick list.
• Measure the beautiful rule before you ship it. A sound propagator that never fires is a slow no-op. Mine fired once in 24,000 states, and that one state makes a better test than it does a feature.
• Sound rules make rule selection a performance knob, not a correctness one — and cross-checking solution counts across rule sets is a cheap way to catch an unsound one.
• 145 tests, TypeScript, zero runtime dependencies.

All the code is public: https://github.com/sen-ltd/dominosa