{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T19:18:07Z","timestamp":1648667887604},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2022,1,18]],"date-time":"2022-01-18T00:00:00Z","timestamp":1642464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,2,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we analyze the physical puzzle IcoSoKu, a game about placing some given triangular tiles on the faces of an icosahedron in order to fill the capacities of its vertices, and we propose its generalization called 3coSoKu, admitting an arbitrary playing field with triangular faces, arbitrary capacities and an arbitrary set of triangular tiles. First, we prove the strong NP-completeness of 3coSoKu, even when the playing field is a convex polyhedron with equilateral triangles as faces. Second, we encode 3coSoKu both in the constraint modeling language MiniZinc and in the logic programming paradigm known as Answer Set Programming and we develop a visual tool for an accessible interface to the solver. Finally, we use our encodings to verify experimentally that every initial state for IcoSoKu admits a solution.<\/jats:p>","DOI":"10.1093\/logcom\/exab086","type":"journal-article","created":{"date-parts":[[2021,12,16]],"date-time":"2021-12-16T12:09:29Z","timestamp":1639656569000},"page":"307-330","source":"Crossref","is-referenced-by-count":0,"title":["<tt>3coSoKu<\/tt> and its declarative modeling"],"prefix":"10.1093","volume":"32","author":[{"given":"Nicola","family":"Rizzo","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Helsinki, 00014 Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Agostino","family":"Dovier","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Mathematics and Physics, University of Udine, 33100 Udine, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,1,18]]},"reference":[{"key":"2022022805591678900_ref1","volume-title":"Three.js: Javascript 3D Library","author":"Cabello","year":"2010"},{"key":"2022022805591678900_ref2","volume-title":"Icosoku Online Solver Page","author":"De Biasi"},{"key":"2022022805591678900_ref3","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1080\/09528130701538174","article-title":"An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems","volume":"21","author":"Dovier","year":"2009","journal-title":"Journal of Experimental & Theoretical Artificial Intelligence"},{"key":"2022022805591678900_ref4","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.cag.2014.02.002","article-title":"3d graphics on the web: a survey","volume":"41","author":"Evans","year":"2014","journal-title":"Computers & Graphics"},{"key":"2022022805591678900_ref5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2022022805591678900_ref6","volume-title":"Potassco User Guide","author":"Gebser","year":"2019"},{"key":"2022022805591678900_ref7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-540-72200-7_3","article-title":"The first answer set programming system competition","volume-title":"Logic Programming and Nonmonotonic Reasoning, 9th International Conference, LPNMR 2007, Tempe, AZ, USA, May 15\u201317, 2007, Proceedings","author":"Gebser","year":"2007"},{"key":"2022022805591678900_ref8","first-page":"1070","article-title":"The stable model semantics for logic programming","author":"Gelfond","year":"1988"},{"key":"2022022805591678900_ref9","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/3107239","article-title":"The science of brute force","volume":"60","author":"Heule","year":"2017","journal-title":"Communications of the ACM"},{"key":"2022022805591678900_ref10","volume-title":"Icosoku Puzzle Product page","author":"Recent Toys Intl","year":"2021"},{"key":"2022022805591678900_ref11","doi-asserted-by":"crossref","first-page":"169","DOI":"10.4153\/CJM-1966-021-8","article-title":"Convex polyhedra with regular faces","volume":"18","author":"Johnson","year":"1966","journal-title":"Canadian Journal of Mathematics"},{"key":"2022022805591678900_ref12","first-page":"85","article-title":"Reducibility among combinatorial problems","volume-title":"Proceedings of a Symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series","author":"Karp","year":"1972"},{"key":"2022022805591678900_ref13","first-page":"99","article-title":"Exploring properties of icosoku by constraint satisfaction approach","volume-title":"Declarative Programming and Knowledge Management\u2014Conference on Declarative Programming, DECLARE 2019, Unifying INAP, WLP, and WFLP, Cottbus, Germany, September 9\u201312, 2019, Revised Selected Papers","author":"Liu","year":"2019"},{"key":"2022022805591678900_ref14","volume-title":"Profile Page in Spiele-Autoren-Zunft e.v. Game Designers Association\u2019s Website","author":"Mainini"},{"key":"2022022805591678900_ref15","volume-title":"Clingo Webassembly","author":"Moritz","year":"2020"},{"key":"2022022805591678900_ref16","first-page":"5","article-title":"3cosoku and its logic programming modeling","volume-title":"Proceedings of the 35th Italian Conference on Computational Logic\u2014CILC 2020, Rende, Italy, October 13\u201315, 2020","author":"Rizzo","year":"2020"},{"key":"2022022805591678900_ref17","first-page":"302","article-title":"Sur une courbe dont tout point est un point de ramification","volume":"160","author":"Sierpi\u0144ski","year":"1915","journal-title":"Comptes rendus de l\u2019Acadmie des Sciences"},{"key":"2022022805591678900_ref18","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10601-010-9093-0","article-title":"Philosophy of the MiniZinc challenge","volume":"15","author":"Stuckey","year":"2010","journal-title":"Constraints"},{"key":"2022022805591678900_ref19","volume-title":"The Minizinc Handbook","author":"Stuckey","year":"2021"},{"key":"2022022805591678900_ref20","volume-title":"Gnu Parallel Tutorial","author":"Tangle","year":"2018"},{"key":"2022022805591678900_ref21","first-page":"301","article-title":"Emscripten: an LLVM-to-JavaScript compiler","volume-title":"Companion to the 26th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2011, part of SPLASH 2011, Portland, OR, USA, October 22\u201327, 2011","author":"Zakai","year":"2011"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/2\/307\/42618114\/exab086.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/32\/2\/307\/42618114\/exab086.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T06:00:28Z","timestamp":1646028028000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/32\/2\/307\/6509361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,18]]},"references-count":21,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,1,18]]},"published-print":{"date-parts":[[2022,2,26]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exab086","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,3]]},"published":{"date-parts":[[2022,1,18]]}}}