Solving Yajilin: clues can pin the shading, but they can never steer the loop

Yajilin in the browser with four rule sets inside. Shade some cells,
then run one closed loop through every cell you did not shade. No two
shaded cells touch. Each black clue sits outside the loop, and its arrow
counts the shaded cells in that direction, all the way to the edge of the
board. Puzzle #28 in the solver series.

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

This is also the entry where the idea I built the whole thing around turned
out to be worthless, and I have the measurements to prove it. Both results up
front:

• What worked was noticing an asymmetry. Clues can pin the shading down; they can never steer the loop's routing. So routing uniqueness cannot be repaired after the fact — it decides the entire design of the generator.
• What did not work was the checkerboard colouring argument. It is true, it is free, it is pretty. Measured, it decides zero extra cells on 0 of 40 boards and refutes 1 wrong guess in 1090.

Two puzzles tangled together — but not symmetrically

In Yajilin a cell is shaded exactly when the loop misses it, so every deduction
about one is a deduction about the other. That much is familiar from
Norinori and
LITS earlier in this series.

What is different here is that the tangle is not symmetric, and it took a
badly behaved generator to make me see it.

A clue cell is off the loop by definition. So adding a clue can take a
cell off the loop. That is the only thing it can do to the loop. It can
never steer the routing.

That has teeth. If the set of cells the loop covers admits two different
Hamiltonian circuits, the board has two solutions — and no amount of extra
clues will ever fix it. Shading ambiguity is fixable by clues. Routing
ambiguity is not. A new clue changes which cells are available, but you cannot
aim it at one circuit and kill it.

Which means routing uniqueness has to be designed into the loop's shape
before a single clue exists.

I did not start there. The first generator did the obvious thing — grow a loop,
split the leftover cells into shaded cells and clues, then add clues until the
board is unique — and it produced 8×8 boards with 24 clues and zero shaded
cells. It was converting shaded cells into clues, over and over, trying to
kill an ambiguity that clues cannot touch, until there was nothing left to
shade.

Growing a loop by inflation

The loop needs to be a random closed circuit. I grow it by inflation: start
from a 2×2 square, the smallest legal loop, then repeatedly take one edge and
push it out into the neighbouring 2×2, replacing that edge with a three-edge
detour through two fresh cells.

 x───y         x       y
               └───┐
 p   q         p───q      (x-y becomes x-p-q-y; p and q join the loop)

This move always leaves one closed circuit. No connectivity check, no
rejection, and the loop grows by exactly two cells each time. Whatever the loop
misses becomes either a shaded cell (a greedy independent subset, since shaded
cells may not touch) or a clue, and the arrow numbers are read straight off the
finished shading.

A freely grown loop essentially never has a unique routing

Grown to 62% coverage, then counting the Hamiltonian circuits the cell set
admits:

board	loops with a unique circuit	median rival circuits
6×6	7/40 (18%)	3
8×8	0/40	52
10×10	0/40	60+ (counting cap)

Zero at 8×8 and above, with a median of 52 rival circuits. No wonder the first
generator ate all the shading: it was fighting an ambiguity it had no weapon
against.

Two attempts to ban it locally, both failed

If the ambiguity has a shape, ban the shape. The obvious culprit is a 2×2
square whose four cells are all on the loop and which the loop enters by two
parallel edges — swap that pair for the other pair and every degree stays at
two, so you may well have a second circuit.

Attempt 1: ban the shape outright during growth. Uniqueness went to 100% —
40/40 at every size. But growth stalls: against a 62% target it reached
21–43%. That leaves most of the board off-loop, and most of that becomes
clues. A 10×10 with 38 clues is not a puzzle. Useless.

Attempt 2: ban only the swaps that really produce a rival. Do the swap, and
if the result is still a single circuit it is a genuine rival; if it splits the
circuit in two it is harmless. Sharper condition, checked at every move. Result
at 8×8: 0/40. It did nothing at all.

The reason is that the property is not monotone. A square whose swap splits
the circuit today becomes a genuine rival after two more inflations somewhere
else. A test applied at move time is worthless by the time the loop is
finished. The shape ban is monotone but kills growth; the effect ban preserves
growth but does not hold. Local conditions do not reach.

Descending the shape itself

That leaves the only honest objective: how many Hamiltonian circuits the cell
set admits, counted for real.

To change the shape without changing the size, pair a deflation with an
inflation. Deflation is exactly the inverse of the growth step: where the
loop runs x-p-q-y and x is adjacent to y, drop p and q and join x
to y. It also preserves the single circuit.

deflate:  x-p-q-y  ->  x-y      (two cells smaller)
inflate:  x-y      ->  x-p-q-y  (two cells larger)

Take a random deflation and a random inflation, keep the pair if the circuit
count did not go up, roll back otherwise. That is the whole thing.

board	reached target size with exactly one circuit	seeds abandoned	time
6×6	40/40	0	54ms
8×8	40/40	0	952ms
10×10	40/40	0	17.9s

0/40 to 40/40, at the target size. Norinori's generator taught me that
hill-climbing on solution count oscillates and never converges; this
objective behaves because it depends only on the loop's shape, with no shading
or clues entangled in it.

Adding clues by looking at the counterexample

With the routing pinned, the only ambiguity left is in the shading — and
clues can fix that.

The first version picked at random: if the board has more than one solution,
turn some random shaded cell into a clue. It works, but it is wasteful, and it
strips the board of nearly all its shading before it happens to hit the cells
that were actually ambiguous.

The fix is to ask the solver for one rival solution and look at the
disagreement. Pick a cell that our solution shades and the rival does not, and
convert that one. The move is guaranteed on both sides:

• it kills this rival — nobody can shade that cell any more
• it leaves our solution standing — the cell was off-loop already, so the loop is untouched

At 8×8 the random version converged on 24 clues and 0 shaded cells. The
counterexample version gives 12–18 clues and 6–12 shaded cells; at 10×10,
21–28 clues and 10–17 shaded. Those are Yajilin-shaped boards.

And now the pretty argument that does nothing

This is the part I most wanted to write.

A grid graph is bipartite. Colour it like a checkerboard and every pair of
adjacent cells differs in colour, so a closed loop alternates colours and
must cover equally many of each.

With W, B the non-clue cells of each colour and sw, sb the shaded counts,
the loop covers W - sw white cells and B - sb black ones, so

W - sw == B - sb    <=>    sw - sb == W - B

and the right-hand side is a constant fixed by the clue positions alone —
known before you shade a cell or draw an edge. A whole-board constraint, for one
O(cells) pass, that no amount of local arrow-counting can see.

I was sure this would carry the entry. Measured:

boards where colouring decided more than the arrows:   0 / 40
mean gap:                                             +0.0 cells
wrong guesses the arrows accept and colouring refutes:  1 / 1090  (0%)

Nothing. Drop it from the strongest rule set and the fixpoint stays at 78%,
unchanged to the point. Look at rule-set reach and arrows and parity are
identical: 30%/30% at 6×6, 32%/32% at 8×8.

Why it does nothing

The algebra shows it. Write the unknown cells that will end up shaded as xw
(0 to uw) on white and xb (0 to ub) on black, and the identity becomes

xw - xb == T        (T a constant fixed by the board)

whose left side ranges over [-ub, uw]. This constraint forces something
only when T sits at one end of that interval — T == uw means every unknown
white cell is shaded and every unknown black one is on the loop, and T == -ub
is the mirror image.

And the interval stays wide until the board is nearly solved. Twenty unknown
cells means an interval about twenty wide, and T landing exactly on an
endpoint is rare. As a contradiction detector it is the same story: one wrong
cell moves T by one, which almost never pushes it outside a wide interval.

True, free, and never tight. That is what 0/40 and 1/1090 are saying.

I locked the result into a test — parity must decide exactly as many cells as
arrows — so that a future change to the propagator in either direction breaks
the build instead of quietly invalidating this article. And it ships in the demo
as the rule set that loses; switch the hint level between arrows and parity
and watch nothing change.

What actually carries the load

Drop one propagator at a time from the strongest fixpoint (6×6, 30 boards):

dropped	free cells still decided
nothing	78%
the arrow counting	47%
shaded-adjacency	62%
the colouring argument	78% (no change)
the loop's structure	39%

It is the loop structure — degrees, dead ends, circuits that would close too
early, cells stranded in an unreachable component. Drop it and 78% falls to 39%.
The puzzle is named after its arrows, but the loop is what breaks it open.

Rule-set reach, measured on boards generated with the uniqueness filter
switched off (filtering by solvability and then reporting solvability is
circular — a trap this series has fallen into before):

board	arrows	parity	loop	probe
6×6 cells decided	30%	30%	67%	100%
8×8 cells decided	32%	32%	66%	100%

Soundness: three counters, and one external sequence

Two brute-force counters share no logic with the propagators:

1. shading first — enumerate the shadings, then count Hamiltonian circuits on whatever cells are left
2. loop first — enumerate the circuit edge by edge, read the shading off as the complement

Plus a propagation-backed counter and an independent validator that re-derives
every rule from scratch. All of them must agree on solution counts.

But agreement between counters I wrote myself does not rule out being wrong in
the same way twice. So the circuit counter is pinned to an external source:
the number of Hamiltonian cycles in an n×n grid graph is published as
OEIS A003763 — 1, 6, 1072 — and the counter
reproduces it exactly. That single test did more for my confidence than the
other twenty-nine combined.

30 tests.

Takeaways

• Clues pin the shading; they can never steer the routing, because a clue cell is off the loop by definition. Routing ambiguity has no post-hoc repair, so it must be built into the loop's shape.
• Freely grown loops are unique 0% of the time at 8×8 and above (median 52 rivals). Two attempts to ban the ambiguity locally both failed — the blunt ban stalls growth at 21–43% coverage, and the sharp one is not monotone.
• Deflate + inflate descent on the real circuit count: 0/40 to 40/40, at target size.
• Add clues by walking counterexamples, not at random: degenerate 0-shaded boards became boards with 6–12 shaded cells.
• The checkerboard colouring argument is correct and worthless: 0/40 boards, 1/1090 refutations, 0% change when removed. It only bites at the ends of an interval that stays wide. Pinned by a test; shipped as the losing rival.
• Pin at least one counter to a published sequence, not just to another counter you wrote.

Puzzle #28 in the solver series.