The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Chained Block est l'un des puzzles au crayon de Nikoli. Nous étudions la complexité informatique des puzzles Chained Block. Il est démontré que décider si une instance donnée du puzzle Chained Block a une solution est NP-complet.
Chuzo IWAMOTO
Hiroshima University
Tatsuya IDE
Hiroshima University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Chuzo IWAMOTO, Tatsuya IDE, "Chained Block is NP-Complete" in IEICE TRANSACTIONS on Information,
vol. E107-D, no. 3, pp. 320-324, March 2024, doi: 10.1587/transinf.2023FCL0001.
Abstract: Chained Block is one of Nikoli's pencil puzzles. We study the computational complexity of Chained Block puzzles. It is shown that deciding whether a given instance of the Chained Block puzzle has a solution is NP-complete.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023FCL0001/_p
Copier
@ARTICLE{e107-d_3_320,
author={Chuzo IWAMOTO, Tatsuya IDE, },
journal={IEICE TRANSACTIONS on Information},
title={Chained Block is NP-Complete},
year={2024},
volume={E107-D},
number={3},
pages={320-324},
abstract={Chained Block is one of Nikoli's pencil puzzles. We study the computational complexity of Chained Block puzzles. It is shown that deciding whether a given instance of the Chained Block puzzle has a solution is NP-complete.},
keywords={},
doi={10.1587/transinf.2023FCL0001},
ISSN={1745-1361},
month={March},}
Copier
TY - JOUR
TI - Chained Block is NP-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 320
EP - 324
AU - Chuzo IWAMOTO
AU - Tatsuya IDE
PY - 2024
DO - 10.1587/transinf.2023FCL0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E107-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2024
AB - Chained Block is one of Nikoli's pencil puzzles. We study the computational complexity of Chained Block puzzles. It is shown that deciding whether a given instance of the Chained Block puzzle has a solution is NP-complete.
ER -