Generalized Shisen-Sho is NP-Complete

Chuzo IWAMOTO  Yoshihiro WADA  Kenichi MORITA  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.11   pp.2712-2715
Publication Date: 2012/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.2712
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
NP-complete,  computational complexity,  one-player game,  Shisen-Sho,  

Full Text: PDF(595.1KB)>>
Buy this Article

Shisen-Sho is a tile-based one-player game. The instance is a set of 136 tiles embedded on 817 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.