# 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.

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