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
Kurotto와 Juosan은 Nikoli의 연필 퍼즐입니다. 우리는 Kurotto와 Juosan 퍼즐의 계산 복잡도를 연구합니다. 각 퍼즐의 주어진 인스턴스에 해결책이 있는지 여부를 결정하는 것은 NP-완전인 것으로 나타났습니다.
Chuzo IWAMOTO
Hiroshima University
Tatsuaki IBUSUKI
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.
부
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
부
@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},}
부
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 -