Comparing ASP and CP on Four Grid Puzzles

We study two declarative programming languages namely Answer Set Programming (ASP) and Constraint Programming (CP) on four grid puzzles: Akari, Kakuro, Nurikabe, and Heyawake. We represent these problems in both formalisms in a systematic way and compute their solutions using ASP system Clasp and CP system Comet. We compare the ASP approach with the CP approach both from the point of view of knowledge representation and from the point of view of computational time and memory.

A summary of our studies is presented in the paper ``Comparing ASP and CP on Four Grid Puzzles'' that appeared in Proc. of RCRA'09 Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. Extended version of the paper contains further details including the comparison of ASP solvers on the puzzles.

The source files and the examples of the developed systems are below:

Akari Puzzle

ASP formulation of Akari
CP formulation of Akari
Akari Puzzle instances

Kakuro Puzzle

ASP formulation of Kakuro
CP formulation of Kakuro
Kakuro Puzzle instances

Heyawake Puzzle

ASP formulation of Heyawake
CP formulation of Heyawake
Heyawake Puzzle instances

Nurikabe Puzzle

ASP formulation of Nurikabe
CP formulation of Nurikabe
Nurikabe Puzzle instances