Generalized Shisen-Sho is NP-Complete

スポンサーリンク

概要

• 論文の詳細を見る

• Shisen-Sho is a tile-based one-player game. The instance is a set of 136 tiles embedded on 8×17 rectangular grids. Two tiles can be removed if they are labeled by the same number and if they are adjacent or can be connected with at most three orthogonal line segments. Here, line segments must not cross tiles. The aim of the game is to remove all of the 136 tiles. In this paper, we consider the generalized version of Shisen-Sho, which uses an arbitrary number of tiles embedded on rectangular grids. It is shown that deciding whether the player can remove all of the tiles is NP-complete.

著者

• Iwamoto Chuzo

  Graduate School Of Engineering Hiroshima University

• Morita Kenichi

  Graduate School Of Engineering Hiroshima University

• WADA Yoshihiro

  Graduate School of Engineering, Hiroshima University

関連論文

• On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
• A Recursive Padding Technique on Nondeterministic Cellular Automata
• Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(Cellular Automata)
• A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function(Cellular Automata)
• Time and Space Complexity Classes of Hyperbolic Cellular Automata(Cellular Automata)
• NP-Hard and k-EXPSPACE-Hard Cast Puzzles
• Generalized Shisen-Sho is NP-Complete
• Generalized Chat Noir is PSPACE-Complete

スポンサーリンク