Open AccessHIROIMONO is NP-complete
Author(s) -
Daniel Andersson
Publication year - 2007
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v14i1.21924
Subject(s) - grid , square tiling , set (abstract data type) , square (algebra) , mathematics , computer science , np complete , combinatorics , algorithm , geometry , time complexity , programming language
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.