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 dan Juosan ialah teka-teki pensel Nikoli. Kami mengkaji kerumitan pengiraan teka-teki Kurotto dan Juosan. Ia ditunjukkan bahawa memutuskan sama ada contoh tertentu bagi setiap teka-teki mempunyai penyelesaian adalah NP-lengkap.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -