Haisu: the number is an ordinal, and I measured what happens when you read it as a total

I built Haisu in the browser with a six-rung solver. The interesting part turned out to be a single word in the rules.

A Haisu number does not say how many times its region is visited. It says which visit the line is on when it stands on that cell. 3 means "this cell is walked on the third entry" — not "there are three entries", and it says nothing at all about whether there is a fourth. That is an ordinal, not a cardinal, and the two readings are incomparable: neither implies the other. So I built both, laid the same digits in the same cells, and counted.

Play it · Source

The rules

• Draw one line from S to G.
• It passes through every cell exactly once.
• The grid is cut into regions.
• A number in a cell says the line is standing on that cell during that region's n-th visit.

That is the whole game. I checked it against the reference implementation rather than against my memory of it, and I am glad I did, because the check in pzprjs is unambiguous about which reading it is:

if (didChangeRoom) {
  curRoom.visit++;
  oldRoom = curRoom;
}
if (this.pid === "haisu" && curCell.qnum > 0 && curCell.qnum !== curRoom.visit) {
  curCell.seterr(1);
  err = true;
}

curRoom.visit is a counter that ticks every time the walk crosses into the region, and the number has to equal it at the moment the walk is on that cell. Ordinal.

The answer is a Hamiltonian path, so count them exactly

Strip every number off a Haisu board and what is left is still a hard question: how many ways are there to walk from S to G through every cell of a w × h grid? That number is the size of the haystack the clues have to cut down to one, and it is worth an exact answer rather than an estimate.

The tool is a broken-profile connectivity sweep. Cells in row-major order; the frontier is w + 1 plugs, each one a half-drawn edge crossing the boundary between decided and undecided ground:

  f[j] for j < c   the edge leaving cell (r, j) downwards
  f[c]             the edge arriving at (r, c) from the left
  f[j] for j > c   the edge leaving cell (r-1, j-1) downwards

A plug's value names the path fragment it belongs to. Fragments with both ends loose carry a paired label written in both plugs. A fragment already nailed down at S carries a single reserved value, one nailed down at G carries another — anchors, at most one of each.

The usual headache in a path (rather than cycle) sweep is tracking whether the S-end and the G-end have already been joined, because joining them completes the answer. Here that bit is free, and the reason is worth stating because it is not about grids at all:

A cell's degree is settled the moment the sweep reaches it. So if the anchors are joined at cell k, every cell after k finishes the sweep with degree zero — untouched, not on the line. Therefore the anchors may only be joined at the very last cell of the sweep.

No "finished" flag, no extra state. The whole frontier fits in thirteen nibbles — 52 bits, exact in a double — so states are plain numbers and the memo is a plain Map<number, T>.

function unpackState(state: number, slots: number, out: Int32Array): void {
  let x = state;
  for (let j = 0; j < slots; j++) {
    const d = x % 16;
    out[j] = d;
    x = (x - d) / 16;
  }
}

That loop is deliberate. Math.floor(state / 16 ** j) is the obvious way to read nibble j, and on a 13-slot frontier it lands within one ulp of a nibble boundary. % 16 on an integral double is exact, and dividing an exact multiple of 16 by 16 is exact, so this version cannot drift.

Three free correctness checks

The sweep is a lot of fiddly transition code, and fiddly transition code is exactly the kind that passes its own tests. So it gets checked against published sequences instead:

• corner to opposite corner of an odd square: A001184
• summed over every endpoint pair — every Hamiltonian path of the square grid: A120443
• the same doubled, which is how OEIS lists the directed count: A096969

All three match. The sweep reproduces 2, 104, 111712 for the 3×3, 5×5 and 7×7 squares corner to corner, and 4, 20, 276, 4324, 229348 for every Hamiltonian path of the 2×2 to 6×6 squares; the test suite pins both, plus a brute-force enumeration of every small grid and endpoint pair.

With that in hand, the haystack for the shipped boards (S in the top-left corner, G as far away as the colours allow):

grid	walks with no numbers at all	frontier states
8×8	2,184,565	16,894
10×10	194,570,357,335	187,904
12×12	4.05 × 10^17	1,961,330

The first two are exact. The 12×12 count is past 2^53, where a double stops holding every integer, so it is shown rounded — the sampler only ever needs ratios of neighbouring counts, which a double carries fine.

Even squares are absent from the first list for a reason that is also the first screen below: on a board with an even number of cells the two corners are the same checkerboard colour, and no walk through every cell can start and end on the same colour.

And the same table is a uniform sampler

The recursion is memoised backwards from the end of the sweep, so memo[pos].get(state) is the number of ways to finish from there. Walk forwards, pick each move with probability proportional to the memo entry it leads to, and the path that comes out is drawn uniformly from all of them:

const opts = moves(w, h, s, g, pos, state);
const weights = opts.map((mv) => sw.memo[pos + 1].get(mv.next) ?? 0);
let t = rnd() * weights.reduce((a, b) => a + b, 0);
let k = 0;
while (k < opts.length - 1 && (t -= weights[k]) >= 0) k++;

So no board in the bank owes its shape to a randomised DFS's habits. That removes one excuse — and exposes a second effect that would otherwise have hidden behind it, which is the last section.

Two screens that run before the board exists

Colour. A walk through every cell alternates checkerboard colours at every step. With an even number of cells the two ends must be on opposite colours; with an odd number, both on the majority colour. That kills about half of all endpoint pairs on sight. On a general graph it would be necessary but not sufficient, so every surviving pair was handed to the exact sweep:

grid	endpoint pairs	pass the colour test	carry a walk (exact sweep)
4×4	120	64 (53.3%)	64
5×4	190	100 (52.6%)	100
5×5	300	78 (26.0%)	78
6×5	435	225 (51.7%)	225
6×6	630	324 (51.4%)	324

Not one pair passed the colour test and then carried no walk. That matches the known result for rectangular grids (Itai, Papadimitriou and Szwarcfiter, 1982): the exceptions only exist on grids one, two or three cells thin.

Shape. Inside one visit the line walks a run of cells, alternating colours, so a run covers a colour imbalance of at most one. A region whose black and white counts differ by d needs at least d visits, and every visit spends two border edges except one that starts at S or ends at G. So each region must satisfy 2d − ends ≤ border from its own shape alone. The honest result: on the maps this generator cuts, it never fires — 60,000 of 60,000 random cuts across 8×8, 10×10 and 12×12 pass. Grown regions are compact, and a compact region always has border to spare. It stays because it is free and sound: across 101,429 regions of boards with a real walk on them, 0 had a visit count outside the floor-and-ceiling window.

Both ends of the region dial carry no information

A region of one cell is visited exactly once: the line cannot leave it and come back without passing through it twice. So its number is always 1, whatever the walk — a number that rules nothing out. The same goes for a single region covering the whole board. Both ends of the dial are dead, and the useful part is in between:

regions (8×8)	every cell numbered: pinned	search capped	walks left (median, finished)	one-cell regions per board
1	0/120 (0.0%)	0	≥ 80	0.0
2	5/120 (4.2%)	0	≥ 80	0.0
4	23/120 (19.2%)	0	4	0.1
6	38/120 (31.7%)	0	2	0.3
8	68/120 (56.7%)	0	1	0.6
12	92/120 (76.7%)	0	1	1.6
16	97/120 (80.8%)	0	1	3.0
24	77/120 (64.2%)	0	1	7.8
32	28/120 (23.3%)	0	2	15.0
64	0/120 (0.0%)	0	≥ 80	64.0

With every cell numbered, 8×8 is pinned most often at 16 regions (80.8%); 6×6 peaks at 8 (91.7%). Past that, the last column takes over.

The singleton argument is checked, not just argued: across 3,799 one-cell regions drawn at random, 0 carried a number other than 1, and rubbing them all off 300 fully numbered boards changed the walk count on 0. The generator erases them first, and the test suite refuses any board that prints one.

The cell holding S is the same story — it is the walk's first cell, so it is always on its region's first visit (0 exceptions in 300 boards). I wondered whether such a number could still act as a hint, shortening the proof even though it excludes nothing. Measured on all 20 shipped boards: writing the 1 back on S changed the answer count on 0 and the search-node count on 0. The solver already knows the walk starts at S.

Ordinal against cardinal, on the very same digits

The experiment: one number per region, on a cell picked at random inside it, read twice. As an ordinal it is Haisu. As a cardinal it is the region's total visit count — a perfectly sensible rule, just not this one. Same sites, same digits, same walk underneath. Walk counts are capped at 80, the search at 120,000 nodes; a board whose search runs out counts as "not pinned", and the medians are over boards where both searches finished.

grid	regions	boards	ordinal pins	cardinal pins	search capped (ord / card)	ordinal walks (median)	cardinal walks (median)
6×6	4	120	2	0	0 / 0	53	79
6×6	6	120	1	1	0 / 0	25	28
6×6	8	120	3	1	0 / 0	16	20
6×6	10	120	1	6	0 / 0	12	10
6×6	14	120	2	5	0 / 0	12	7
6×6	18	120	2	6	0 / 0	15	7
8×8	4	120	0	0	48 / 0	≥ 80	≥ 80
8×8	6	120	0	0	54 / 0	≥ 80	≥ 80
8×8	8	120	0	0	61 / 0	≥ 80	≥ 80
8×8	10	120	0	0	55 / 0	≥ 80	≥ 80
8×8	14	120	0	0	64 / 0	≥ 80	≥ 80
8×8	18	120	0	0	70 / 0	≥ 80	≥ 80
8×8	24	120	0	0	64 / 0	≥ 80	≥ 80

Summed up: on 6×6 the ordinal reading pins 11 of 720 boards and the cardinal reading 19. Those are small numbers — one digit per region is nowhere near enough — so the more telling comparison is board by board: which reading leaves fewer walks? On 6×6, where every search finished, the ordinal wins more boards at 4, 6, 8 regions and the cardinal at 10, 14, 18. A clean crossover.

My first guess had been "the ordinal says more, because it names a run". It does — but only while regions are big. A plausible reading of the crossover: a few large regions are visited many times, and "this cell is on the third visit" pins more than a total that is large and loose; many small regions are visited once or twice, and there "exactly one visit" or "exactly two" closes the region outright, which the ordinal never does. Neither reading implies the other, and the data agrees: neither wins everywhere.

On 8×8 one number per region pins nothing under either reading (0 and 0 of 840), and the ordinal search ran out of nodes on 416 of those boards (the cardinal on 0), so that half of the table is a floor, not a comparison.

The first version of this table measured a bug

The first run said something else entirely: the cardinal reading "won" almost every 6×6 row, with a median of zero walks left on several of them. Zero is impossible — the walk the digits were read from satisfies both readings by construction. The culprit was local. It labels each path in a region with the number written on it, which is exactly right for an ordinal and exactly wrong for a total: under the cardinal reading a cell printed 3 means "this region has three visits", not "this cell is on the third". Read as a label, it pinned the cell to the last visit — and then the cell holding S, which is always on visit one, or G, which is always on the last, could no longer share its path or its region's final slot, and the real answer was ruled out. One line fixes it:

localLabel[i] = p.cardinal ? 0 : p.clue[cells[i]];

The "no rung ever rules against a known answer" test had not caught it for a simple reason: it only ran the real rule. It now runs both readings on the same kept cells, and fails on the old line. An ablation has to be held to the same soundness test as the thing it is compared against, or the comparison measures the bug.

The ladder, and the rung that pays for itself

The solver is six rungs, cheapest first.

• degree — the path itself: two line ends per cell, one at S and one at G, no step that closes a ring.
• region — border crossings. A region visited v times spends exactly 2v − ends of them, where ends counts S and G inside it. That is an arithmetic progression of step two, not an interval, which is worth more than it sounds: it means the parity of the crossings is fixed too.
• segment — the ordinals as labels. Two cells with different numbers can never end up on the same run, so the edge that would join them goes.
• reach — a cell that has spent both its line ends is not a corridor to anywhere new.
• local — see below.
• probe — assume a step, keep the contradiction.

local is the one that pays, and it is the rung none of the counting rules states. A region's traffic is a partition of all its cells into vertex-disjoint paths, one per visit, laid on the region's own internal edges. Everything else the region knows is a filter on that partition:

• the number of paths is the visit count, so it must sit inside the border bounds;
• every path's two loose ends must pay for a border crossing the cell can still afford;
• the numbers force distinct ordinals onto distinct paths — two cells written 2 lie on one path, and a cell written 5 needs four more paths beside its own;
• S begins the first path and G ends the last.

Regions are four or five cells wide on the shipped boards, so the whole set of legal partitions can simply be walked. An edge drawn in every one of them is drawn; a cell that never spends a border crossing in any of them has every border edge ruled out. The rest of the board is never consulted.

const rec = (k: number, edgeCount: number): void => {
  if (k === localEdges.length) { accept(edgeCount); return; }
  rec(k + 1, edgeCount);                                 // leave this edge out
  if (m - edgeCount - 1 >= lo && join(localEdges[k], k)) {
    used[k] = 1;
    rec(k + 1, edgeCount + 1);                           // or draw it
    used[k] = 0;
    part(localEdges[k], k);
  }
};

The bug that taught me to save the undo, not recompute it

Segments inside the enumeration are tracked with the classic endpoint-mate trick: for a cell that terminates a run, mate[cell] is the other end. Joining two runs is two writes. Undoing a join is not, and my first version got it wrong in a way that was quietly catastrophic:

// wrong: after the join, mate[ia] is the stale value the join replaced
const part = (e: number): void => {
  const x = localMate[ib];
  const y = localMate[ia];
  ...
};

The join is precisely what invalidates mate[ia], so recomputing the old ends at part time reads garbage. The enumeration then walked corrupted runs, declared perfectly good regions impossible, and the rung reported a contradiction on boards that had a real answer. Saving the two old ends per depth slot when joining is three extra lines:

localSaveX[slot] = x;
localSaveY[slot] = y;

The reason I caught it at all is a test I write for every solver in this series before writing any of the clever rungs: take a board with a known answer, run each rung from an empty board, and assert that no rung ever contradicts and no rung ever sets an edge against the answer. A sound rung that does nothing is invisible; an unsound rung is invisible too, until it eats a board you cannot check by hand.

Every rung, priced separately on the 20 shipped boards from an empty board:

grid	rung	finished with no search	decides something new on	gaps decided (median)	search nodes left (median)
8x8	degree	0/12	12	8.9%	≥ 120,000
8x8	region	0/12	1	8.9%	≥ 120,000
8x8	segment	0/12	12	25.0%	17,809
8x8	reach	0/12	0	25.0%	17,809
8x8	local	3/12	12	35.7%	2,497
8x8	probe	3/12	7	40.2%	1,361
10x10	degree	0/6	6	5.6%	≥ 120,000
10x10	region	0/6	3	8.3%	≥ 120,000
10x10	segment	0/6	6	16.7%	≥ 120,000
10x10	reach	0/6	0	16.7%	≥ 120,000
10x10	local	0/6	6	66.1%	28,851
10x10	probe	1/6	6	81.7%	24,725
12x12	degree	0/2	2	3.8%	≥ 120,000
12x12	region	0/2	1	8.3%	≥ 120,000
12x12	segment	0/2	2	58.7%	≥ 120,000
12x12	reach	0/2	0	58.7%	≥ 120,000
12x12	local	1/2	2	100.0%	59,577
12x12	probe	1/2	1	100.0%	42,901

local finishes 4 of 20 boards with no search at all, and probe on top of it 5. On 10×10 local takes the share of decided gaps from 16.7% to 66.1% and the median search from the node cap down to 28,851. The other end of the table is the part I would not have seen without pricing: reach decides something new on 0 of 20 boards from an empty start. It is sound, cheap, and dead on move one; it earns its keep, if at all, inside the search, where cells are full and corridors close.

How many numbers a board actually needs

Numbering a random share of cells on boards with a real walk:

cells numbered (random)	8×8 pinned	10×10 pinned	12×12 pinned
10%	0.0%	0.0%	0.0%
20%	0.0%	0.0%	0.0%
30%	0.8%	0.0%	0.0%
40%	9.2%	1.7%	0.0%
50%	12.5%	5.8%	0.0%
60%	33.3%	10.8%	1.7%
80%	58.3%	40.8%	28.3%
100%	79.2%	65.0%	61.7%

Even every cell numbered leaves a fifth to a third of boards ambiguous, and the curve moves right as the grid grows: the number of walks grows much faster than the number of cells available to carry numbers.

The bank is deliberately not all minimal. Every board starts fully numbered and the generator rubs numbers off, smallest regions first, keeping a removal only if one walk remains. On some seeds it runs to a fixed point — those boards are minimal to the node budget, and the tests check that no single number can come off any of them. On the others it stops part-way on purpose, so the page has dense, gentle boards as well as sparse ones:

grid	cells	minimal boards	numbers kept (minimal)	numbers kept (part-way boards)
8×8	64	3	12–14	12–58
10×10	100	2	20–25	40–88
12×12	144	1	38	119

The 6 minimal boards keep 19%–26% of their cells numbered; the part-way boards go up to 91%.

The sampler is uniform; is the bank?

A bank filtered for uniqueness need not be a uniform sample of the genre: a walk that crosses region borders more often leaves more distinct ordinals to write down, which should make uniqueness likelier. So three numbers, not two — the raw draw, the bank, and the noise floor of a bank this small:

grid	visits per region, raw draw (draws)	visits per region, bank	boards in bank	one-sigma noise
8×8	2.066 (3,000)	2.065	12	± 0.061
10×10	2.136 (3,000)	2.174	6	± 0.069
12×12	2.171 (3,000)	2.078	2	± 0.099

The bank sits inside one sigma of the raw draw on all three sizes. That is not evidence the bend is absent — a bank of a dozen boards cannot see an effect smaller than the last column — only that it is smaller than this bank can measure. Without the third column, I would have been tempted to read the 12×12 gap as a finding.

What I would tell you to steal

1. Check the rules against a primary source, not against the name. The ordinal/cardinal distinction is one word in a rulebook and a visible shift in how much a clue is worth — and which reading is worth more flips with region size. Twenty lines of the reference implementation settled it in a minute.
2. If your puzzle's answers are a structured family, count them exactly before you tune anything. The sweep paid for itself three times: an exact haystack size, three OEIS cross-checks the code cannot fake, and a uniform sampler for free.
3. Write the "no rung ever rules against a known answer" test first. It is the only test that catches an unsound propagation rule, and propagation rules are where the interesting bugs live.
4. Price each rung separately. A rung can be sound, shippable, and completely dead, and end-to-end tests will never tell you.
5. Report three numbers, not two, when a filter sits between your sampler and your output. Uniform draw, filtered output, and the noise floor of the sample size you actually have.
6. Hold the ablation to the same soundness test as the real thing. If only one side of a comparison is sound, you are measuring a bug, not a gap. An impossible zero is a reason to stop and look before writing a conclusion.

Everything numeric here is emitted by npm run stats, and the README and the page prose are written out of src/stats.json by npm run notes. No number on this page was typed in by hand.

Play it · Source