Generalized Shisen-Sho is NP-Complete

被引：1

作者：

Iwamoto, Chuzo ^{[1
]}

Wada, Yoshihiro ^{[1
]}

Morita, Kenichi ^{[1
]}

机构：

[1] Hiroshima Univ, Grad Sch Engn, Higashihiroshima 7398527, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2012年 / E95D卷 / 11期

关键词：

NP-complete; computational complexity; one-player game; Shisen-Sho;

D O I：

10.1587/transinf.E95.D.2712

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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

引用

页码：2712 / 2715

页数：4