使用答案集规划的N-Queens问题

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

您的程序有两个问题：

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.

使用在线版本的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-皇后的例子。

你的计划可行，但仍有改进的余地。如果您想要实现高效的代码，第一个提示将是减少地面逻辑程序的大小。例如，可以通过减少谓词的重要性来做到这一点。