Grid Puzzles

Puzzles like Blocks World, Sudoku, Cross Sum, and Sokoban have been studied in various areas of AI (e.g., knowledge representation, planning, constraint programming, answer set programming) as toy problems, and these studies have led to interesting insights and useful approaches for solving them as well as some real-life problems. There are many other challenging puzzles that have not been well-studied, but could be useful for investigating some theoretical or application-oriented questions.

We study such challenging grid puzzles (like Akari, Kakuro, Nurikabe, Heyawake, Bag Puzzle, Masyu) in answer set programming and in constraint programming. Our goal is to represent these problems in both formalisms in a systematic way, compute their solutions using the state-of-the-art solvers, and compare different approaches both from the point of view of knowledge representation and from the point of view of computational time and memory.

PUBLICATIONS

[1] Solving challenging grid puzzles with answer set programming.
M. Cayli, A. G. Karatop, E. Kavlak, H. Kaynar, F. Ture, and E. Erdem.
In Proc. of ASP'07, pp. 175-190.
formulations of puzzles

[2] Comparing ASP and CP on four grid puzzles.
M. Celik, H. Erdogan, F. Tahaoglu, T. Uras and E. Erdem.
In Proc. of RCRA'09 Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion.
formulations of puzzles