Goishi Hiroi

An emptied square and a square that never held a stone are the same thing

Everything below rests on one line of the rules: a stone is gone once you pick it up. A traveller looking down a row cannot tell a square that was cleared from a square that was always bare — both are holes to fly over, and neither lets you turn. So how many ways there are to finish depends on the stones that are left, where you stand and which way you arrived, and not at all on which stones used to be there. One table f(remaining, position, arrival) therefore prices every stone layout on a grid at once, and a layout's answer count is just a sum of lookups into it. That is what makes the exhaustive censuses on this page possible: the 1,048,575 non-empty layouts of a 4×5 board are all counted in 827 ms.

A one-stone board is trivially its own answer, so the last column drops those. It is the interesting column, and on more than half of these grids it reads zero.

A board is a puzzle only if its answer dies when you read it backwards

Take any clearance and run it in reverse. The "never go back the way you came" clause is symmetric in time, so that is not what breaks. What breaks is the holes. Going forward, a move may fly over a stone you collected ten moves ago; going backwards that stone has not been collected yet, and it blocks the way. So a clearance reversed is again a clearance exactly when no move in it ever flew over a square it had already emptied. Call such a clearance clean.

That single sentence decides which boards can be published. If a board's only answer were clean, its reverse would be a second, different answer — so a board with exactly one answer must contain a fly-over. The census checks it rather than taking it on faith: across every layout of the grids below, the number of one-answer boards whose answer is clean is 0.

The shipped boards say the same thing from the other side: every one of them carries at least one fly-over, because it had to. The 8×8 boards average 2.1 of them across 504 moves, which is 10.1% of all moves 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 early, and on a cramped board there is not enough room to arrange one that also kills every other route. The census walks every layout and finds the floor exactly. No board one row deep holds a puzzle at any width up to 12, and none two rows deep at any width up to 10; 3×3 holds none; 3×4 is the smallest grid that holds any, and it holds exactly 12.

There is a second floor, and it does not move. Across every grid measured, no layout of two to six stones has ever had exactly one answer — the smallest genuine puzzle in this game is seven stones, on every grid where one exists at all. Nor does the sweet spot drift: uniqueness peaks near half the squares.

Clearing a board with a stone on every square

Fill the grid completely and the answer count becomes a clean sequence. A single row has exactly two clearances however long it is — start at one end, walk to the other — and those two are each other reversed, which is the whole reversal argument in miniature. Two rows behave much less simply.

The 2×n column satisfies a(n) = 4·a(n−1) − a(n−2) − 6·a(n−3) on every term computed, and the tests re-derive each term from the search rather than from the recurrence. None of these sequences is in the OEIS.

The cheapest clause in the rules is not the cheapest to delete

"You may not go back the way you came" is eight words and looks like a tidying-up rule. Delete it and re-run the whole census: more layouts become clearable, and — the surprise — more layouts end up with exactly one answer, because boards that had no answer at all acquire exactly one. The clause is not mainly a filter on answers; it is a filter on which boards are alive.

The generator cannot sample. It has to climb

There are no clues to place and nothing to minimise here: the board is the stone layout, and moving one stone rewrites every move of the answer. The obvious generator — lay stones down and test — dies fast, and it dies on the stone count rather than on the board size.

So the generator builds the answer first. It walks a route stone by stone; any square the walk flies over that has not been decided yet is banned — it must stay empty forever, or a stone placed there later would block a move already committed to. That yields 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 number of answers, until one is left. On 8×8 with 22 stones, rejection sampling landed a puzzle not once in 1,882 layouts; the climb gets there in a median of 43 answer counts.

The ladder, measured both ways

The hint button runs one of five rungs. line is the rules and nothing else. reach notices that every real move joins two stones sharing a row or a column, so the stones still out there must stay connected in that relaxed graph. dead adds the shape of that graph: what remains has to be walked as a path, so it can afford at most two stones of degree one, and a low-degree stone that does not share a line with where you stand can only ever be the last. probe plays each move and lets the cheaper rungs speak. search is the search itself.

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

Read as pruning, the same rungs are worth the search nodes they delete when proving a shipped board has only one answer.

The shipped boards

The first move of a board has no predecessor, so the turn columns are counted over moves minus boards. Every shipped board opens on exactly one stone, and every one of them carries a fly-over — not by editorial choice but because a board without one cannot have a single answer. The stone you are standing on is also the only thing that tells you where you may go next, which is why the cheap rungs stall around 64% on the largest boards: two thirds of the moves along the answer are forced, and the rest need the search.