
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

NPHardness of Rotation Type CellMazes
Shiro AOKI Hiro ITO Hideyuki UEHARA Mitsuo YOKOYAMA Tsuyoshi HORINOUCHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.3
pp.492496 Publication Date: 2000/03/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section LETTER (Special Section of Selected Papers from the 12th Workshop on Circuits and Systems in Karuizawa) Category: Keyword: puzzle, maze, computational complexity, NPhard, polynomialtime,
Full Text: PDF(472.6KB)>>
Summary:
In this paper, a puzzle called CellMaze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. CellMaze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as CellMaze may be extremely difficult. In this paper, NPhardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.

