3coSoKu and its declarative modeling. (18th January 2022)

• Record Type: Journal Article
• Authors: Rizzo, Nicola; Dovier, Agostino
• Is Part Of: Journal of logic and computation. Volume 32:Number 2(2022)
• Page Start: 307
• Page End: 330
• Publication Date: 2022-01-18
• Subjects: Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exab086
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: 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.