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.
In the literature, there are several attempts to solve the puzzles that we are interested in as well as the empirical works to compare several declarative programming paradigms. For instance, [1] studies the representations of some grid puzzles in ASP including Heyawake and Nurikabe. In [2] the authors compare ASP, CP and ILP on Wire Routing problems and Haplotype Inference problems. [10, 11] presents CP formulations of some grid puzzles. In addition, in [7], the authors study the comparison of ASP and CP on some puzzles. Similarly, [4] presents some experimental results for comparing Constraint Logic Programming and Answer Set Programming on some NP-complete problems.
In the rest of the paper, we show the representations of each puzzle in the language of Lparse (grounder for the ASP solver Clasp) and in the language of Comet, show the results of our experiments with Clasp and Comet using these formulations and point out the weaknesses and strengths of each approaches. 2
Akari, also known as Light-Up, uses a rectangular grid of black cells and white cells. Hints (integers) are placed in black cells. Figure 1 is an example of an initial Akari board and its solution. The player solves puzzles via placing light bulbs in the white boxes according to following rules: A1 Light bulbs are permitted to be placed at any white square. A hint (numbered black square) indicates how many light bulbs are next to it, vertically or horizontally.
A2 Each light bulb illuminates from itself to a black square or the outer frame in its row and column, and every white square must be illuminated.
A3 No light bulbs should illuminate each other.
Given an Akari problem, deciding whether a solution exists is NP-complete [9]. 2.1
Input: The initial board is described with two types of atoms:
hint(Row; Column; Value) is used to specify hints. Row; Column
species the location of the hint4, Value speci es the value (constraint) of
the hint. For example, in Fig. 1, there is a hint at the bottom left
corner with the value 1 and represented by hint(
Output: The output is described by atoms of the form bulb(Row; Column), that means the cell (Row; Column) has a bulb in it.
The constraints are forced as follows in ASP:
A1 Light bulbs are permitted to be placed at any white square. A hint (numbered black square) indicates how many light bulbs are next to it, vertically and horizontally.
C{bulb(V1,H1) : adjacent(V,H,V1,H1) : white(V1,H1)}C :- hint(V,H,C). A2-A3 Each light bulb illuminates from itself to a black square or the outer frame in its row and column, and every white square must be illuminated. 1{bulb(V,H) : reachable(V,H,V1,H1) : verticalIndex(V) : horizontalIndex(H)}2 :- white(V1,H1),verticalIndex(V1),horizontalIndex(H1).
A cell is vertically (horizontally) reachable from another, if it is vertically (horizontally) adjacent to it, or reachable from any of its vertical (horizontal) adjacent cells.
4In all of the puzzle grids in this paper, the cell on the bottom left corner has the location (1; 1), and the cell on the top right corner has the location (m; n), where m is the number of columns and n is the number of rows. 2.2
Input: The input is given as a series of tuples for black cells, hints and vertical and horizontal blocks. The hint inputs are tuples of 3: row, column, and the value, while the black cells are identi ed by their rows and columns. The vertical (or horizontal) blocks are identi ed by tuples of 3, the vertical (or horizontal) index of the block and the horizontal (or vertical) beginning and end indices of the block. So, all vertical and horizontal blocks are given in input, according to these a neighborhood set is constructed for each cell, which contains reachable cells from that cell.
Output: The output is an integer matrix board. For every (i; j), board(i; j) is mapped to either 0 or 1, where board(i; j) = 1 indicates that the cell (i; j) has a bulb.
Rules: The rules are enforced via constraints as follows: A1-I Light bulbs are permitted to be placed at any white square. A1-II A hint (numbered black square) indicates how many light bulbs are next to it, vertically and horizontally. forall(i in 1..nbB){ //read row and column index from input m.post(board[r,c] == 0);} forall(i in 1..nbH){ //read row, column and constraint from input m.post(board[r,c] == 0); m.post((board[r,c-1] + board[r,c+1] + board[r-1,c] + board[r+1,c]) == v); } A2-A3 Each light bulb illuminates from itself to a black square or the outer frame in its row and column, and every white square must be illuminated.
for all block x{ //that block should have at most 1 bulb m.post(sum(i in x) board[i.r, i.c] <= 1); forall(row in RowRange) forall(column in ColumnRange) if(the cell is white){ //every white cell should be lighted m.post(sum(j in neighborhood[row,column]) board[j.r, j.c] >= 1);}} Kakuro uses a rectangular grid of black and white cells. Black cells may contain hints (integers) as in Akari. The number below the diagonal divider is the hint for cells below, the number above the diagonal divider is the hint for cells to the right. Figure 2 shows an example and solution for a Kakuro problem. The goal is to ll the white cells while satisfying the following rules:
K1 Each white cell should contain a single value between 1-9. K2 All numbers in a continuous block of white cells must be pairwise di erent.
K3 The sum of a continuous block of white cells in horizontal (or vertical) direction must be equal to the hint given in the black cell to the left (above).
Deciding whether there is a solution for a Kakuro instance is NP-complete [6] 3.1
Input: The initial board is described with three types of atoms:
hHint(Row; Column; Sum; Extent) is used to specify horizontal hints.
Row; Column speci es the location of the hint, Sum speci es the sum
constraint of the hint and Extent speci es how many cells the hint
covers. For example, in Figure 2, there is a horizontal hint which
requires 3 cells and with the constraint value 6 on the bottom left
corner of the grid and represented by hHint(
Output: The output is described by atoms of the form cellVal(Row; Column; Value), meaning the cell Row; Column is assigned Value that ranges between 1 and 9. The rules are enforced via constraints and are as follows:
K1 For each white cell, there must be exactly one cellVal atom 1{cellVal(R,C,Val) : val(Val)}1 :- not black(R,C), row(R), column(C).
K2 For any hint block and any two di erent cells in it, the value of the cells cannot be the same :- vHint(R, C, Sum, E), cellVal(R1, C, Val), cellVal(R2,C,Val), row(R1; R2),
R < R1, R1 < R2, R2 <= R + E, val(Val).
% Same rule applies for the horizontal hint (hHint) K3 The enforcement of the sum constraint is a bit harder. Basically, for each hint (horizontal or vertical) we sum the values of the cells starting from the farthest cell in the hint block all the way to the rst cell of the hint. Then the total sum is forced to be equal to the value of the hint. Step by step: 1. The end points for the hints are determined and the sums up to these points are set to 0.
horSum(R,C+E,0) :- hHint(R,C,Sum,E).
verSum(R+E,C,0) :- vHint(R,C,Sum,E). 2. The horizontal and vertical sums are computed all the way to the hints verSum(R-1,C,Sum+Val) :- not black(R,C), verSum(R,C,Sum), cellVal(R,C,Val), sum(Sum), val(Val).
% Same rule applies for the horizontal sum (horSum) 3. The total sum cannot be di erent than the value of the hint :- vHint(R,C,Sum,E), verSum(R,C,Sum2),
sum(Sum2), Sum != Sum2. % Same rule applies for the horizontal hint (hHint) 3.2
Input: The input is given as a series of tuples for vertical hints, horizontal hints and black cells. The hint inputs are tuples of 4: row, column, sum and extent of the hint, while the black cells are identi ed by their rows and columns. The input for vertical and horizontal hints are processed in the program to form an array called hints where a hint consists of a set of cells associated with it and its sum constraint.
Output: The output is an integer matrix called board, representing the puzzle. The values in each cell range between 0-9 where 0 means the cell is black and 1-9 is the ll value of a white cell.
For each hint the following function is called with the solver, the hint itself and the board: function void postHint(Solver<CP> m, block bl, var<CP>{int}[,] board) This function contains the following parts:
K1 All white cells are non-black (their domains are 1-9) forall (a in bl.cells)
m.post(board[a.r,a.c]>=1); K2 All cells in the hint's set should contain di erent values
m.post(alldifferent(all(a in bl.cells) board[a.r,a.c])); K3 The sum of the values of the cells in the hint's set should satisfy the sum constraint of the hint m.post(sum(a in bl.cells) board[a.r,a.c] == bl.sumC); Also, all of the black cells are forced to be 0 in the input reading phase. 4
Nurikabe is played on a rectangular grid of cells where some cells are numbered. The challenge is to paint some of the cells black while obeying the following set of constraints and de nitions.
N1 The \walls" are made of connected adjacent white cells in the grid of cells.
N2 At the start of the puzzle, each numbered cell de nes (and is one block in) a wall, and the number indicates how many white cells the wall must contain. The solver is not allowed to add any further walls beyond these.
N3 Walls shall not connect to each other.
N4 Any cell which is not a block in a wall is part of \the maze" { meaning that is a black cell.
N5 The maze must be a single orthogonally (vertically or horizontally) contiguous whole.
N6 The maze is not allowed to have any \rooms" { meaning that the maze may not contain any 2x2 squares of black cells.
Deciding whether there is a solution to Nurikabe is NP-complete [8]. 4.1
Problem representation in ASP is nearly identical with the representation in [1]. We try some modi cations in the representation but they did not a ect the search of the ASP solver, and produce negligible changes in the computational time and e ciency. 4.2
Input and Output: The input is represented as two list of values. Tuples for the rows, columns to express the position of the numbered cells and the values of the numbered cells in the grid. The output is a binary matrix board where [i; j] is 1 if the cell is painted white and 0 otherwise.
In the CP formulation, all constraints related to neighborhood relations are represented as follows: N2 At the start of the puzzle, each numbered cell de nes a wall, and the number indicates how many white cells the wall must contain. forall(k in 1..NumberedCellsRange) m.post((sum(i in 1..r, j in 1..c) board[i,j]==k)) == Number[k]); N3 Walls shall not connect to each other.
forall(i in 2..r-1) //without matrix borders forall(j in 2..c-1) m.post(board[i,j] != 0 =>( (board[i+1,j] == 0 || board[i+1,j] == board[i,j]) && (board[i,j+1] == 0 || board[i,j+1] == board[i,j]) && (board[i,j-1] == 0 || board[i,j-1] == board[i,j]) && (board[i-1,j] == 0 || board[i-1,j] == board[i,j]))); N6 The maze is not allowed to have any \rooms" (meaning that the maze may not contain any 2x2 squares of black cells). forall(i in 1..r-1) forall(j in 1..c-1) m.post(board[i,j] != 0 || board[i+1,j] != 0 || board[i,j+1] != 0 || board[i+1,j+1] != 0);
N 1 and N 4 are de nitions needed for the implementations of the other constraints. The most challenging part of the CP formulation of this puzzle is to represent N 5. This constraint forces all the black cells in the solution to be reachable to each other. The CP representation of \reachability" is not as easy as in ASP, since Comet does not allow transitive closure. Therefore, we have not represented this constraint explicitly in CP, but we do change the search mechanism: we ensure that Comet goes over each computed solution and checks whether the solution satis es the reachability constraint by performing a depth rst search from a black cell to other black cells. If we encounter all the black cells in the search than we say it satis es N 5. 5
Heyawake is played on a rectangular grid whose cells are white or numbered, like in Nurikabe. Furthermore, di erent from Nurikabe, the grid is divided into rooms, as shown in Figure 4. The goal is, like in Nurikabe, to paint some cells black Figure 4, but obeying a di erent set of rules: H1 Painted cells may never be orthogonally connected.
H2 All white cells must be interconnected.
H3 A number (also known as room black cell size) indicates exactly how many painted cells there must be in that particular room.
H4 A room which has no number may contain any number of painted cells (including the possibility of zero cells).
H5 Where a straight (orthogonal) line of connected white cells is formed, it must not contain cells from more than two rooms. In other words, any such line of white cells which connects three or more rooms is forbidden.
Deciding whether there is a solution to Heyawake is NP-complete [5]. 5.1
We modify the ASP representation of Heyawake in [1] for a better computational e ciency.
Input: The initial board is described with two types of atoms:
room(N,R1,C1,R2,C2) indicates the boundaries of the room N as the
rows between R1 R2 and the columns between C1 C2. For
example, in Figure 4, the rst room in the top left corner of the grid is
represented as room(
We have observed that, in the ASP representation of Heyawake in [1] the most time consuming part of the representation is the formulation of the constraint H5 : The atoms that represent length of the vertical (or horizontal) path between two cells, take six arguments, and thus require a lot of time and space consumption since the grounding results in huge number of rules. Therefore, we have reformulated the constraint H5. In this representation: nroom(X,Y) describes that the rooms X and Y are neighbor rooms and inroom(C,R,T) represents that the cell (C; R) is in room T . In addition, the atoms of the form vconnected(C; R; C1; R1) (resp. hconnected(C; R; C1; R1)) represent a vertical (resp. horizontal) straight path between (C; R) and (C1; R1). Using these atoms, we reformulate the constraint H5 as below. It is not allowed that two white cells are connected by a orthogonal path and included in rooms that are not neighbors. The representations of other constraints are the same as in [1]. % H5: It is not allowed that two white cells are straight connected % and included in non neighbor rooms. :- vconnected(C,R,C1,R1), inroom(C,R,T), inroom(C1,R1,T1), not nroom(T,T1), num(T;T1). :- hconnected(C,R,C1,R1), inroom(C,R,T), inroom(C1,R1,T1), not nroom(T,T1), num(T;T1). 5.2
Input: The input is very similar to the input of ASP formulation except that, instead of atoms, we obtain tuples of integers for the boundaries and black cell sizes of the rooms. We preprocess the input and have a matrix NeighborRooms where NeighborRooms[R1,R2] determines whether the rooms R1 and R2 are neighbor or not.
Output: The output is a binary matrix that represents the solution of the puzzle, where the 1s denote the black cells and 0s denote the white cells.
In the CP representation, we have a binary decision variable Grid[i,j] which is 1 if the cell (i; j) in the solution is black; it is 0 if the cell is white. Using this decision variable we represent the constraints as follows: H1 Painted cells can never be orthogonally connected. forall(i in 1..noofRows) forall(j in 1..noofColumns){ if((i-1) > 0)
m.post(Board[i,j] + Board[i-1,j] < 2); if((i+1) <= noofRows)
m.post(Board[i,j] + Board[i+1,j] < 2); if((j-1) > 0)
m.post(Board[i,j] + Board[i,j-1] < 2); if((j+1) <= noofColumns)
m.post(Board[i,j] + Board[i,j+1] < 2); } H3 & H4 A number (also known as room black cell size) indicates exactly how many painted cells there must be in that particular room. A room which has no number may contain any number of painted cells forall(room in 0..noofRooms) if(RoomBlackCellSize[room] > -1) m.post((sum(cell in RoomContains[room])
(Board[cell.r, cell.c]==1))==RoomBlackCellSize[room]); H5 A straight (orthogonal) line of connected white cells is formed, it must not contain cells from two di erent rooms. forall(i in 1..noofRows) forall(j1 in 1..noofColumns) forall(j2 in j1..noofColumns) if(AdjRooms[CellInRoom[i,j1],CellInRoom[i,j2]] != 1) m.post( (Board[i,j1] + Board[i,j2] == 0) => ((sum(k in j1..j2) Board[i,k]) > 0) );
As in Nurikabe, we have not represented the constraint H1 since it requires reachability. Instead, Comet goes over the computed solutions (with a depth rst search fashion) and determine whether there is a solution which satis es reachability. 6
In this section, we present the experimental results for the formulations described in the previous sections. The ASP representations are tested on the ASP solver Clasp (with default settings) version 1.2.1 (Lparse as grounder) and the CP representations are tested on the CP solver Comet (with default settings) version 2. Table 1 shows the results for each puzzle instance. For each puzzle instance we show the computational time that is consumed by each solver5. We compare the program sizes, in terms of number of 5All CPU times are in seconds, for a workstation with a 2.1GHz Intel Core2 Duo T6570 processor and 2,96GB RAM, running MS Windows XP 32 bit. atoms and number of rules for Clasp and number of variables and number of constraints for Comet. In addition, we compare the search strategies of the solvers by means of \number of choices" and \number of con icts" for Clasp, and number of choices and number of fails for Comet. The number of choices, con icts, and fails will give us insights about how much/less the solvers search while nding the solution.
When we look at the results for the Akari instances, we can see that both solvers do not have much di culty solving these puzzles. For the small instances, Clasp performs better; whereas, for the large instances Comet performs better. One can see that number of choices made both by Comet and Clasp are outnumbered by the choices made in other puzzles. In addition, few number of encountered con icts and fails indicate that both solvers solve this problem with few number of search steps.
For the Kakuro instances, Comet nds solutions by doing less search, spending less computational time in comparison with clasp. For these instances, we can say that Comet outperforms clasp. The strength of Comet for these instances can be explained by the usage of the alldifferent propagator which is known to be very e cient constraint. As regards the ASP representation, we have recursive de nitions for the summations which results in huge program after grounding. The summations are handled more easily in CP with an iterative approach.
On the other hand, for the Nurikabe and Heyawake instances, Clasp performs much better than Comet. There are instances for which Clasp nds solutions in a couple of seconds where Comet cannot nd a solution in 10 minutes. Most reasonable explanation for that is the unnatural handling of reachability in CP. In ASP, we represent reachability easily since it allows recursive transitive closure de nitions. On the other hand, we could not nd an e ective reachability representation in CP. Not posting reachability as a constraint but going over the found solutions consumes a lot of time.
As interesting future work, we would like to represent reachability in constraint programming via enumerating all possible paths with all possible lengths between two cells. For that, we keep decision variables for each path between each two cells with each length. As a result, we will force that there exists a path of any length between two cells; by doing that we force reachability of two cells. However, our initial test results using Gecode6, does not seem to be impressing from the point of view of computational e ciency. According to the results of our discussions with Helmut Simonis, we believe that implementing propagators for reachability can be another way for representing reachability in CP, and this will be more e ective to solve Heyawake and Nurikabe. Furthermore, we can use the CP solvers that includes built-in propagators for reachability, like ECLIPSe7. We also try to use the Gecode library for graph concepts, cp(graph) [3], which allows representation of reachability in Gecode; but, we could not manage to use it properly.
Clasp
Comet