Ripple Effect: the rule that matters most never shows up in the difficulty rating

Ripple Effect (also sold as Hakyuu and 波及効果) in the browser with
five rule sets inside. Every outlined region of s cells holds 1 to s,
each exactly once. And the rule it is named for: if the same value k shows up
twice in one row or one column, the two cells must be more than k apart — a
1 needs one clear cell between them, a 5 needs five. Puzzle #30 in the solver
series.

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

Three things came out of this one, and only the first was on the plan.

• A row is not one constraint graph. It is a different graph for every value you might place in it.
• Most boards do not exist. 87% of randomly drawn region partitions have no solution at all, before a single number is written.
• The rule I was proudest of never appears in a difficulty rating. It is worth one percentage point to the solver and everything to the generator.

A row is not one graph, it is one graph per value

In Sudoku a row is an all-different clique. Nine cells, all mutually exclusive,
and that stays true whichever digit you happen to be holding. Every propagator
you write can take "the row" as a fixed object.

Here the row is a different object for every value. Two equal values k must sit
more than k apart, so the row splits into overlapping windows of width k+1 —
and the window depends on k. The conflict graph for 1s is just the grid's own
adjacency graph. The graph for 5s is eleven cells wide. They share no edges
beyond the trivial ones. One board carries as many line-conflict graphs as it has
distinct values.

So the reach function takes the value as an argument, and this is the entire
puzzle in six lines:

export function rippleReach(k: number, v: number, n: number): number[] {
  const r = rowOf(k, n), c = colOf(k, n);
  const out: number[] = [];
  for (let d = 1; d <= v; d++) {
    if (c - d >= 0) out.push(k - d);
    if (c + d < n) out.push(k + d);
    if (r - d >= 0) out.push(k - d * n);
    if (r + d < n) out.push(k + d * n);
  }
  return out;
}

There is no such thing as "the cells k conflicts with". Only "the cells k
conflicts with when it holds a 4".

Measured on an empty board — the mean number of cells a single placed v
forbids, against how many v's the whole board can hold at once:

board	v=1	v=2	v=3	v=4	v=5
6×6	deg 3.3, room 18	deg 6.0, room 12	deg 8.0, room 12	deg 9.3, room 12	deg 10.0, room 6
8×8	deg 3.5, room 32	deg 6.5, room 24	deg 9.0, room 16	deg 11.0, room 16	deg 12.5, room 16
10×10	deg 3.6, room 50	deg 6.8, room 40	deg 9.6, room 30	deg 12.0, room 20	deg 14.0, room 20

The two halves pull opposite ways, and the tension between them is where the
puzzle lives. A big value reaches far but turns up rarely — only a region of size
v or more ever holds a v. A 1 barely reaches at all, but every region
owns one, so 1s are the most crowded thing on the board.

Where the counting arguments can and cannot live

I wrote this in the header of the solver on day one:

Every counting argument here is region-scoped, because a region must hold
each of 1..s while a row promises nothing at all.

The first half is right. A region of size s has to contain a 3 if s ≥ 3, so
"only one cell in this region can still take a 3" pins that cell — the ordinary
hidden single. A row has no such duty. A row of a Ripple Effect board need not
contain a 3 anywhere, so there is no line-scoped hidden single, and I concluded
there was nothing to count along a line.

That is wrong, and the region partition is what makes it wrong.

A region that lies entirely inside one row promises that row a 1, and a 2, and
so on up to its size. Trapped regions are disjoint, so their demands add. On
the supply side, the ripple rule caps how many v's fit in n cells at
⌈n/(v+1)⌉. Demand against capacity, per line, per value — a line-scoped counting
argument after all, and the only place where the region-scoped "must contain" and
the line-scoped "must be far apart" ever meet.

It prunes, too, not just refutes. If a line owes need copies of v, then a
cell that cannot be part of any packing of at least need copies cannot hold v:

for (const i of spots) {
  let best = 1;
  const left: number[] = [], right: number[] = [];
  for (const j of spots) {
    if (i - j > v) left.push(j);
    else if (j - i > v) right.push(j);
  }
  best += maxPacked(left, v) + maxPacked(right, v);
  if (best < need && !strike(b, line.cells[i], v)) return false;
}

maxPacked is greedy left-to-right, which is optimal here for the usual
interval-scheduling reason. A worked case, with no givens on the board at all:
row 0 holds two 1×3 regions, so it owes two 3s, and a row of 6 has room for
exactly two — they must sit four apart. Columns 2 and 3 are in no such pair, so
neither can hold a 3, and the rule says so from an empty grid.

Most boards do not exist

Take the same argument global. Every region of size ≥ v spends exactly one v,
those regions are disjoint, and each of the n rows holds at most ⌈n/(v+1)⌉ of
them. Cut a 6×6 board into eighteen dominoes and it is over: eighteen regions
want a 2 and the board has room for twelve. No numbers, no givens, no solution.

The smallest case in the whole family is prettier still — two size-1 regions
sitting orthogonally adjacent. A size-1 region is a forced 1, so that is two 1s
one step apart, and 1s need a gap.

Which made me wonder how often a random partition survives any of this. The
answer is: rarely. The solver is the ground truth here, and I brute-force
verified a sample of the verdicts with a counter that enumerates region
permutations, because "most of your boards are impossible" is exactly the kind of
claim that is usually a bug.

board	size-1 share	dead	adjacent singletons	board capacity	line rule	any of them
6×6	5%	85%	31%	0%	8%	33%
6×6	12%	87%	56%	0%	13%	62%
6×6	25%	100%	90%	10%	48%	93%
6×6	40%	100%	98%	32%	67%	98%
8×8	12%	88%	66%	0%	4%	66%
8×8	40%	100%	100%	10%	60%	100%
10×10	12%	93%	84%	0%	0%	84%

Read the middle 6×6 row: 87% of partitions are dead; the adjacent-singleton test
explains 56% of the corpses, the line rule another handful, and 38% of them are
dead for reasons no static test I have catches. Across every row, the cheap
tests never once killed a partition that had a solution.

At 10×10 it is worse: 93% dead, and the counting tests stop explaining any of it.

This is a genuinely different shape from the other puzzles in this series. In
Kurodoko or Yajilin you paint a legal board first and the skeleton comes along
for free. Here the skeleton is chosen blind and is usually a corpse, and the
generator's real job is drawing skeletons until one is alive.

The prefilter that made things slower

Obvious next move: the solver is expensive, the counting tests are arithmetic, so
skip the solver on partitions that are obviously hopeless. Free speed.

It is not free. Median of 5 trials, order alternated to cancel warm-up:

board	live / drawn	solver only	with prefilter	speedup
6×6	40 / 396	35 ms	44 ms	0.80×
8×8	20 / 312	753 ms	760 ms	0.99×

Slower at 6×6, indistinguishable at 8×8. The premise was wrong. A dead partition is dead for reasons the ordinary
propagators hit within a round or two, so the solver refutes it almost
immediately — there is no expensive search to skip. Meanwhile the "cheap" test
rebuilds the line structures for every candidate, which is the most expensive
thing in the loop.

There is a second lesson buried in that table, and it cost me an hour. The first
version of this measurement took one sample per configuration, and on two
consecutive runs it read 0.4× and 2.4× — the second one while a test suite was
running on the same machine. I had already written the "it is negative" paragraph
around the first sample. A timing claim from a single shot is not a measurement;
it now takes five, alternates the order, and reports a median, and the honest
answer turns out to be "no difference worth having" rather than the more dramatic
thing I nearly published.

So the prefilter came out of the generator. looksDead stays in the codebase
because it answers a different question — it says why a partition is dead, one
named reason at a time, which is what the mortality table above is made of. It is
not there to save time, because it doesn't.

The strongest rule never shows up in a difficulty rating

Five rule sets, each strictly containing the one below:

name	what it adds
region	a region of size s holds 1..s, once each
ripple	a placed v erases v within v steps along the row and column
hidden	a value with only one seat left in its region takes it
lines	demand from trapped regions against the line's capacity
probe	singleton consistency: assume a value, propagate, watch it die

Reach, measured on boards carrying the same number of givens as the shipped banks
but never filtered for solvability, so the last column is not circular. Each
cell reads surplus candidates eliminated / boards finished outright:

board	region	ripple	hidden	lines	probe
6×6 (N=40)	15% / 0%	52% / 0%	63% / 5%	63% / 5%	82% / 13%
8×8 (N=25)	18% / 0%	56% / 0%	64% / 0%	64% / 0%	81% / 0%

lines adds nothing. Not "a little" — the columns are identical. The ablation
says the same thing from the other direction, dropping one propagator at a time
from the strongest fixpoint over 30 solvable 6×6 boards:

dropped	candidates eliminated	boards finished
nothing	100%	30/30
region	97%	27/30
ripple	16%	0/30
hidden	67%	10/30
lines	99%	29/30

One percentage point and one board. And not a single board in the shipped bank of
48 is labelled lines — they come out as ripple or hidden, every time.

The rule with the sharpest argument behind it, the one that took the most care to
get right, is dead weight to the solver. Its entire contribution is upstream, on
the skeleton, deciding which boards get to exist at all. By the time a board has
givens on it, the cheaper rules have already been everywhere it would go.

The lesson I am taking from it: a difficulty rating measures the solver, and a
solver is only one of the two consumers of a rule. A rule can be load-bearing
for the generator and worthless for the player, and nothing in the difficulty
column will ever tell you which. If I had only ever measured rule sets the usual
way — reach on finished boards — I would have deleted lines as dead code and
never found out that it is the thing that explains why most boards do not exist.

Meanwhile the eponymous rule is exactly as important as the name suggests:
without ripple the solver eliminates 16% of the candidates and finishes nothing
at all.

Generation: one monotone knob and one that isn't

The givens are the pleasant half. A given is written on a cell whose value the
intended solution already fixes, so adding one cannot change the solution — it
can only remove rivals. Termination is free: in the worst case every cell becomes
a given and the board is pinned by construction. Size-1 regions are kept out of
the pool, since a given there would only repeat what the partition already says.

Then the walk runs backwards and drops every given that is not pulling its weight.
The test is not "is it still unique" but "can the rule set still finish it", which
is strictly stronger — every propagator here is sound, so a rule set that decides
every cell has also proved the board unique. The sweep removes 43–48% of them.

The partition has no such courtesy. It is monotone in nothing, it is usually
dead, and the only thing to do with a dead one is throw it away whole.

Cross-checking

Three counters, and any unsound propagator shows up as a disagreement:

• by cells — walk the grid in row-major order, trying every value a cell could hold
• by regions — hand each region a permutation of 1..s at a time
• with propagation — the rule sets plus search

The first two enumerate opposite halves of the problem and share nothing but the
geometry helpers. validate re-reads the distance rule from scratch by brute
force over every ordered pair in every line, and shares no code with the
propagators at all. The soundness tests take boards with known solutions, run each
propagator, and insist the solution's value survived in every cell — which is the
property that makes "finished without search" a uniqueness certificate rather than
a guess that happened to work.

34 tests. Puzzle #30 in the solver series.

npm install
npm run dev        # demo at http://localhost:5173
npm test
npm run generate   # rebuild the bank
npm run stats      # every number in this post

MIT. No runtime dependencies.