Search code examples
answer-set-programming

Contiguous group of cells in grid

I'm working on a puzzle solver (nonograms, griddler, picross...) just for fun and to learn a bit more of ASP. (You can read more about these puzzles in wikipedia https://en.wikipedia.org/wiki/Nonogram)

I want to check if there's a horizontal contiguous group of black colored cells (cell(I,J,o)) surrounded by two white cells (cell(I,J,x)), one to the left and one to the right of the group.

#const rows = 3.
#const cols = 3.

symbol(x;o).

row(0..rows+1).
col(0..cols+1).

% Padding surrounding the puzzle so we can check every group's surroundings
cell(I,0,x) :- row(I).
cell(I,cols+1,x) :- row(I).  
cell(0,J,x) :- col(J).
cell(cols+1,J,x) :- col(J).

% Assign symbols to every cell available
1 { cell(I, J, S) : symbol(S) } 1 :- row(I), col(J).

% Horizontal block (row,starting col,length)
hblock(I,J1,L) :- row(I), col(J1), col(J2), J1 <= J2, L = J2-J1+1, 
                    col(J1-1), col(J2+1), cell(I,J1..J2,o),
                    cell(I,J1-1,x), cell(I,J2+1,x).

% Output only cells that are not padding
out_cell(I,J,S) :- cell(I,J,S), I > 0, J > 0, I <= rows, J <= cols.

#hide.
#show hblock/3.
#show out_cell/3.

As you can see I'm using cell(I,J1..J2,o) in the hblock/3 definition to check that every cell between col(J1) and col(J2) is black (marked with the o symbol), but when given the following input:

cell(1,1,x). cell(1,2,x). cell(1,3,x).
cell(2,1,o). cell(2,2,x). cell(2,3,o).
cell(3,1,x). cell(3,2,x). cell(3,3,x).

It outputs hblock(2,3,1) hblock(2,1,3) hblock(2,1,1), which means that it's detecting two blocks of a single black cell (In (2,1) and (2,3)) and a larger block of three black cells between (2,1) and (2,3), but it shouldn't be detected as it has a cell marked with x in the middle...

What am I doing wrong?

Solution

  • If I recall correctly, cell(I,J1..J2,o) will generate separate rules for each number between J1 and J2. It doesn't expand them on the same line i.e. in one rule. So

    hblock(I,J1,L) :- row(I), col(J1), col(J2), J1 <= J2, L = J2-J1+1, 
                col(J1-1), col(J2+1), cell(I,J1..J2,o),
                cell(I,J1-1,x), cell(I,J2+1,x).

    expands to

    ...
hblock(1,1,1) :- cell(1,1,o).
hblock(1,2,1) :- cell(1,2,o).
hblock(1,3,1) :- cell(1,3,o).
hblock(1,1,2) :- cell(1,1,o).
hblock(1,1,2) :- cell(1,2,o).
hblock(1,2,2) :- cell(1,2,o).
hblock(1,2,2) :- cell(1,3,o).
hblock(1,1,3) :- cell(1,1,o).
hblock(1,1,3) :- cell(1,2,o).
hblock(1,1,3) :- cell(1,3,o).
...

    I didn't get as far as figuring out why hblock(2,1,2) and hblock(2,2,2) are missing, but that's probably not very relevant.