Solving Kurodoko: whether a rule looks useless depends on where you measure it

Kurodoko (also sold as Kuromasu and 黒マスはどこだ) in the browser with
four rule sets inside. Blacken some cells. A numbered cell is always
white, and its number is how many white cells it can see — itself, plus
the unbroken runs of white in all four directions, each stopping at the first
black cell or the edge. No two black cells touch, and all the white
cells form one connected group. Puzzle #29 in the solver series.

Demo: https://sen.ltd/portfolio/kurodoko/
Repo: https://github.com/sen-ltd/kurodoko

Two measurement stories this time.

• The cross-check caught an unsound propagator — one that looked obviously correct while I was writing it.
• The same rule looked worthless and then decisive, with nothing changing but where I measured it.

The variable is not the cell

A clue with number k says

1 + up + right + down + left == k

where each term is the length of an unbroken white run with a hard geometric
cap. Four bounded integers summing to a constant is a shape a solver
already knows what to do with: a direction's run is at least the total minus
what the other three could contribute at their most generous, and at most the
total minus what they must contribute at their meanest. Plain interval
propagation.

How much smaller does that make the problem? Measuring the size of one clue's
domain — the compositions of k−1 into four capped parts:

board	mean compositions per clue	largest	raw cell space
6×6	9.9	28	2³⁶ ≈ 6.9e10
8×8	19.0	60	2⁶⁴ ≈ 1.8e19
10×10	35.2	100	2¹⁰⁰ ≈ 1.3e30

Thirty-five options at 10×10, against a raw cell space of 2¹⁰⁰.

And the reach of each rule set, measured on boards carrying the same number of
clues as the shipped banks but never filtered for solvability, so the last
column is not circular:

board	cells	rays	connect	probe
6×6 cells decided	8%	25%	25%	74%
8×8 cells decided	8%	34%	35%	86%

Reading each clue on its own gets 8%. Lifting it to four integers gets 25–34%.

The rule that looked obviously right and wasn't

Once a direction's run is pinned to [lo, hi], two conclusions seem to follow:

1. the run is at least lo, so the first lo cells of that ray are white
2. the run is at most hi, so the cell at hi is black

The first is sound. The second is not.

"At most hi" does not put a black cell at index hi. If the run stops short,
the cell at hi sits beyond the stopping cell — outside this clue's view
entirely — and is completely free. The step is only justified once the whole
prefix is already known white, which pins the run at exactly hi.

That rule shipped into the first working version, and the boards it generated
looked perfectly fine. What caught it was the counters disagreeing:

6x6 #0: byCells=1 byRays=1 byRules=0   <- only the propagation-backed counter
                                           says there are no solutions

Propagation was killing the real solution, which is exactly what an unsound
propagator does. Fixing it re-labelled the difficulty of the whole bank — the
weaker rule sets had been "solving" boards by smuggling in the answer.

The two brute-force counters are deliberately written to enumerate opposite
halves of the problem:

1. by cells — walk the grid row-major, pruning on clue bounds
2. by rays — walk the clues, choosing each one's four ray lengths from the compositions of k−1, and paint the consequences

They share no logic with the propagators and none with each other, so one
mistake cannot show up identically in both.

Whether a rule looks useless depends on where you measure it

This was the interesting part.

Drop one propagator from the strongest fixpoint and count again (6×6, 30
boards):

dropped	free cells still decided
nothing	35%
shaded-adjacency	26%
plain per-clue counting	35% (no change — the lifting subsumes it)
the ray lifting	7%
connectivity	34%

The lifting is load-bearing: 35% collapses to 7% without it. Expected.

And connectivity moves the number by one point. On that table alone the
conclusion writes itself: dead weight. It looks exactly like the checkerboard
colouring argument from the previous entry,
which stayed at 78% whether you kept it or not.

It isn't. Measure the same rule inside singleton consistency — assume a
cell, propagate, see whether the board dies:

	free cells decided	boards finished
probe with connectivity	100%	25/25
probe without connectivity	90%	8/25

Same propagator. Same boards. Opposite verdict.

The two measurements ask the rule to do different jobs. At fixpoint, the job is
decide a cell on your own — and connectivity almost never can, because
early on there are too few known white cells for an articulation point to
separate any of them.

Inside singleton consistency the job is refute an assumption. The moment
you assume a cell is black, the board becomes far more constrained: more whites
are forced, more blacks are forced, and severing the white region becomes a
real possibility. As a decider it is powerless; as a refuter it is the
difference between finishing 8 boards and finishing 25.

I called Yajilin's colouring argument "true and worthless" last time, and that
verdict holds — it was worthless at fixpoint and inside probing, refuting 1
wrong guess in 1090. This one is not the same situation, and the lesson is:
before concluding a rule does nothing, measure it in both of the jobs a
propagator can hold.

Adding a clue never changes the answer

The generator has exactly the opposite character to the last one.

In Yajilin a clue cell is off the loop, so adding a clue pulls a cell out of
the solution and changes it — and routing ambiguity could not be fixed by
clues at any price.

In Kurodoko a clue cell is just a white cell carrying a number, and it was
white already. So:

Adding a clue cannot change the solution. It can only remove rivals.

That makes the whole pipeline monotone and termination free. Paint a legal
board, then keep adding clues until nothing else solves it — in the worst case
every white cell becomes a clue and the board is pinned by construction. Then
run it backwards and drop every clue that turns out not to be pulling its
weight:

board	clues when the walk stopped	after the sweep	removed
6×6	7.8	6.2	21%
8×8	12.5	10.0	20%
10×10	18.1	15.1	17%

The test for keeping a clue is not "is the board still unique" but "can the
rule set still finish it" — which is strictly stronger, because a rule set
that decides every cell has proved uniqueness (every propagator is sound). A
board that is unique but unreachable by propagation leaves the demo's hint
button with nothing to say.

I got that distinction wrong first, pruned for uniqueness only, and then
rejected every board because its post-sweep difficulty came back null. Two
hundred attempts, zero output.

One Tarjan pass instead of a flood fill per candidate

The connectivity propagator asks which still-open cells would strand a white
cell if blackened. The obvious implementation blanks each candidate and redoes
the flood fill — O(cells²) per pass. And it sits inside singleton
consistency, so that factor gets cubed and a 10×10 board simply stops
finishing.

One Tarjan pass answers it for every cell at once: an articulation point of the
not-black graph separates whites exactly when some child subtree holds a white
cell and at least one white cell lies outside it.

board	blunt	Tarjan	speedup	disagreements
6×6, 200 partial boards	11ms	2ms	5.5×	0
10×10, 200 partial boards	52ms	5ms	10.4×	0

The blunt version stays in the test suite as the reference the fast one is
checked against — on 60 random partial boards, with an assertion that at least
one of them actually forced a cell, so the comparison cannot pass by testing
nothing.

Takeaways

• Lift a clue to four bounded integers summing to k−1 and a whole-board counting rule becomes ordinary interval propagation: 8% of cells decided becomes 25–34%.
• "The run is at most hi, so cells[hi] is black" is unsound — the run can stop short and leave that cell outside the clue's view. Found by two independent counters disagreeing with a third.
• Whether a rule looks useless depends on where you measure it. Connectivity is worth one point at fixpoint and takes probing from 8/25 to 25/25 boards finished. Measure a propagator as a refuter, not only as a decider.
• A clue cell here is already white, so adding clues never changes the answer — generation is monotone and terminates for free. The redundancy sweep then removes 17–21% of them.
• Prune against "can the rule set still finish it", not "is it still unique". The former implies the latter and keeps the boards playable.
• Articulation points: one Tarjan pass, not a flood fill per candidate (5.5–10.4×, zero disagreements).

27 tests. Puzzle #29 in the solver series.