{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T15:18:11Z","timestamp":1726240691755},"reference-count":23,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2022,9,1]]},"DOI":"10.1587\/transfun.2021dmp0006","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T22:24:13Z","timestamp":1646087053000},"page":"1187-1194","source":"Crossref","is-referenced-by-count":4,"title":["Moon-or-Sun, Nagareru, and Nurimeizu are NP-Complete"],"prefix":"10.1587","volume":"E105.A","author":[{"given":"Chuzo","family":"IWAMOTO","sequence":"first","affiliation":[{"name":"Graduate School of Advanced Science and Engineering, Hiroshima University"}]},{"given":"Tatsuya","family":"IDE","sequence":"additional","affiliation":[{"name":"Graduate School of Advanced Science and Engineering, Hiroshima University"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] https:\/\/www.nikoli.co.jp\/en\/puzzles\/"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] A.B. Adcock, E.D. Demaine, M.L. Demaine, M.P. O'Brien, F. Reidl, F.S. Villaamil, and B.D. Sullivan, \u201cZig-zag numberlink is NP-complete,\u201d J. Inf. Process., vol.23, no.3, pp.239-245, 2015. DOI: 10.2197\/ipsjjip.23.239 10.2197\/ipsjjip.23.239","DOI":"10.2197\/ipsjjip.23.239"},{"key":"3","unstructured":"[3] A. Adler, J. Bosboom, E.D. Demaine, M.L. Demaine, Q.C. Liu, and J. Lynch, \u201cTatamibari is NP-complete,\u201d Proc. 10th International Conference on Fun with Algorithms, LIPICS, vol.157, pp.1:1-1:24, 2021. DOI: 10.4230\/LIPIcs.FUN.2021.1 10.4230\/LIPIcs.FUN.2021.1"},{"key":"4","unstructured":"[4] A. Allen and A. Williams, \u201cSto-Stone is NP-Complete,\u201d Proc. 30th Canadian Conference on Computational Geometry, Winnipeg, Canada, pp.28-34, 2018."},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] D. Andersson, \u201cHashiwokakero is NP-complete,\u201d Inf. Process. Lett., vol.109, no.19, pp.1145-1146, 2009. DOI: 10.1016\/j.ipl.2009.07.017 10.1016\/j.ipl.2009.07.017","DOI":"10.1016\/j.ipl.2009.07.017"},{"key":"6","unstructured":"[6] M. Biro and C. Schmidt, \u201cComputational complexity and bounds for Norinori and LITS,\u201d Proc. 33rd European Workshop on Computational Geometry, Malm\u00f6, Sweden, pp.29-32, April 2017."},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] M.R. Garey, D.S. Johnson, and R.E. Tarjan, \u201cThe planar Hamiltonian circuit problem is NP-complete,\u201d SIAM J. Comput., vol.5, no.4, pp.704-714, 1974. 10.1137\/0205049","DOI":"10.1137\/0205049"},{"key":"8","unstructured":"[9] A. Ishibashi, Y. Sato, and S. Iwata, \u201cNP-completeness of two pencil puzzles: Yajilin and Country Road,\u201d Utilitas Mathematica, vol.88, pp.237-246, 2012."},{"key":"9","doi-asserted-by":"publisher","unstructured":"[10] C. Iwamoto, \u201cYosenabe is NP-complete,\u201d J. Inf. Process., vol.22, no.1, pp.40-43, 2014. DOI: 10.2197\/ipsjjip.22.40 10.2197\/ipsjjip.22.40","DOI":"10.2197\/ipsjjip.22.40"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[11] C. Iwamoto and M. Haruishi, \u201cComputational complexity of Usowan puzzles,\u201d IEICE Trans. Fundamentals, vol.E101-A, no.9, pp.1537-1540, Sept. 2018. DOI: 10.1587\/transfun.E101.A.1537 10.1587\/transfun.e101.a.1537","DOI":"10.1587\/transfun.E101.A.1537"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[12] C. Iwamoto, M. Haruishi, and T. Ibusuki, \u201cComputational complexity of Herugolf and Makaro,\u201d IEICE Trans. Fundamentals, vol.E102-A, no.9, pp.1118-1125, Setp. 2019. DOI: 10.1587\/transfun.E102.A.1118 10.1587\/transfun.e102.a.1118","DOI":"10.1587\/transfun.E102.A.1118"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[13] C. Iwamoto and T. Ibusuki, \u201cDosun-Fuwari is NP-complete,\u201d J. Inf. Process., vol.26, pp.358-361, 2018. DOI: 10.2197\/ipsjjip.26.358 10.2197\/ipsjjip.26.358","DOI":"10.2197\/ipsjjip.26.358"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[14] C. Iwamoto and T. Ibusuki, \u201cPolynomial-time reductions from 3SAT to Kurotto and Juosan puzzles,\u201d IEICE Trans. Inf. & Syst., vol.E103-D, no.3, pp.500-505, March 2020. DOI: 10.1587\/transinf.2019FCP0004 10.1587\/transinf.2019fcp0004","DOI":"10.1587\/transinf.2019FCP0004"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[15] C. Iwamoto and T. Ide, \u201cComputational complexity of Nurimisaki and Sashigane,\u201d IEICE Trans. Fundamentals, vol.E103-A, no.10, pp.1183-1192, Oct. 2020. DOI: 10.1587\/transfun.2019DMP0002 10.1587\/transfun.2019dmp0002","DOI":"10.1587\/transfun.2019DMP0002"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[16] S. Kanehiro and Y. Takenaga, \u201cSatogaeri, Hebi and Suraromu are NP-complete,\u201d Proc. 3rd International Conference on Applied Computing and Information Technology, Okayama, Japan, pp.47-52, July 2015. 10.1109\/acit-csi.2015.17","DOI":"10.1109\/ACIT-CSI.2015.17"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] J. K\u00f6lker, \u201cKurodoko is NP-complete,\u201d J. Inf. Process., vol.20, no.3, pp.694-706, 2012. DOI: 10.2197\/ipsjjip.20.694 10.2197\/ipsjjip.20.694","DOI":"10.2197\/ipsjjip.20.694"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[18] P. Lafourcade, D. Miyahara, T. Mizuki, L. Robert, T. Sasaki, and H. Sone, \u201cHow to construct physical zero-knowledge proofs for puzzles with \u201ca single loop\u201d condition,\u201d Theor. Comput. Sci., vol.888, no.4, pp.41-55, 2021. DOI:10.1016\/j.tcs.2021.07.019 10.1016\/j.tcs.2021.07.019","DOI":"10.1016\/j.tcs.2021.07.019"},{"key":"18","unstructured":"[19] D. Packer, S. White, and A. Williams, \u201cA paper on pencils: A pencil and paper puzzle \u2014 Pencils is NP-complete,\u201d Proc. 30th Canadian Conference on Computational Geometry, Winnipeg, Canada, pp.35-41, Aug. 2018."},{"key":"19","doi-asserted-by":"publisher","unstructured":"[20] J. Plesnik, \u201cThe NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two,\u201d Inf. Process. Lett., vol.8, no.4, pp.199-201, 1979. DOI: 10.1016\/0020-0190(79)90023-1 10.1016\/0020-0190(79)90023-1","DOI":"10.1016\/0020-0190(79)90023-1"},{"key":"20","doi-asserted-by":"publisher","unstructured":"[21] S. Ruangwises and T. Itoh, \u201cPhysical zero-knowledge proof for ripple effect,\u201d Theor. Comput. Sci., vol.895, no.4, pp.115-123, 2021. DOI:10.1016\/j.tcs.2021.09.034 10.1016\/j.tcs.2021.09.034","DOI":"10.1016\/j.tcs.2021.09.034"},{"key":"21","unstructured":"[22] Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, \u201cShikaku and ripple effect are NP-complete,\u201d Congressus Numerantium, vol.216, pp.119-127, 2013."},{"key":"22","doi-asserted-by":"publisher","unstructured":"[23] A. Uejima and H. Suzuki, \u201cFillmat is NP-complete and ASP-complete,\u201d J. Inf. Process., vol.23, no.3, pp.310-316, 2015. DOI: 10.2197\/ipsjjip.23.310 10.2197\/ipsjjip.23.310","DOI":"10.2197\/ipsjjip.23.310"},{"key":"23","doi-asserted-by":"publisher","unstructured":"[24] A. Uejima, H. Suzuki, and A. Okada, \u201cThe complexity of generalized pipe link puzzles,\u201d J. Inf. Process., vol.25, pp.724-729, 2017. DOI: 10.2197\/ipsjjip.25.724 10.2197\/ipsjjip.25.724","DOI":"10.2197\/ipsjjip.25.724"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0006\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T04:35:55Z","timestamp":1662179755000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E105.A\/9\/E105.A_2021DMP0006\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,1]]},"references-count":23,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2021dmp0006","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,1]]},"article-number":"2021DMP0006"}}