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.

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]

References

1. Andersson, Daniel (2007), "HIROIMONO Is NP-Complete", in Crescenzi, Pierluigi; Prencipe, Giuseppe; Pucci, Geppino (eds.), Fun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4475, Springer, pp. 30–39, doi:10.1007/978-3-540-72914-3_5, ISBN 978-3-540-72913-6
2. Costello, Matthew J. (1988), The Greatest Puzzles of All Time, Dover books on mathematical & logical puzzles, cryptography and word recreations, Courier Corporation, pp. 9–10, ISBN 9780486292250
3. Tagaya, K. (1727), Wakoku Chie Kurabe. As cited by Fukui, Suetsugu & Suzuki (2017).
4. Fukui, Masanori; Suetsugu, Koki; Suzuki, Akira (2017), "Complexity of "Goishi Hiroi"", (PDF), pp. 142–143, archived from the original (PDF) on 2017-09-12, retrieved 2017-09-11