Solving Shikaku with constraint propagation: when the unknown is a rectangle, not a cell

Shikaku (四角に切れ, "divide by squares") in the browser with a
constraint-propagation solver inside. Cut the grid into rectangles: every
rectangle holds exactly one number, and that number is its area. This
is where the previous twelve solvers' model breaks. They all put the unknown
in a cell — a colour bit, a digit domain, an edge bit. Shikaku's unknown is
coarser: which rectangle does each number take? Enumerate those candidates
up front and the puzzle collapses into a plain exact cover, with
propagation running over sets of rectangles instead of cells. Two sound,
mutually dual rules (only-coverer and forced-cell) run to a
fixpoint, then a fewest-candidates search proves uniqueness. Solver-backed
puzzle #13.

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

The rules, and the logic that follows

A Shikaku grid is R×C with some cells carrying a number. A finished board
cuts it into axis-aligned rectangles so that:

1. every rectangle contains exactly one number;
2. a rectangle's area equals that number;
3. the rectangles tile the grid — every cell covered exactly once.

Why the cell model is the wrong one here

Ask "what colour is this cell?" and Shikaku gives a useless answer: every cell
is covered, always. The information isn't in the cell — it's in the cut. So
the domain moves up a level, from the cell to the clue:

// every box that contains the clue, has exactly its area, and eats no other clue
export function candidatesFor(p: Puzzle, cell: number): Rect[] {
  for (let h = 1; h <= n; h++) {
    if (n % h !== 0) continue;   // only integer h×w factorisations
    const w = n / h;
    ...
  }
}

A 12 clue has at most six shapes (1×12, 2×6, 3×4, 4×3, 6×2, 12×1), each with a
handful of placements — a domain of a few dozen at worst. Small enough to
enumerate once and then just filter, which is the whole trick.

Note the third condition doing quiet work: a candidate that would swallow
another clue never enters the domain at all. The closer the numbers sit, the
smaller every domain starts out.

The two rules are duals

The entire propagation is two sound rules — and they're mirror images:

// only-coverer: a cell nobody else can reach pins its clue
if (who.size === 0) return false;              // orphan cell — nothing can cover it
if (who.size === 1) /* kill k's candidates that miss c */

// forced-cell: a cell one clue always takes is closed to the rest
for (const c of common) /* kill every OTHER clue's candidate covering c */

One says a cell needs someone; the other says a cell allows only one.
Together they're enough — and the rule you'd reach for first, "a clue down to a
single candidate commits it, and everything overlapping dies", needs no code
at all. It falls out of forced-cell: a singleton domain's intersection is its
own rectangle, so every cell of that box closes to everyone else automatically.

propagate() runs both to a fixpoint, returning false the moment a clue
loses every candidate or a cell loses every coverer.

When logic stalls: search that proves uniqueness

Some boards need a guess. The search branches on the clue with the fewest
surviving candidates, pins it, re-propagates, and counts. A complete assignment
is accepted only when isSolved() agrees — an independent validator that
re-checks areas, containment, overlap and full coverage from scratch, sharing no
logic with the propagator, so a solver bug can't cancel out a validator bug.

export function hasUniqueSolution(p: Puzzle): boolean {
  return solveAll(p, 2).length === 1;
}

solveAll enumerates up to a limit; hasUniqueSolution stops at two, and the
tests assert every bundled puzzle stops at exactly one.

There's also a nearly-free sanity check worth doing before any of it: the clues
must sum to the area of the grid. One pass, and it rejects a whole class of
malformed boards before a single rectangle is enumerated.

const total = p.clues.reduce((a, b) => a + b, 0);
if (total !== p.R * p.C) return [];

Puzzles are solver-verified, not hand-keyed

Each board is authored as its solved tiling — one letter per cell naming its
rectangle, uppercase on the cell that carries the number:

'aaabBcc'      region 'b' is a 1×2 box, so its clue reads 2
'aAadDCc'      region 'a' is a 3×3 box, so its clue reads 9
'aaaeecc'

Both halves of a clue are derived: its position is the uppercase cell, its
number is the area of that letter's region. Nothing is typed twice, so a
clue cannot drift out of sync with its answer. Better, a drawing that isn't a
real tiling — an L-shaped region, a region with two numbers, a region with none —
fails to parse at all:

if (h * w !== cells.length) {
  throw new Error(`board "${name}" region "${key}" is not a filled rectangle`);
}

The generator (tools/generate.mts) cuts a grid into random rectangles and tries
several clue placements per tiling — which cell in a box carries the number
changes the puzzle completely, and that turned out to be the search axis that
mattered — keeping a board only if the solver proves a single solution. The
tests re-solve every board and assert it recovers exactly the drawn tiling:

expect(hasUniqueSolution(b.puzzle)).toBe(true);        // exactly one answer
expect(coverMap(solveAll(b.puzzle, 2)[0], b.puzzle))   // and it's the drawn one
  .toEqual(b.cover);

One more generator knob that earned its keep: penalise 1×1 rectangles
(weight 1 vs 3). A board of single cells is perfectly unique and perfectly
boring. Same discipline as the Nurikabe, Masyu, Hashiwokakero, Star Battle,
Kakuro and Akari entries: ship your levels through your solver. The bundled
boards run 5×5 up to 10×10.

A small UI lesson

Colouring the rectangles, I first cycled hue by k * 47 % 360. Red came up.
Red was already the colour for an illegal rectangle, so a perfectly good box
rendered as an error. Fixed by exiling the hue from the red band:

// Kept inside 40°..330° — red is reserved for illegal boxes and must not collide.
const hue = 40 + ((k * 67) % 290);

Generated palettes don't just look bad when they collide — they break meaning.

Takeaway

The real lesson of Shikaku is that the granularity you put the unknown at
decides how hard the puzzle is. Put it in the cell and you get a useless
answer: everything is covered, always. Move it to the cut — which rectangle
does each number take — and the domain becomes a small enumerable set, the puzzle
collapses into exact cover, and you need exactly two rules, which are duals of
each other, and which contain the obvious third rule for free. Get the model
right and the code gets shorter. Solver-backed puzzle #13.