Hiroimono

A single player game in which the player moves on a rectangular grid picking up stones as they are encountered, possibly changing 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 emptying 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 encountered, 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.

▸ ▾ Cite this page

@misc{cog:hiroimono,
    author = "{CoG contributors}",
    title  = "{Hiroimono --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/hiroimono/",
    note   = "[Online; accessed 2024-05-28]"
}