Solving Norinori: the puzzle with nothing written on it

Norinori in the browser with three rule sets inside. The grid is cut
into regions. Shade cells so that every region holds exactly two shaded
cells, and every shaded cell has exactly one shaded orthogonal neighbour —
so the shaded cells fall apart into dominoes, which are free to straddle
a border. That is the whole rule set. Notice what is missing: there are no
clue numbers. Every other puzzle in this series ships a generator whose job
is to carve numbers away; Norinori has nothing to carve. The partition is
the puzzle, and that changes both the variable you solve with and the way you
generate. Puzzle #26 in the solver-included series.

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

The rules

1. The grid is cut into regions (arbitrary polyominoes)
2. Every region holds exactly two shaded cells
3. Every shaded cell has exactly one shaded orthogonal neighbour

Rule 3 says the shaded cells decompose exactly into dominoes, and a domino
may straddle a region border.

That's it. No numbers.

What changes when there are no clues

Two things that were the same in every previous entry in this series both break.

	a clued puzzle	Norinori
what the generator varies	which clues survive	the partition itself
difficulty knob	how many numbers are left	which partitions you accept
natural variable	the cell	the region

The last row is the interesting one.

Lift the variable from the cell to the region

Treat a region as a variable. A region of k cells has exactly one decision to
make — which two of its cells are shaded — so its domain is the C(k,2) pairs,
and the domain is small: the mean region on a shipped board is 4 cells, which
is 6 pairs.

Under that lifting, the sprawling condition about dominoes wandering across the
board becomes an ordinary binary constraint between neighbouring regions.
Read both regions off their candidate pairs, everything else off the board, and
check that no cell that comes out shaded has two shaded neighbours or no
candidate partner left. Enforcing it is textbook AC-3.

const kept = live[i].filter((p) =>
  live[j].some((q) => binaryOk(state, puzzle, i, meta[i].pairs[p], j, meta[j].pairs[q])),
);
if (kept.length === 0) return null;
if (kept.length < live[i].length) {
  live[i] = kept;
  for (const k of meta[i].neighbours) if (k !== j) push(k, i);
}

Writing back down to cells is the obvious thing: a cell is shaded if every
surviving pair of its region contains it, white if none does.

The binary check is deliberately sound but not complete — a cell can touch
three regions and this looks at two — which is exactly why there is a third rule
set.

Three rule sets

local — count the region, look at the four neighbours, repeat. The puzzle
as a solver that never leaves the cell sees it. Shipped as the falsified rival.

pairs — the same, plus arc consistency on the region variables, driven to a
joint fixpoint.

probe — singleton consistency: assume a cell shaded, run pairs, erase it
if the board dies, and the other way round.

Measured over unique boards generated with no solvability filter, so the last
column is not circular:

size	local	pairs	probe	regions	mean region size
5×5	0%	55%	100%	6.0	4.17
6×6	3%	53%	100%	9.0	4.00
7×7	0%	33%	100%	11.9	4.10
8×8	0%	62%	100%	15.8	4.05

The cell-local rules finish almost nothing (the 3% is 2 boards out of 60).

A 900-position property test says it from the other side:

the local rules saw a cell the lifting missed ....   0 / 900   (subsumed)
the lifting saw a cell the local rules missed .... 509 / 900   (57%)
average advantage over all 900 positions ......... +11.4 cells

The 0 is structural, not luck: pairs runs every rule local runs, so the
containment holds by construction and the test just pins it down.

Generation is where the work is

There are no clues to remove, so the only thing the generator can vary is the
partition. Can it just draw one at random?

No — not even close. A random partition is not merely ambiguous, it usually
admits no shading whatsoever:

size	no shading at all	exactly one	two or more
5×5	62%	5%	33%
6×6	77%	2%	22%
7×7	93%	0%	7%

93% dead at 7×7, and 0% usable. Random generation is completely non-viable.

Build it backwards

So draw the shading first. Specifically an induced matching: a set of
dominoes no two of which touch. That is precisely the shape a legal Norinori
shaded set has to have, so the moment you have one you already have a valid
solution. Then grow one connected region around each pair of shaded cells, and
flood the leftovers into their smallest neighbour.

And then density turns out to be everything

One number decides whether this produces a puzzle or mush. Every region holds
exactly two shaded cells, so

mean region size = 2 / shaded fraction

is forced. Which means:

size	plain greedy matching	+ remove-one-and-refill	forced mean region size
6×6	37% shaded	50% shaded	5.37 → 4.00
7×7	38% shaded	49% shaded	5.21 → 4.12
8×8	35% shaded	48% shaded	5.66 → 4.21
10×10	36% shaded	48% shaded	5.59 → 4.15

Plain greedy matching stalls around 36%. That forces regions of 5.4 cells,
domains of C(5,2) and up, and partitions with hundreds of solutions — in
practice they pegged the counter's cap of 200.

The refill pass — drop a random domino, greedily re-add along a reshuffled edge
list, keep it if the count didn't drop — reaches 48–50%, close to the packing
limit for a grid. That one change tightens the boards by an order of
magnitude.

let best = refill([]);
for (let t = 0; t < rounds; t++) {
  const trimmed = best.slice();
  trimmed.splice(Math.floor(rng() * trimmed.length), 1);
  const grown = refill(trimmed);
  if (grown.length >= best.length) best = grown;
}

Close the gap by walking counterexamples

Even at full density some boards keep two or a few solutions. Hill-climbing on
the solution count did not work — most edits to a partition change nothing, so
the search wanders a plateau. (Measured: one board went 60 → 10 solutions in nine
moves, then oscillated in the 20s indefinitely.)

What worked is walking counterexamples:

1. Find one rival shading S' besides the intended solution S
2. Pick a cell k that S' shades and S does not
3. Move k into a neighbouring region

That single move always kills S': under S', k's old region is left
holding one shaded cell and its new region three. Meanwhile S survives
untouched, because k is unshaded there, so neither region's shaded count
changed. Strict progress against the rival you aimed at, every time.

A free theorem

Every region holds exactly two shaded cells. Every shaded cell sits in exactly
one domino. So project a solution onto the regions — each domino becomes an
edge between the regions of its two cells, a self-loop when both cells are in the
same region — and every region has degree exactly 2.

The projection is a 2-regular multigraph: a disjoint union of cycles covering
every region. Over 919 regions of shipped boards:

dominoes ................................. 919
crossing a region border ................. 233  (25%)
cycles of length 1 (a region's own domino)  686  (87%)
cycles of length 2 (two regions swapping)    88  (11%)
cycles of length 3 .......................   15   (2%)
cycles of length 4 .......................    3   (0%)

regionCycles returns that decomposition and a property test asserts the degrees
on every generated board.

Both rules are load-bearing

Take the shipped 5×5 boards and switch one rule off in the validator:

drop the region counts ... 7358 shadings — the same number on all 40 boards
drop the domino rule ..... median 54000 shadings (worst 77760)
still unique either way ..    0 / 80

The first line is the fun one. With only the domino rule left, the partition is
never read, so the answer is a property of the 5×5 grid — the number of
induced matchings on it — rather than of the puzzle. With only the counts left,
every region picks its pair independently and the answer is the product of
C(|R|,2). Neither rule decides anything on its own.

Soundness: two brute forces, on purpose

The series standard plus one. Two exhaustive counters that share no code with the
propagators, deliberately taking different routes:

• countBrute walks the cells in row-major order, pruning only incrementally (region shaded counts; the domino condition on a cell once all four of its neighbours are decided)
• countByRegions walks the regions, picking one 2-subset each

These two disagree only if the cell ↔ region translation itself is wrong — and
since that translation is the subject of this entry, checking it from both ends
is worth the extra counter.

Then four counters must agree on solution counts: the two brute forces plus the
rule-set searches. A disagreement means someone dropped or invented a solution.
124 tests.

Takeaways

• Norinori has nothing written on the board — the partition is the entire puzzle
• So the natural variable is the region, not the cell. Domains are C(k,2) pairs, averaging 6, and the global domino condition collapses into binary constraints between neighbours. AC-3 does the rest
• The cell-local rule set finishes ~0% of boards; the lifting decided more in 509 of 900 positions, +11.4 cells on average
• With no clues to remove, generation is the hard part. Random partitions are 93% unsolvable at 7×7 and 0% unique
• So draw the shading first as an induced matching. Density is everything: mean region size is pinned at 2 / shaded fraction, so greedy's 36% forces 5.4-cell regions and mush, while a remove-one-and-refill pass at 48–50% forces 4.0-cell regions and tight boards
• Close the rest by walking counterexamples: moving a cell that the rival shades and the intended solution does not always kills the rival and never the intended solution
• Free theorem: projecting a solution onto the regions always gives a 2-regular multigraph — a union of cycles. 87% are length 1, the longest seen is 4, and 25% of dominoes cross a border
• Soundness pinned by four counters, two of them brute forces taking different routes. 124 tests

Which puzzle should I take apart next?

---

SEN LLC — software development and technical consulting