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. In some variants, the choice of the first stone is fixed, while in others the player is free to choose the first stone.^[1] After the first stone, each stone that is removed must be taken from the next occupied position along a vertical or horizontal line from the previously-removed stone. 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.

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.

These puzzles were used for bar bets in 14th-century Japan,^[2] and a collection of them was published in a Japanese puzzle book from 1727.^[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.^[4]