Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles
Summary :
Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan 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.E103-D No.3 pp.500-505
- Publication Date
- 2020/03/01
- Publicized
- 2019/12/20
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019FCP0004
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
- Category
Authors
Chuzo IWAMOTO
Hiroshima University
Tatsuaki IBUSUKI
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, Tatsuaki IBUSUKI, "Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 3, pp. 500-505, March 2020, doi: 10.1587/transinf.2019FCP0004.
Abstract: Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan 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.2019FCP0004/_p
Copy
@ARTICLE{e103-d_3_500,
author={Chuzo IWAMOTO, Tatsuaki IBUSUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles},
year={2020},
volume={E103-D},
number={3},
pages={500-505},
abstract={Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.},
keywords={},
doi={10.1587/transinf.2019FCP0004},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles
T2 - IEICE TRANSACTIONS on Information
SP - 500
EP - 505
AU - Chuzo IWAMOTO
AU - Tatsuaki IBUSUKI
PY - 2020
DO - 10.1587/transinf.2019FCP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2020
AB - Kurotto and Juosan are Nikoli's pencil puzzles. We study the computational complexity of Kurotto and Juosan puzzles. It is shown that deciding whether a given instance of each puzzle has a solution is NP-complete.
ER -
English
