处理 Prolog 代码输出

Manipulating Prolog code output

我正在尝试 运行 此页面上的代码: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 部分?没有 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|...] ;
...

如何获得较大数字的完整列表输出?此外,如何将所有数字放在一起,而不必为每个解决方案按空格键?感谢您的帮助。

n_queens/2 not 解决了 N-queens 问题 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.

所以我们看到四个皇后 (ABCD)。每个皇后都应该在域 1..4 中,此外我们看到不相等的约束,如 A #\= D 以防止第一个皇后 A 与最后一个皇后 D 共享一个列。我们终于看到像 abs(A-C) #\= 2 这样的约束来防止第一个皇后 A 和第三个皇后 C 区分两列(对角攻击)。

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

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

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

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]].