使用答案集编程的 N 皇后问题

Question

尝试学习答案集编程并决定尝试一下 n 皇后问题。这是我目前所拥有的：-

% 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'|.

我正在通过命令使用 clingo - clingo n-queens.lp --const n=5 --models 2。我得到的输出是：-

如您所见，尽管声明皇后不应该在同一列或同一行，但输出包含一些。程序有什么问题？

你们有什么提高 ASP 的一般技巧吗？我觉得在尝试用 ASP 语法描述知识时总是卡住。

Answer 1

你的程序有 2 个问题：

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

应该是

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

如果您想要它用于除 n=5 和

之外的任何用途

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

应该是

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

这是因为您想写 :- ..., X != X' OR Y != Y' 而不是 :- ..., X != X' AND Y != Y' - 导致此约束仅在两个值不同时才生效。

对于我添加的输出：

#show on/3.

使用 online 版本的 clingo 进行测试（在代码中添加 #const n=5.）：

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

请注意，在线版本提供了一个非常简洁的 n 皇后示例。

您的程序有效，但还有改进的余地。如果你想实现高效的代码，第一个提示就是减少基础逻辑程序的大小。这可以通过减少谓词的数量来完成 - 例如 -

使用答案集编程的 N 皇后问题

N-Queens problem using answer set programming

answer-set-programming

clingo