Goishi Hiroi

Goishi Hiroi, also known as Hiroimono, is a Japanese variant of peg solitaire.

In it, pegs (or stones on a Go board) are arranged in a set pattern, and the player must pick up all the pegs or stones, one by one.

Additionally, it is not possible to reverse direction along a line: each step from one position to the next must either continue in the same direction as the previous step, or turn at a right angle from the previous step.

[3] Determining whether a given puzzle can be solved is NP-complete.

This can be proved either by a many-one reduction from 3-satisfiability,[1] or by a parsimonious reduction from the closely related Hamiltonian path problem.

Solving a Goishi Hiroi puzzle
1. An example with a fixed first stone.
2. A failed attempt: as U-turns are not allowed, the top-right stone must be the last stone.
3. A failed attempt: as stone 4 is removed on passing it, there is nowhere to go from stone 7.
4. The unique solution, even if stone 1 is not fixed.