constraint-programminganswer-set-programmingclingo

Newbie question about the difference between integrity constraints and choice rules in ASP/Clingo?


#const w = 2.
#const h = 1.

% Create a grid wxh
row(1..h).
col(1..w).

% Generate
% {} below indicates all rooms need not exist in the solution.
% There can be 1x1 rooms, that can be placed anywhere on the grid.
{room11(X, Y) : col(X), row(Y) }.
% 2x1 (width 2) rooms can be placed anywhere except the last column,
% because that will take it out of the grid
{room21(X, Y) : col(X), col(X+1), row(Y) }.

% Calculate what areas the generated rooms cover.
% Multiple rooms covering the same X,Y , or no room covering it,
% would indicate a invalid model.

% A 1x1 room covers its own location. 
covered(room11(X, Y), X, Y) :- room11(X, Y) .

% Put all generated rooms in a list
_r(room11(X, Y)) :- room11(X, Y) .

% A 2x1 room covers X, Y and X+1, Y
covered(room21( X, Y), X, Y) :- room21(X, Y) .
covered(room21( X-1, Y), X, Y) :- room21(X-1, Y) .

% Put all generated rooms in a list
_r(room21(X, Y)) :- room21(X, Y) .

% Each grid point can be covered by one and only one room.
% There can be only one covered(_,X,Y) in the model.
1 {covered(R, X, Y) : _r(R) } 1 :- col(X), row(Y) .

% Count the number of cover(_, X, Y) atoms for debugging
cc (X, Y, N) :- N = {covered(R, X, Y) : _r(R) } , col(X), row(Y) .

Explained my thinking in the comments above.

I am expecting 2 answers

room11(1,1) room11(2,1)

and

room21(1,1)

But when I enumerate all answers, I get a lot of other inconsistent answers too.

What am I doing wrong?

Answer: 1
row(1) col(1) col(2) room11(1,1) _r(room11(1,1)) 
covered(room11(1,1),1,1) cc(1,1,1) covered(room11(1,1),2,1) cc(2,1,1)

How is the atom covered(room11(1,1),2,1) coming into being? Is 1 {covered(R, X, Y) : _r(R) } 1 :- col(X), row(Y) . causing this? What is the correct way to write this?

Answer: 10
row(1) col(1) col(2)
room11(1,1) room11(2,1) _r(room11(1,1)) _r(room11(2,1)) room21(1,1) _r(room21(1,1))
covered(room21(1,1),1,1) covered(room21(1,1),2,1)
cc(1,1,1) cc(2,1,1)

How can room11(1,1) be true but covered(room11(1,1),1,1) be not true/not present in the model?


Solution

  • Everthing in the head of a rule can be derived. You do not want to derived covered/2 without a reason. Therefore, you have to replace your generating rule for covered/2 with this one:

    % Each grid point can be covered by one and only one room.
    % There can be only one covered(_,X,Y) in the model.
    :- 1 != {covered(R, X, Y)}, col(X), row(Y).
    

    This gives you the 2 expected solutions.

    PS: If you want to generalize your encoding you should put the dimensions of the room as parameters to the room predicate, e.g. room(Width,Height,PosX,PosY).