Goishi Hiroi: a board can only be a puzzle if its answer dies when you read it backwards

Goishi Hiroi in the browser with a five-rung solver. Start on any
stone and travel in a straight line; you must pick up the first stone you
meet, you may turn on a stone but never go back the way you came — and a
stone is gone once you collect it. That last clause decides everything.
To a traveller, a square you emptied and a square that never held a stone are
the same hole. So how many ways there are to finish depends only on
(stones left, where you stand, how you arrived), and not at all on which
stones used to be there. Two things follow. (1) One table prices every
stone layout on a grid at once, so all 1,048,575 non-empty layouts of a
4×5 board are counted in 827 ms. (2) The puzzle is not symmetric in
time — forwards you may fly over a stone collected ten moves ago, backwards
that stone is still sitting there. So a clearance read backwards is legal
exactly when it never flew over a square it had already emptied, and
therefore a board with exactly one answer must contain such a fly-over.
Measured, not assumed: across every layout of the grids up to 3×4 and
120,000-layout samples at 4×4 and 4×5, the count of one-answer boards whose
answer survives reversal is zero. The same fact starves small boards:
no one-row board up to width 12, no two-row board up to width 10 and no 3×3
board holds a genuine puzzle at all. 3×4 is the smallest that does, and it
holds exactly 12. 57 tests.

Live: https://sen.ltd/portfolio/goishi-hiroi/
Source: https://github.com/sen-ltd/goishi-hiroi

The rules

Goishi Hiroi is a Nikoli puzzle. I read Nikoli's own page as the primary source before writing any code. The whole thing is four sentences:

Start on any stone and travel along the grid lines, horizontally or vertically, until every stone has been picked up.
If the square you move onto has no stone, you keep going straight.
If it has a stone you must pick that stone up. There you may change direction, but you may not go back the way you came.
A stone is gone once picked up, so passing over a square you have already emptied does not let you turn there.

Four sentences, and not a single number on the board. The clue is the stone layout, and nothing else is written anywhere. Every other puzzle in this series works by printing symbols that narrow the grid down. Here there is nothing to print — which also means the whole business of minimising clues is unavailable. More on that later.

One of the shipped 6×6 boards (o is a stone, the right half is the answer):

  the board                 the order

   .  o  o  o  .  .         .  5  6  7  .  .
   .  .  .  .  .  .         .  .  .  .  .  .
   o  .  o  .  .  .        11  . 10  .  .  .
   o  o  o  .  o  .        12  4  3  .  2  .
   .  .  .  .  o  .         .  .  .  .  1  .
   o  .  o  o  .  o        13  .  9  8  . 14

Look at move 9 → 10. Stone 9 is in the bottom row, column 3; stone 10 is in row 3, column 3. The route travels up that column — and row 4, column 3 held stone 3, which is already gone. It is a hole now. Move 14 does the same thing, flying over 9 and 8 along the bottom row.

An emptied square and a square that never held a stone

This is where all of it comes from. The fourth rule is written as a restriction on turning, but read from the state-space side it says something else entirely.

When you look down a row to find your next stone, you are looking at the remaining stones. A square you emptied and a square that never had anything on it are both just squares you pass over, and they are indistinguishable.

So the number of ways to finish from any position is

f(set of remaining stones, square you are on, direction you arrived from)

and which stones used to be there does not enter the state. That is not automatic — if the rule had been "you may not pass over a square you emptied", the board's history would leak into the state and this would fail. Nikoli's rule, deliberately or not, is shaped so that the game forgets its own past.

Consequence 1: one sweep prices every layout at once

If f does not depend on the original layout, then every stone layout on a grid shares the same table. Run the mask (the bit set of remaining stones) from 0 upward: every dependency drops exactly one bit, so plain increasing numeric order is already a topological order.

for (let mask = 1; mask < 1 << cells; mask++) {
  for (let pos = 0; pos < cells; pos++) {
    if (mask & (1 << pos)) continue;   // you are standing where you just picked up
    let total = 0;
    for (let d = 0; d < 4; d++) {
      const t = firstIn(rays, mask, pos, d);   // first remaining stone that way
      if (t < 0) { hd[d] = 0; continue; }
      const v = f[(((mask ^ (1 << t)) * cells + t) * 5) + d + 1];
      hd[d] = v; total += v;
    }
    f[(mask * cells + pos) * 5] = cap(total);                  // no arrival yet
    for (let d = 0; d < 4; d++)
      f[(mask * cells + pos) * 5 + d + 1] = cap(total - hd[(d + 2) % 4]);
  }
}

"The first remaining stone that way" is an AND with a precomputed ray mask followed by a lowest- or highest-set-bit — right and down walk towards higher indices (m & -m), up and left towards lower (31 - Math.clz32(m)). The inner loop is branch-light.

Once the table exists, a layout's answer count is Σ_{stone s} f(layout \ {s}, s, no arrival) — |stones| lookups. Build the table once and the whole grid is priced.

grid	stone layouts	can be cleared	exactly one answer	genuine puzzles (≥2 stones)	sweep
2x10	1,048,575	612,069 (58.4%)	20	0	761 ms
3x4	4,095	2,718 (66.4%)	24	12	1 ms
3x5	32,767	21,788 (66.5%)	275	260	10 ms
3x6	262,143	177,437 (67.7%)	3,582	3,564	99 ms
4x4	65,535	44,571 (68.0%)	416	400	25 ms
4x5	1,048,575	751,237 (71.6%)	10,316	10,296	738 ms

A one-stone board is trivially its own answer, so the last column drops those. That column is the subject of this article, and across the top half of the table it reads zero.

Consequence 2: the game is not symmetric in time

Read a clearance backwards. The "never go back the way you came" clause is symmetric in time, so it is not what breaks. What breaks is the holes.

Forwards, a move may fly over a stone you collected ten moves ago. Backwards, that stone has not been collected yet and it sits there blocking the way. Equivalently:

A clearance read backwards is again a clearance exactly when no move in it ever flew over a square it had already emptied.

Call such a clearance clean. And now the publishing condition falls out. If a one-answer board's only answer were clean, its reverse would be a second, different answer (for two stones or more, a sequence never equals its own reverse). Therefore:

A board with exactly one answer must contain a move that flies over a square it has already emptied.

Not assumed — counted. Counting clean clearances is the one thing the shared table cannot do, because "did it fly over a stone" needs the original layout, so that census runs per board.

grid	layouts examined	clearable	one answer	has a clean answer	all answers clean	one answer, and clean
2x4	247	175	0	175 (100.0%)	147 (84.0%)	0
2x5	1,013	681	0	681 (100.0%)	545 (80.0%)	0
2x6	4,083	2,629	0	2,629 (100.0%)	2,033 (77.3%)	0
3x3	502	343	0	339 (98.8%)	271 (79.0%)	0
3x4	4,083	2,706	12	2,616 (96.7%)	1,996 (73.8%)	0
4x4 (120k sampled)	119,979	81,431	752	75,327 (92.5%)	58,753 (72.2%)	0
4x5 (120k sampled)	120,000	86,196	1,165	76,618 (88.9%)	62,011 (71.9%)	0

The rightmost column is zero everywhere. The shipped boards say it from the other side: all 72 of them carry at least one fly-over, not by editorial taste but because a board without one cannot be unique. The 8×8 boards average 2.1 fly-overs across 504 moves — 10.1% of every move made.

Which is why small boards hold no puzzles at all

A fly-over needs three stones in a line and a route that collects the middle one first. On a cramped board there is not enough room to build one and kill every other route. The exhaustive census finds the floor exactly.

• One row: zero genuine puzzles up to width 12. Obvious in hindsight — a single row has exactly two clearances, left-to-right and right-to-left, and those two are each other reversed. The whole argument in miniature.
• Two rows: zero up to width 10. In every two-row grid counted exhaustively, every clearable layout had a clean answer (the 100.0% column above).
• 3×3: zero.
• 3×4: exactly 12. The smallest grid in the game that holds a puzzle at all.

There is a second floor, and it does not move with the grid. Across every grid measured, no layout of two to six stones has ever had exactly one answer. The smallest genuine puzzle is always seven stones.

grid	stones in the smallest puzzle	stone count with the most puzzles	puzzles there	share of clearable layouts there
3x4	7	7 of 12	12	1.83%
3x5	7	8 of 15	120	2.52%
3x6	7	9 of 18	1,128	3.38%
4x4	7	8 of 16	192	2.17%
4x5	7	10 of 20	3,464	2.45%

The sweet spot is about half the squares, and it barely drifts as the grid grows.

Boards with a stone on every square

Fill the grid and the answer count becomes a clean sequence.

grid	ways to clear it	grid	ways to clear it
2x2	8	1x2	2
2x3	20	1x3	2
2x4	60	1x4	2
2x5	172	1x8	2
2x6	508	1x16	2
2x7	1,500	3x3	64
2x8	4,460	3x4	400
2x9	13,292	3x5	2,004
		3x6	11,936
		4x4	6,984

1×n is 2 whatever the width, for the reason above. Fitting a linear recurrence to the first eight terms of the 2×n column gives

a(n) = 4·a(n−1) − a(n−2) − 6·a(n−3)

which at that point is only suggestive — three unknowns fixed by three equations and checked against two more. So I computed 2×9 outright (18 squares, 189 MB of Float64Array): 13,292, exactly the recurrence's prediction of 4·4460 − 1500 − 6·508. The tests re-derive every term from the plain search rather than from the recurrence.

None of these sequences is in the OEIS — not 2, 8, 20, 60, 172, 508, 1500, 4460, not the puzzle counts 12, 260, 3564, not 64, 400, 2004.

Deleting the eight cheapest words in the rules

"…but you may not go back the way you came." It reads like tidying-up. Delete it and re-run the whole census.

grid	clearable, real rules	clause deleted	one answer, real rules	clause deleted	unique under both
3x4	2,718	3,259 (+19.9%)	24	232	12
3x5	21,788	27,274 (+25.2%)	275	1,351	15
3x6	177,437	227,637 (+28.3%)	3,582	6,522	18
4x4	44,571	54,427 (+22.1%)	416	2,928	112
4x5	751,237	917,043 (+22.1%)	10,316	29,980	1,444

Relaxing a restriction should add answers, and clearable layouts do rise by a fifth to nearly a third. The surprise is that one-answer layouts rise too — 3,582 to 6,522 on 3×6 — because boards that previously had no answer acquire exactly one. And the "unique under both" column is small: of the 10,316 one-answer 4×5 boards, only 1,444 survive the change.

The clause is not mainly a filter on answers. It is a filter on which boards are alive.

The generator: no clues to place, so nothing to minimise

The board is the stone layout, and moving one stone rewrites every move of the answer. The loop this series usually runs — derive an answer, cover it with clues, strip clues until they are minimal — has nothing to bite on.

The naive alternative is to scatter stones and count. That dies, and it dies on the stone count rather than on the board.

grid	stones	layouts tested	exactly one answer	hit rate
6×6	8	1,438	28	1.95%
6×6	10	2,044	29	1.42%
6×6	12	2,541	16	0.63%
6×6	14	2,947	3	0.10%
6×6	16	3,237	2	0.06%
6×6	18	2,594	0	0.00%
8×8	14	2,232	10	0.45%
8×8	18	2,210	1	0.05%
8×8	22	1,882	0	0.00%

Read the table down: on 6×6, 1.95% at eight stones becomes 0.06% at sixteen — a factor of 32 for eight stones. Read it across: at the same fourteen stones, 8×8 (0.45%) beats 6×6 (0.10%). It is the stone count that kills the hit rate; enlarging the board actually helps. At the 8×8, 22-stone size I wanted to ship, 1,882 layouts produced nothing.

So the generator builds the answer first.

Walk a route stone by stone. Whenever the walk flies over a square that has not been decided yet, that square is banned — it must stay empty forever, because a stone placed there later would block a move already committed to. Squares the walk has already collected are free to fly over, and those fly-overs are exactly what a one-answer board needs.

while (inside the board) {
  if (used[i] >= 0) ghost = true;        // already collected: free to fly over
  else if (banned[i]) { /* known to stay empty */ }
  else {
    out.push({ to: i, dir: d, ban: ban.slice(), ghost });  // this can be the next stone
    if (ban.length >= maxBan) break;
    ban.push(i);                          // pass over it and it is empty forever
  }
  step on;
}

That gives a layout that is at least clearable. Then a hill-climb relocates one stone at a time, keeping any move that does not raise the (capped) answer count, until one answer is left.

shipped board	stones	answer counts spent	relocations kept	restarts needed
6x6	14	median 17, worst 141	median 6	median 1
8x8	22	median 43, worst 137	median 11	median 1
10x10	30	median 99, worst 177	median 38	median 1

The size that rejection sampling failed to hit in 1,882 tries, the climb reaches in a median of 43 answer counts.

Pricing the ladder twice

The hint button runs one of five rungs.

• line — the rules, and nothing else.
• reach — every real move joins two stones sharing a row or a column. Whatever sits between them may be collected first, so the row/column graph with blockers ignored is a relaxation of the real moves, and the remaining stones must stay connected in it.
• dead — the shape of that relaxed graph. What remains has to be walked as a single path, so it can afford at most two stones of degree one; and since the next stone must share a line with where you stand, a low-degree stone that does not can only ever be the last one — and there can be at most one of those.
• probe — play each move, then let the cheaper rungs speak.
• search — the search itself.

Read forwards, a rung is worth the share of moves along the answer where it leaves exactly one legal move.

rung	6x6	8x8	10x10
line	66.7%	59.9%	59.1%
reach	72.8%	65.7%	61.9%
dead	73.7%	67.5%	63.5%
probe	80.4%	71.6%	65.7%
search	100.0%	100.0%	100.0%

Even on 10×10, nearly 60% of the moves are forced by the rules alone: with no numbers to read, where you are standing is effectively the entire clue. But stacking rungs on top only reaches 65.7% — a third of the moves genuinely need search.

Price the same rungs as pruning and the picture changes a lot.

rung	6x6 median	8x8 median	10x10 median	10x10 worst
line	2,078	64,029.5	1,400,855	3,329,017
reach	326.5	7,443	78,181.5	229,632
dead	241.5	4,759	40,897.5	138,990
probe	169	3,445	29,568.5	101,477

A ladder that earns only 6.6 percentage points as a proof device turns 1.4 million nodes into 30 thousand as a pruner — a factor of 47, with reach alone worth 18× of it. Row-and-column connectivity says almost nothing to a player and deletes most of the search tree.

The shipped boards

board	boards	stones	moves	turned 90°	carried straight on	fly-overs	longest single move	stones that can open it
6x6	24	14	312	201 (69.8%)	87	median 1, max 2	median 4.5, max 5	1–1
8x8	24	22	504	330 (68.8%)	150	median 2, max 4	median 6, max 7	1–1
10x10	24	30	696	436 (64.9%)	236	median 3, max 8	median 8, max 9	1–1

Every board opens on exactly one stone. Even on a 10×10 board with thirty stones, twenty-nine of them lose immediately. Finding the first move is the puzzle's first real gate, which is why the search rung on the page will name it for you and the cheaper rungs decline to.

Implementation notes

• Five slots, not four. f(mask, pos, dir) needs a "no arrival yet" slot alongside the four directions; index with (mask * cells + pos) * 5 + dir + 1. At 20 squares that is 2^20 × 20 × 5 = 105 MB of Uint8Array.
• Why capped subtraction is still exact. Each direction's contribution h_d is capped, summed into S, and the value for arrival dir comes out as S − h_{opposite(dir)}. That looks unsafe, but Σ_{i≠opp} min(h_i, CAP) equals the true sum when the true sum is below CAP and is at least CAP otherwise — so a final min(·, CAP) is exactly right.
• The clean census is per board. "Did this move fly over a stone" needs the original layout, so the shared table does not apply; the DP allows only moves where firstIn(remaining, pos, d) === firstIn(original, pos, d). That is why the reversal census is exhaustive up to 3×4 and honestly labelled as sampled at 4×4 and 4×5.
• A budget-exhausted completable returns true. Returning false when the node cap is hit would wrongly declare a live move dead. Claiming nothing is the safe failure.
• The climb scores with the real answer count. A proxy would lie, so every candidate is actually counted, capped at 64 / 28 / 16 by size. A higher cap gives a smoother gradient and a much more expensive evaluation.
• Every number here comes from counts.json / stats.json; the README and page tables are emitted by tools/notes.mts, so nothing is transcribed by hand. The tests re-derive, for each of the 72 shipped boards, that the answer is legal, that it is the only one, that it contains at least one fly-over, that it is illegal when reversed, and that exactly one stone can open the board — 57 tests in all.

Takeaway

Goishi Hiroi has no numbers. The clue is the stone layout, there is nothing to place and nothing to strip. And yet — or rather, because of that — it is a rare genre where the condition for being a publishable puzzle fits on one line.

• Emptied and never-occupied squares are indistinguishable, so the state closes into a triple and one table prices every layout at once.
• The same fact breaks time symmetry: a clearance reverses exactly when it never flew over a square it had emptied.
• Therefore a one-answer board must contain a fly-over — and the absence of any puzzle on one-row boards, two-row boards and 3×3, and the existence of exactly twelve on 3×4, are all consequences of that single line.

It is unusual to find a puzzle where "the answer must be unique" translates so directly into the geometry of the board.

Live: https://sen.ltd/portfolio/goishi-hiroi/
Source: https://github.com/sen-ltd/goishi-hiroi