Generalized Shisen-Sho is NP-Complete

Chuzo IWAMOTO; Yoshihiro WADA; Kenichi MORITA

doi:10.1587/transinf.E95.D.2712

Generalized Shisen-Sho is NP-Complete

Chuzo IWAMOTO, Yoshihiro WADA, Kenichi MORITA

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E95-D No.11 pp.2712-2715

Publication Date: 2012/11/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E95.D.2712

Type of Manuscript: LETTER

Category: Fundamentals of Information Systems

Cite this

Copy

Chuzo IWAMOTO, Yoshihiro WADA, Kenichi MORITA, "Generalized Shisen-Sho is NP-Complete" in IEICE TRANSACTIONS on Information, vol. E95-D, no. 11, pp. 2712-2715, November 2012, doi: 10.1587/transinf.E95.D.2712.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E95.D.2712/_p

Copy

@ARTICLE{e95-d_11_2712,
author={Chuzo IWAMOTO, Yoshihiro WADA, Kenichi MORITA, },
journal={IEICE TRANSACTIONS on Information},
title={Generalized Shisen-Sho is NP-Complete},
year={2012},
volume={E95-D},
number={11},
pages={2712-2715},
abstract={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.},
keywords={},
doi={10.1587/transinf.E95.D.2712},
ISSN={1745-1361},
month={November},}

Copy

TY - JOUR
TI - Generalized Shisen-Sho is NP-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 2712
EP - 2715
AU - Chuzo IWAMOTO
AU - Yoshihiro WADA
AU - Kenichi MORITA
PY - 2012
DO - 10.1587/transinf.E95.D.2712
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2012
AB - 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.
ER -