Goishi Hiroi

rdf:langString Goishi Hiroi

rdf:langString 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.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. These puzzles were used for bar bets in 14th-century Japan,and a collection of them was published in a Japanese puzzle book from 1727. Determining whether a given puzzle can be solved is NP-complete. This can be proved either by a many-one reduction from 3-satisfiability, or by a parsimonious reduction from the closely related Hamiltonian path problem.