prolog - 操作 Prolog 代码输出

Question

我正在尝试在此页面上运行代码:https://swish.swi-prolog.org/example/clpfd_queens.pl在 Linux 终端上的 swipl 中。

:- use_module(library(clpfd)).

n_queens(N, Qs) :-
    length(Qs, N),
    Qs ins 1..N,
    safe_queens(Qs).

safe_queens([]).
safe_queens([Q|Qs]) :-
    safe_queens(Qs, Q, 1),
    safe_queens(Qs).

safe_queens([], _, _).
safe_queens([Q|Qs], Q0, D0) :-
    Q0 #\= Q,
    abs(Q0 - Q) #\= D0,
    D1 #= D0 + 1,
    safe_queens(Qs, Q0, D1).

以下命令有效:

?- n_queens(4, Qs), labeling([ff], Qs).

但不仅仅是n_queens(4, Qs):

?- n_queens(4, Qs).
Qs = [_G1470, _G1473, _G1476, _G1479],
_G1470 in 1..4,
abs(_G1470-_G1479)#\=3,
_G1470#\=_G1479,
abs(_G1470-_G1476)#\=2,
_G1470#\=_G1476,
abs(_G1470-_G1473)#\=1,
_G1470#\=_G1473,
_G1479 in 1..4,
abs(_G1476-_G1479)#\=1,
_G1476#\=_G1479,
abs(_G1473-_G1479)#\=2,
_G1473#\=_G1479,
_G1476 in 1..4,
abs(_G1473-_G1476)#\=1,
_G1473#\=_G1476,
_G1473 in 1..4.

为什么这里需要labeling部分？在没有标签的情况下可以获得正确的输出吗？

对于较大的数字，人们只能得到解决方案的初始部分:

?- n_queens(20, Qs), labeling([ff], Qs).
Qs = [1, 3, 5, 14, 17, 4, 16, 7, 12|...] ;
Qs = [1, 3, 5, 18, 16, 4, 10, 7, 14|...] ;
...

如何获得较大数字的完整列表输出？另外，如何才能将所有数字组合在一起，而不必为每个解决方案按空格键？感谢您的帮助。

Answer 1

n_queens/2 确实没有解决N个皇后的N皇后问题:它构造约束规划问题:它构造N个变量(皇后的列)，并在这些皇后之间添加约束:例如两个皇后不能放在同一行，也不在同一条对角线上。如果我们将问题输出重写为更方便的输出，我们就会看到这一点:

A in 1..4,
abs(A-D)#\=3,
A#\=D,
abs(A-C)#\=2,
A#\=C,
abs(A-B)#\=1,
A#\=B,
D in 1..4,
abs(C-D)#\=1,
C#\=D,
abs(B-D)#\=2,
B#\=D,
C in 1..4,
abs(B-C)#\=1,
B#\=C,
B in 1..4.

所以我们看到四个皇后(A、B、C 和 D)。每个皇后都应该在域 1..4 中，此外，我们看到像 A #\= D 这样的非相等约束，以防止第一个皇后 A 与最后一位皇后 D 共享一列。我们最终看到像 abs(A-C) #\= 2 这样的约束，以防止第一个皇后 A 和第三个皇后 C 使两列不同(直接攻击)。

下一步labeling/2实际上将解决问题:它执行松弛(减少域)以及分支(为变量选择一个值或值的子范围) )并在约束失败时回溯。它会一直持续下去，直到找到解决方案，我们可以利用Prolog的回溯机制让labeling/2想出更多的解决方案。

labeling 因此给出了一个变量列表，并旨在标记它们:为它们分配一个超出范围的值，以满足所有约束。

因此，与实际求解部分相比，问题构造部分通常非常快:很容易生成 O(N) 个变量和 O(N²) 约束，但可能需要指数级的时间 O(D^N) 才能得出满足所有约束的解决方案。

Also, how can one get all numbers together, without having to press spacebar for each solution?

您可以使用元谓词 findall/3 来实现:

all_n_queens(N,LL) :-
    <b>findall(L,</b>(n_queens(N,<b>L</b>), labeling([ff], <b>L</b>)),<b>LL)</b>.

生成:

?- all_n_queens(5,LL).
LL = [[1, 3, 5, 2, 4], [1, 4, 2, 5, 3], [2, 4, 1, 3, 5], [2, 5, 3, 1, 4], [3, 1, 4, 2|...], [3, 5, 2|...], [4, 1|...], [4|...], [...|...]|...].

How can one get full list output for larger numbers?

您可以设置answer_write_options标志:

?- set_prolog_flag(answer_write_options,[max_depth(0)]).
true.

?- all_n_queens(5,LL).
LL = [[1,3,5,2,4],[1,4,2,5,3],[2,4,1,3,5],[2,5,3,1,4],[3,1,4,2,5],[3,5,2,4,1],[4,1,3,5,2],[4,2,5,3,1],[5,2,4,1,3],[5,3,1,4,2]].