IEICE TRANSACTIONS on Information
Five Cells and Tilepaint are NP-Complete
Summary :
Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.508-516
- Publication Date
- 2022/03/01
- Publicized
- 2021/10/18
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021FCP0001
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
- Category
Authors
Chuzo IWAMOTO
Hiroshima University
Tatsuya IDE
Hiroshima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Chuzo IWAMOTO, Tatsuya IDE, "Five Cells and Tilepaint are NP-Complete" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 508-516, March 2022, doi: 10.1587/transinf.2021FCP0001.
Abstract: Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0001/_p
Copy
@ARTICLE{e105-d_3_508,
author={Chuzo IWAMOTO, Tatsuya IDE, },
journal={IEICE TRANSACTIONS on Information},
title={Five Cells and Tilepaint are NP-Complete},
year={2022},
volume={E105-D},
number={3},
pages={508-516},
abstract={Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.},
keywords={},
doi={10.1587/transinf.2021FCP0001},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Five Cells and Tilepaint are NP-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 508
EP - 516
AU - Chuzo IWAMOTO
AU - Tatsuya IDE
PY - 2022
DO - 10.1587/transinf.2021FCP0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - Five Cells and Tilepaint are Nikoli's pencil puzzles. We study the computational complexity of Five Cells and Tilepaint puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
ER -
English
