|
HIROIMONO is NP-complete
Daniel Andersson January 2007 |
Abstract:
In a Hiroimono puzzle, one must collect a set of stones from a
square grid, moving along grid lines, picking up stones as one encounters
them, and changing direction only when one picks up a stone. We show that
deciding the solvability of such puzzles is NP-complete
Available as PostScript, PDF. |