How the Solver Works

A puzzle is three things: a set of cells (the board can be non-rectangular, with holes), a multiset of dominoes — each a pair of pips from 0–6 — and a set of regions, each with a rule. A solution tiles every cell with dominoes so that every region rule holds at once.

The five region rules reduce to simple aggregates over the cells they cover:

sum = N

the covered pips add to exactly N

equal

every covered pip is the same value

unequal

every covered pip is distinct

< N / > N

the covered pips sum to less than / greater than N

empty

no rule — any pips are fine

Crucially — and unlike classic dominoes — touching halves do not need to match. Only the region rules matter, which is exactly what makes the search interesting.

At heart it's depth-first backtracking: place a domino, recurse, and undo on failure. The leverage comes from which cell you fill next. Instead of scanning in reading order, the solver uses the minimum-remaining-values (MRV) heuristic — it always fills the empty cell with the fewest empty neighbours, i.e. the most boxed-in one, and stops looking as soon as it finds a cell with one option or none. Forced moves get made immediately and dead ends surface early, which collapses the branching factor.

solve():
  if every cell filled            -> SOLUTION
  cell = empty cell with the
         fewest empty neighbours          # MRV
  for each empty neighbour n of cell:
    for each remaining domino (a, b):
      for each orientation:
        place (a,b) over (cell, n)
        if regionsValid()                 # incremental check
           and noCellIsolated()           # structural prune
           and regionsStillSatisfiable(): # forward check
          if solve(): return SOLUTION
        undo placement                    # backtrack
  return FAIL

Re-scanning the whole board after every placement would be wasteful, so the solver keeps live aggregates for each region: a running sum, a filled-cell count, and a per-value tally. From those, every rule is an O(1) test:

• sum fails fast if the partial sum already exceeds the target;
• equalis just “at most one distinct value present”;
• unequalis “distinct count equals filled count”.

Because a domino only ever touches the (at most two) regions containing its two cells, placing or removing one is an O(1) update — no board sweep required.

Before recursing, the solver asks a cheap but powerful question: can each unfinished region still be satisfied with the pips that are left? It keeps a pip pool— how many of each value 0–6 remain in unplaced dominoes — and, using a greedy minimum/maximum achievable sum, prunes branches where a target has already become unreachable, an “all-equal” region no longer has enough matching pips, or an “all-different” region has run out of distinct values. Every test is a necessary condition, so it never discards a real solution — it just amputates doomed branches before they grow.

• No isolated cells. A placement that strands an empty cell with no empty neighbour can never be tiled by a 1×2 domino — reject it. Only cells adjacent to the piece you just placed can become newly isolated, so the check stays local and cheap.
• Symmetric dominoes.A piece like 3|3 is identical when flipped, so the redundant orientation is skipped — halving that piece's branching.

Everything constant is precomputed once into typed arrays — neighbour adjacency, each cell's region membership, and the domino pip-pairs as parallel arrays. The board is an Int8Array, the pip pool an Int32Array, and the per-region tallies are typed arrays too. The hot loop has no string keys, no Map rebuilds, and no per-node allocations: the search is just integer pointer-chasing, which is what keeps it fast under heavy backtracking.

The worst case is exponential, but real NYT puzzles are far from worst case once MRV and propagation are doing their jobs:

A few puzzles even admit more than one valid tiling — the solver returns the first it proves correct.