{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T06:03:11Z","timestamp":1766210591006,"version":"3.48.0"},"reference-count":22,"publisher":"Information Processing Society of Japan","issue":"0","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Information Processing"],"published-print":{"date-parts":[[2025]]},"DOI":"10.2197\/ipsjjip.33.1101","type":"journal-article","created":{"date-parts":[[2025,12,14]],"date-time":"2025-12-14T22:09:23Z","timestamp":1765750163000},"page":"1101-1109","source":"Crossref","is-referenced-by-count":0,"title":["Sokoban-style PushPush Games with Unique Solutions"],"prefix":"10.2197","volume":"33","author":[{"given":"Robert D.","family":"Barish","sequence":"first","affiliation":[{"name":"Division of Medical Data Informatics, Human Genome Center, Institute of Medical Science, The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuo","family":"Shibuya","sequence":"additional","affiliation":[{"name":"Division of Medical Data Informatics, Human Genome Center, Institute of Medical Science, The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1012","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] Ajani, Y. and Bright, C.: SAT and lattice reduction for integer factorization, <i>Proc. 49th International Symposium on Symbolic and Algebraic Computation<\/i> (<i>ISSAC<\/i>), pp.391-399 (2024).","DOI":"10.1145\/3666000.3669712"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] Biedl, T. and Kant, G.: A better heuristic for orthogonal graph drawings, <i>Comput. Geom.<\/i>, Vol.9, No.3, pp.159-180 (1998).","DOI":"10.1016\/S0925-7721(97)00026-6"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] Bondy, J.A. and Murty, U.S.R.: <i>Graph theory with applications<\/i>, 1st edition, Macmillan Press (1976).","DOI":"10.1007\/978-1-349-03521-2_1"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] Cook, S.A. and Mitchell, D.G.: Finding hard instances of the satisfiability problem: A survey, <i>DIMACS Series in Discrete Mathematics and Theoretical Computer Science<\/i>, Vol.85, pp.1-17 (1997).","DOI":"10.1090\/dimacs\/035\/01"},{"key":"5","unstructured":"[5] Culberson, J.C.: Sokoban is PSPACE-complete, Technical Report TR 97-02, University of Alberta, pp.1-15 (1997)."},{"key":"6","unstructured":"[6] Demaine, E.D., Demaine, M.L. and O&apos;Rourke, J.: PushPush and Push-1 are NP-hard in 2D, <i>Proc. 12th Canadian Conference on Computational Geometry<\/i> (<i>CCCG<\/i>), pp.211-219 (2000)."},{"key":"7","unstructured":"[7] Demaine, E.D., Demaine, M.L. and O&apos;Rourke, J.: PushPush is NP-hard in 2D, Technical Report 066, Smith College, pp.1-18 (2000)."},{"key":"8","unstructured":"[8] Demaine, E.D., Hoffmann, M. and Holzer, M.: PushPush-k is PSPACE-complete, <i>Proc. 3rd International Conference on Fun with Algorithms<\/i> (<i>FUN<\/i>), pp.159-170 (2004)."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] Diestel, R.: <i>Graph theory<\/i>, 5th edition, Springer-Verlag, Heidelberg (2017).","DOI":"10.1007\/978-3-662-53622-3"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] Dor, D. and Zwick, U.: SOKOBAN and other motion planning problems, <i>Comput. Geom.<\/i>, Vol.13, No.4, pp.215-228 (1999).","DOI":"10.1016\/S0925-7721(99)00017-6"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] Garey, M.R., Johnson, D.S. and Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete, <i>SIAM J. Comput.<\/i>, Vol.5, No.4, pp.704-714 (1976).","DOI":"10.1137\/0205049"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] Mosca, M. and Verschoor, S.R.: Factoring semi-primes with (quantum) SAT-solvers, <i>Sci. Rep.<\/i>, Vol.12, No.7982, pp.1-12 (2022).","DOI":"10.1038\/s41598-022-11687-7"},{"key":"13","unstructured":"[13] O&apos;Rourke, J. and The Smith Problem Solving Group: PushPush is NP-hard in 3D, Technical Report 065, Smith College, pp.1-10 (1999)."},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] Papakostas, A. and Tollis, I.G.: Algorithms for area-efficient orthogonal drawings, <i>Comput. Geom.<\/i>, Vol.9, No.1-2, pp.83-110 (1998).","DOI":"10.1016\/S0925-7721(97)00017-5"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Ples\u0144ik, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, <i>Inf. Process. Lett.<\/i>, Vol.8, No.4, pp.199-201 (1979).","DOI":"10.1016\/0020-0190(79)90023-1"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] Rusu, I.: Hamiltonian problems in directed graphs with simple row patterns, <i>Theoret. Comput. Sci.<\/i>, Vol.916, pp.70-85 (2022).","DOI":"10.1016\/j.tcs.2022.03.005"},{"key":"17","unstructured":"[17] Seta, T.: The complexities of puzzles, cross sum and their another solution problems (ASP), <i>Senior thesis, Department of Information Science, the University of Tokyo<\/i>, pp.1-43 (2002)."},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] Tutte, W.T.: On Hamiltonian circuits, <i>J. Lond. Math. Soc.<\/i>, Vol.s1-21, No.2, pp.98-101 (1946).","DOI":"10.1112\/jlms\/s1-21.2.98"},{"key":"19","unstructured":"[19] Ueda, N. and Nagao, T.: NP-completeness results for NONOGRAM via parsimonious reductions, Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, pp.1-8 (1996)."},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] Valiant, L.G.: Relative complexity of checking and evaluating, <i>Inf. Process. Lett.<\/i>, Vol.5, No.1, pp.20-23 (1976).","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] Valiant, L.G. and Vazirani, V.V.: NP is as easy as detecting unique solutions, <i>Theoret. Comput. Sci.<\/i>, Vol.47, No.1, pp.85-93 (1986).","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"22","unstructured":"[22] Yato, T. and Seta, T.: Complexity and completeness of finding another solution and its application to puzzles, <i>IEICE Trans. Fundamentals of Electronics Communications and Computer Sciences<\/i>, Vol.E86-A, No.5, pp.1052-1060 (2003)."}],"container-title":["Journal of Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/ipsjjip\/33\/0\/33_1101\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T03:53:24Z","timestamp":1766202804000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/ipsjjip\/33\/0\/33_1101\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":22,"journal-issue":{"issue":"0","published-print":{"date-parts":[[2025]]}},"URL":"https:\/\/doi.org\/10.2197\/ipsjjip.33.1101","relation":{},"ISSN":["1882-6652"],"issn-type":[{"type":"electronic","value":"1882-6652"}],"subject":[],"published":{"date-parts":[[2025]]}}}