Goishi Hiroi, also known as Hiroimono, is a Japanese variant of
peg solitaire
Peg solitaire, Solo Noble or simply Solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known as solitaire in Britain and as peg solitaire in ...
. In it, pegs (or stones on a
Go board
Go equipment refers to the board, stones (playing pieces), and bowls for the stones required to play the game of Go. The quality and materials used in making Go equipment varies considerably, and the cost varies accordingly from economical to ex ...
) 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
In geometry and trigonometry, a right angle is an angle of exactly 90 Degree (angle), degrees or radians corresponding to a quarter turn (geometry), turn. If a Line (mathematics)#Ray, ray is placed so that its endpoint is on a line and the ad ...
from the previous step.
These puzzles were used for
bar bet
A bar bet is a bet made between two patrons at a bar. Bar bets can range from wagers about little-known trivia, such as obscure historical facts, to feats of skill and strength. Some bar bets are intended to trick the other party into losing.
F ...
s 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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. This can be proved either by a
many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...
from
3-satisfiability
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...
,
[ or by a ]parsimonious reduction
In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions. Informally, it is a bijection between the respective sets of so ...
from the closely related Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...
.
References
{{reflist
Logic puzzles