answer-set-programmingclingo

N-Queens problem using answer set programming

trying to learn answer set programming and decided to give the n-queens problem a go. This is what I have so far:-

% Queens are placed on an n x n chess board.
% Each queens must not attack each other.

% Represent the chess board squares.
square(1..n, 1..n).

% Place a Queen on one chess square.
queen(1..n).
5 { on(Q, X, Y) : queen(Q), square(X, Y) } 5.
:- queen(Q), on(Q, X, Y), on(Q, X', Y'), X != X', Y != Y'.

% Make sure each square only has one queen.
:- queen(Q), queen(Q'), on(Q, X, Y), on(Q', X, Y), Q != Q'.

% A Queen attacks another if both are on the same vertical, horizontal or diagonal.
:- on(Q, X, Y), on(Q', X, Y'), Q != Q', Y != Y'.
:- on(Q, X, Y), on(Q', X', Y), Q != Q', X != X'.
:- on(Q, X, Y), on(Q', X', Y'), Q != Q', |X-X'| = |Y-Y'|.

I am using clingo with the command - clingo n-queens.lp --const n=5 --models 2. The output that I get is:-

clingo output

As you can see, despite stating that the queens should not be in the same column or row, the output contains some. What is wrong with the program?

Do you guys have some tips in general for getting better at ASP? I feel like I always get stuck when trying to describe the knowledge in ASP syntax.

Solution

  • There are 2 issues with your program:

    5 { on(Q, X, Y) : queen(Q), square(X, Y) } 5.

    should be

    n { on(Q, X, Y) : queen(Q), square(X, Y) } n.

    if you want it for anything else than n=5 and

    :- queen(Q), on(Q, X, Y), on(Q, X', Y'), X != X', Y != Y'.

    should be

    :- queen(Q), on(Q, X, Y), on(Q, X', Y'), X != X'.
:- queen(Q), on(Q, X, Y), on(Q, X', Y'), Y != Y'.

    This is because you want to write :- ..., X != X' OR Y != Y' and not :- ..., X != X' AND Y != Y' - causing this constraint to take effect only if both values differ.

    For the output I added also:

    #show on/3.

    tested with the online version of clingo (added #const n=5. to the code):

    clingo version 5.5.0
Reading from stdin
Solving...
Answer: 1
on(2,3,3) on(4,4,5) on(5,2,1) on(1,1,4) on(3,5,2)
SATISFIABLE

    Please note that the online version provides a very neat example of n-queens.

    Your program works but there is room for improvement. If you want to implement efficient code, a first hint would be to reduce the size of the ground logic program. This can be done - for example - by reducing the arity of predicates.