Haisu

The number is an ordinal, and whether that is the stronger reading depends on how big the regions are

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. Write 3 and you have said the cell is walked on the third entry — not that there are three entries, and not that there is no fourth. It is easy to read past, and it is easy to test, because the two readings can be laid on exactly the same digits in exactly the same cells.

So that is the experiment: one number per region, dropped on a cell picked at random inside it, read twice. As an ordinal the digit is what Haisu means. As a cardinal it is the region's total visit count — a perfectly sensible rule, just not this one. Same clue sites, same board, same walk underneath. Summed over every row, on 6 × 6 the ordinal reading pins 11 of 720 boards and the cardinal reading 19; on 8 × 8 the ordinal reading pins 0 of 840 boards and the cardinal reading 0.

Neither reading implies the other, so neither should win everywhere, and neither does. The cardinal digit is an equality — it closes the visit count from above as well as below, which the ordinal never does. The ordinal digit is an identification — it says which run of cells this one belongs to, which the cardinal never does. Compared board by board on 6 × 6, where every search finished, the ordinal reading leaves fewer walks more often at 4, 6, 8 regions and the cardinal reading at 10, 14, 18. That is a clean crossover, and a plausible reason for it: few, large regions are visited many times, and naming which visit a cell is on carries more than a total that is usually large and loose; many small regions are visited once or twice, and there "exactly one" or "exactly two" closes the region outright.

On 8 × 8 the ordinal search ran out of its node budget on 416 boards (the cardinal on 0), so that half of the table is not a comparison, only a floor. One number per region is far too few to pin those boards under either reading anyway; the point of the table is the gap, not the level. Walk counts are capped at 80, a capped search counts as "not pinned", and the medians are over boards where both searches finished.

The first run of this table was wrong, and the way it was wrong is worth keeping. The local rung labels each path in a region with the number written on it, which is right for an ordinal and wrong for a total — under the cardinal reading it pinned a cell printed 3 to its region's third visit, which then collided with S (always on visit one) or G (always on the last) and ruled out the real walk, so the cardinal column showed medians of zero walks. The soundness test only ran the real rule. It now runs both readings, and fails on the old code.

Both ends of the region dial carry no information at all

Cut the grid into more regions and there are more numbers to write. That sounds like more information, and for a while it is, but the curve turns over, and the reason it turns over is a small proof rather than a big constant.

A region of one cell is visited exactly once — the line cannot leave it and come back without passing through it twice, which a walk that uses every cell once does not do. So its number is always 1, whatever the walk. Cut the grid into 64 one-cell regions and the board is covered in numbers that are all 1 and all free: 0 of 120 boards were pinned. Cut it into a single region and there is one number, also always 1: 0 of 120. The useful part is in between: with every cell numbered, an 8 × 8 grid is pinned most often at 16 regions (80.8% of boards), a 6 × 6 grid at 8 (91.7%). Past the peak the one-cell regions pile up — the last column — and every one of them is a number that says nothing.

The singleton claim is checked rather than asserted: across 3,799 one-cell regions drawn at random, 0 carried a number other than 1. Rubbing every one of them off 300 fully numbered boards changed the walk count on 0 of them. The generator erases them first for that reason, and the test suite refuses to ship a board that numbers one.

The same argument covers the cell holding S: it is the walk's first cell, so it is on its region's first visit, always — 0 exceptions in 300 drawn boards. A number that cannot rule out any walk might still be a hint, by shortening the proof that only one is left, so that was measured as well: writing the 1 back on S on every shipped board changed the answer count on 0 of 20 and the search-node count on 0. The solver already knows it: the walk starts at S, and the first visit is the first visit.

Two screens that run before the board exists

A walk through every cell alternates checkerboard colours at every step, so a board with an even number of cells needs its two ends on opposite colours and a board with an odd number needs both of them on the majority colour. That kills about half of all endpoint pairs on sight, and it is the first thing the generator asks. On a general graph it would be necessary and not sufficient, so every surviving pair was handed to the exact sweep: on every grid measured here, not one pair passed the colour test and then carried no walk. That agrees with the known result for rectangular grids (Itai, Papadimitriou and Szwarcfiter, 1982): the exceptions live only on grids one, two or three cells thin.

The second screen reads the region map. 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 therefore needs at least d visits — and every visit spends two of the region's border edges, except one that starts at S or ends at G. Put those together and a region has to satisfy 2d - ends ≤ border using nothing but its own shape. It is sound and, on the maps this generator cuts, it never fires: all 60,000 random cuts across the three sizes passed. Grown regions are compact, and a compact region always has border to spare. It stays in because it costs nothing and would catch a long thin region if a different cutter ever produced one.

Both bounds are claims, so they are measured: across 101,429 regions of boards with a real walk drawn on them, 0 had a visit count outside the floor-and-ceiling window.

How big the haystack is, exactly

Strip every number off a Haisu board and the question that is left — how many walks are there from S to G through every cell? — is worth an exact answer rather than an estimate, because it is the size of the set the numbers have to cut down to one. A broken-profile connectivity sweep gives it: cells in row-major order, a frontier of w + 1 plugs, each plug labelled by the path fragment it belongs to.

The genre supplies a free correctness check. Because a cell's degree is fixed the moment the sweep reaches it, the S end and the G end can only be joined at the very last cell of the sweep — join them earlier and every cell after that point finishes untouched. That removes the "is it finished?" bit from the state, and the whole frontier fits in thirteen nibbles, so states are plain numbers.

And three published sequences fall straight out of it, which is a cross-check the code cannot fake. Corner to opposite corner of an odd square is A001184: 2, 104, 111712 — match: yes. Summing over every endpoint pair gives every Hamiltonian path of the square grid, A120443: 4, 20, 276, 4324, 229348 — match: yes. Doubling that is the directed count, A096969 — match: yes.

The boards on this page are the far corner of that: 2,184,565 walks on 8 × 8, 194,570,357,335 walks on 10 × 10, 4.05 × 10^17 walks on 12 × 12. Every one of them is cut to a single walk by the numbers on the board. The 8 × 8 count is exact. The 10 × 10 count is exact. The 12 × 12 count is past 2^53, where a double stops holding every integer, so the sampler's double carries it only approximately and it is shown rounded to three figures.

What each rung costs, and what it saves

The ladder is six rungs, cheapest first. degree is the path itself: two line ends per cell, one at S and one at G, and no step that would close a ring. region counts border crossings — a region visited v times spends exactly 2v - ends of them, so the numbers and the colour bound squeeze that total from both sides. segment reads 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 notices that a cell which has spent both its line ends is not a corridor to anywhere new. probe assumes a step and keeps the contradiction.

local is the one that pays. It solves each region on its own: 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 — and everything the region knows is a filter on that partition. The visit count has to sit inside the border bounds; each path's two loose ends have to pay for a crossing the cell can still afford; the numbers force distinct ordinals onto distinct paths; S begins the first path and G ends the last. Shipped regions average four or five cells, so the whole set of legal partitions can simply be walked, and an edge drawn in every one of them is drawn. It finishes 4 of the 20 shipped boards with no search at all.

The honest column for the cheap rungs is decides something new on. From an empty board reach adds something beyond the rungs under it on 0 of 20 boards — it is dead on move one, sound but idle, and it is kept only because it is cheap and the search calls it on every node, where cells are full and corridors close. region is nearly as quiet on its own; it matters as the bound local leans on. "decided" is the share of gaps settled with no search; "nodes" is the search still needed afterwards, and a figure written ≥ 120,000 is a board that hit the node cap, so it is a floor.

How many numbers a board needs, and how few it can be talked down to

Numbering every cell is not enough on its own — the region-dial table above already shows boards that stay ambiguous with a number in every square — and numbering a tenth of them is hopeless. In between the curve is steep, and it moves right as the grid grows, because the number of walks grows much faster than the number of cells available to carry numbers.

The bank is deliberately not all minimal. Each board starts fully numbered and the generator rubs numbers off, smallest regions first, keeping only removals that leave one walk. On some seeds it runs that to a fixed point — those boards are minimal to the node budget, and the test suite checks that no single number can come off any of them. On the others it stops part-way on purpose, so the page offers dense, gentle boards as well as sparse ones. The 6 minimal boards keep between 19% and 26% of their cells numbered; the part-way boards run all the way up to 91%.

The walks are drawn uniformly, and the bank shows no bend it could detect

The generator does not hunt for a walk with a randomised search. It runs the sweep, then walks forward choosing every move with probability proportional to the number of ways the rest of the board can still be finished — which draws uniformly from all the walks there are. That removes one excuse, and it leaves a second question in plain view.

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 is more information, which ought to make uniqueness likelier. So the right thing to report is three numbers, not two: what the raw sampler draws, what the bank ends up with, and the noise floor of a bank this small.

Here the bank sits inside one sigma of the raw draw on all 3 sizes. That is not evidence that 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 page can measure.