Hiroimono

A single player game in which the player moves on a rectangular grid picking up stones as they are encoutnered, possibly changind direction at the stones' locations.

Description

Hiroimono is a single player game played on a rectangular grid. Initially, some of the cells of the grid are empty while others contain a stone.

The player starts by picking up a stone of their choice (thus emptiying the corresponding cell) and moves either horizontally or vertically from the stone’s location until another stone is encountered. Every time that a stone is encoutnered, it is picked up and the player has the option of changing the movement direction by making a 90-degrees turn.

The goal is to find a walk on the grid (i.e., a starting stone, a starting direction, and a sequence of turns) that satisfies the above constraints and picks up all the stones.

Computational complexity

The problem of deciding whether an instance of Hiroimono admits a solution is in NP (a yes-certificate is the order in which the stones are picked up) and NP-hard [1].

The problem remains NP-complete even when 180-degrees turns are allowed and/or when the starting stone is part of the problem instance [1].

References

[1] D. Andersson, “HIROIMONO Is NP-Complete”, in FUN 2007.