{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:49:10Z","timestamp":1761965350753},"reference-count":24,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2022,3,1]]},"DOI":"10.1587\/transinf.2021fcp0001","type":"journal-article","created":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T22:25:34Z","timestamp":1646087134000},"page":"508-516","source":"Crossref","is-referenced-by-count":11,"title":["Five Cells and Tilepaint are NP-Complete"],"prefix":"10.1587","volume":"E105.D","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:\/\/nikoli.co.jp\/en\/puzzles\/five_cells.html"},{"key":"2","unstructured":"[2] https:\/\/nikoli.co.jp\/en\/puzzles\/tile_paint.html"},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] 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":"4","unstructured":"[4] 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":"5","unstructured":"[5] 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":"6","doi-asserted-by":"publisher","unstructured":"[6] D. Andersson, \u201cHashiwokakero is NP-complete,\u201d Inf. Process. Lett., vol.109, 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":"7","unstructured":"[7] 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":"8","doi-asserted-by":"publisher","unstructured":"[8] M.R. Cerioli, L. Faria, T.O. Ferreira, C.A.J. Martinhon, F. Protti, and B. Reed, \u201cPartition into cliques for cubic graphs: planar case, complexity and approximation,\u201d Discrete Appl. Math., vol.156, no.12, pp.2270-2278, 2008. DOI: 10. 1016\/j.dam.2007.10.015 10.1016\/j.dam.2007.10.015","DOI":"10.1016\/j.dam.2007.10.015"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] E.D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, \u201cComputational complexity and an integer programming model of Shakashaka,\u201d IEICE Trans. Fundamentals, vol.E97-A, no.6, pp.1213-1219, 2014. DOI: 10. 1587\/transfun.E97.A.1213 10.1587\/transfun.E97.A.1213","DOI":"10.1587\/transfun.E97.A.1213"},{"key":"10","unstructured":"[10] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, NY, 1979."},{"key":"11","unstructured":"[12] T. Ide and C. Iwamoto, \u201cMoon-or-Sun, Nagareru, and Nurimeizu are NP-complete,\u201d Proc. LA Symposium, Kyoto, pp.S4.1-S4.8, 2020."},{"key":"12","unstructured":"[13] 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":"13","doi-asserted-by":"publisher","unstructured":"[14] 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":"14","doi-asserted-by":"publisher","unstructured":"[15] C. Iwamoto and M. Haruishi, \u201cComputational complexity of Usowan puzzles,\u201d IEICE Trans. Fundamentals, vol.D101-A, no.9, pp.1537-1540, 2018. DOI: 10. 1587\/transfun.E101.A.1537 10.1587\/transfun.E101.A.1537","DOI":"10.1587\/transfun.E101.A.1537"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[16] C. Iwamoto, M. Haruishi, and T. Ibusuki, \u201cComputational complexity of Herugolf and Makaro,\u201d IEICE Trans. Fundamentals, vol.E102-A, no.6, pp.1118-1125, 2019. DOI: 10. 1587\/transfun.E102.A.1118 10.1587\/transfun.E102.A.1118","DOI":"10.1587\/transfun.E102.A.1118"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[17] 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":"17","doi-asserted-by":"publisher","unstructured":"[18] 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, 2020. DOI: 10. 1587\/transinf.2019FCP0004 10.1587\/transinf.2019FCP0004","DOI":"10.1587\/transinf.2019FCP0004"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[19] C. Iwamoto and T. Ide, \u201cComputational complexity of Nurimisaki and Sashigane,\u201d IEICE Trans. Fundamentals, vol.E103-A, no.10, pp.1183-1192, 2020. DOI: 10. 1587\/transfun.2019DMP0002 10.1587\/transfun.2019DMP0002","DOI":"10.1587\/transfun.2019DMP0002"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[20] 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":"20","doi-asserted-by":"publisher","unstructured":"[21] 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":"21","unstructured":"[22] D. Packer, S. White, and A. Williams, \u201cA paper on pencils: A pencil and paper puzzle-Pencils is NP-Complete,\u201d Proc. 30th Canadian Conference on Computational Geometry, Winnipeg, Canada, pp.35-41, Aug. 2018."},{"key":"22","unstructured":"[23] 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":"23","doi-asserted-by":"publisher","unstructured":"[24] 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":"24","doi-asserted-by":"publisher","unstructured":"[25] 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 Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/3\/E105.D_2021FCP0001\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,5]],"date-time":"2022-03-05T04:00:35Z","timestamp":1646452835000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E105.D\/3\/E105.D_2021FCP0001\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,1]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2021fcp0001","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,1]]},"article-number":"2021FCP0001"}}