prolog - 了解N皇后问题的CLP(FD)Prolog代码

Question

我正在尝试理解N-皇后问题的解决方案，如下所示:

:- 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).

我无法理解以下代码段:

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

请帮助我理解。任何帮助将不胜感激。

Answer 1

由于您没有提供任何示例查询，因此从一些示例查询开始，以确定参数和输出格式。
通常，要确定未知代码的参数和输出格式，需要查看代码以了解参数的结构，然后尝试执行示例查询。另外请注意，此代码使用Constraint Logic Programming库clpfd；当我读到它时，我实际上停止了思考syntactic unification并开始考虑constraints。我将其视为Prolog中嵌入的独立系统，而不是其他谓词。您会注意到，在此答案中，即使是Prolog，也经常使用constraint，并且相当缺少predicate或rule。

由于N皇后问题是众所周知的逻辑问题，因此Google的快速搜索(clpfd n queens)出现了SWI-Prolog Example: Eight queens puzzle。请注意，添加了关键字clpfd对于理解代码的这种变化至关重要。其他编程语言中还有many解决方案。

这给出了一个示例查询n_queens(8, Qs), label(Qs)，其label/1返回系统生成的变量的值。
这也告诉我们第一个参数是一个正整数，第二个参数是第一个参数的长度列表。
同样，通过之前解决此问题，第一个参数是木板的尺寸，因此1是1x1木板，8是8x8木板，等等，以及板上的皇后数。
接下来的事情是知道什么是有效的解决方案，或者至少对于一组参数而言是有效的解决方案。

Eight queens puzzle的Wikipedia文章在counting solutions部分提供了该内容。
这表明对于1x1的电路板，有一个解决方案，对于2x2或3x3的电路板，没有解决方案，对于4x4的电路板，有两个解决方案，依此类推。

对于1x1电路板，有一种解决方案。

?- n_queens(1,Qs),label(Qs).
Qs = [1].

对于2x2板，没有解决方案。

?- n_queens(2,Qs),label(Qs).
false.

对于4x4板，有两种解决方案。

?- n_queens(4,Qs),label(Qs).
Qs = [2, 4, 1, 3] ;
Qs = [3, 1, 4, 2] ;
false.

Qs = [2, 4, 1, 3]

为了解释结果，列表中的位置与板上的列相对应，值与板上的一行相对应，因此对于列表中的第一个值( 2)，它读取 a queen in row 2, column 1，对于列表中的第二个值( 4) )它读取 a queen in row 4, column 2

Qs = [3, 1, 4, 2]

注意:使用 Chess Diagram Setup生成的图像

如果我们使用值作为变量运行查询，结果将是有效答案的无休止游行。

?- n_queens(N,Qs),label(Qs).
N = 0,
Qs = [] ;
N = 1,
Qs = [1] ;
N = 4,
Qs = [2, 4, 1, 3] ;
N = 4,
Qs = [3, 1, 4, 2] ;
N = 5,
Qs = [1, 3, 5, 2, 4] ;
N = 5,
Qs = [1, 4, 2, 5, 3] ;
N = 5,
Qs = [2, 4, 1, 3, 5] ;
N = 5,
Qs = [2, 5, 3, 1, 4] ;
N = 5,
Qs = [3, 1, 4, 2, 5] ;
N = 5,
Qs = [3, 5, 2, 4, 1] ;
N = 5,
Qs = [4, 1, 3, 5, 2] 
...

现在我们知道代码已运行并提供了有效的解决方案，我们可以开始对其进行剖析。
通常，以 gtrace/0开头的SWI-Prolog trace/0或SWI-PRolog GUI-tracer将是一种选择的工具，但是在clpfd上使用了它之后，我才知道 Constraint Logic Programming不是首选的工具。试试看，您会明白为什么。

在解剖上。

?- n_queens(1,Qs).
Qs = [1].

?- n_queens(2,Qs).
Qs = [_1942, _1948],
_1942 in 1..2,
abs(_1942-_1948)#\=1,
_1942#\=_1948,
_1948 in 1..2.

这很有趣。
为了使这一点更容易理解，请将系统生成的变量替换为用户友好的变量，并人工理解该语句的含义。

?- n_queens(2,Qs).
Qs = [A, B],
A in 1..2,
abs(A-B)#\=1,
A#\=B,
B in 1..2.

请注意，对于其中带有 #的CLP(FD)运算符，通常是约束条件，例如像普通运算符一样读取 #\=和 #=，而不是 #

`A in 1..2`    reads the value for `A` must be in the range `1..2`
`abs(A-B)#\=1` reads the difference of the values between `A` and `B` must not equal 1
`A#\=B`        reads the value of `A` must not equal the value of `B`
`B in 1..2`    reads the value of `B` must be in `1..2`

因此，这些只是一组约束。如果您尝试手动解决约束条件，则会发现没有解决方案，例如

0,_  invalid by `A in 1..2`
_,0  invalid by `B in 1..2`
3,_  invalid by `A in 1..2`
_,3  invalid by `B in 1..2`
1,1  invalid by `A#\=B` 
1,2  invalid by `abs(A-B)#\=1`
2,1  invalid by `abs(A-B)#\=1`
2,2  invalid by `A#\=B` 

对4x4板做相同的操作

?- n_queens(4,Qs).
Qs = [_5398, _5404, _5410, _5416],
_5398 in 1..4,
abs(_5398-_5416)#\=3,
_5398#\=_5416,
abs(_5398-_5410)#\=2,
_5398#\=_5410,
abs(_5398-_5404)#\=1,
_5398#\=_5404,
_5416 in 1..4,
abs(_5410-_5416)#\=1,
_5410#\=_5416,
abs(_5404-_5416)#\=2,
_5404#\=_5416,
_5410 in 1..4,
abs(_5404-_5410)#\=1,
_5404#\=_5410,
_5404 in 1..4.

?- n_queens(4,Qs).
Qs = [A, B, C, D],
A in 1..4,     reads the value for `A` must be in the range `1..4`
abs(A-D)#\=3,  reads the difference of the values between `A` and `D` must not equal 3
A#\=D,         reads the value of `A` must not equal the value of `D`
abs(A-C)#\=2,  reads the difference of the values between `A` and `C` must not equal 2
A#\=C,         reads the value of `A` must not equal the value of `C`
abs(A-B)#\=1,  reads the difference of the values between `A` and `B` must not equal 1
A#\=B,         reads the value of `A` must not equal the value of `B`
D in 1..4,     reads the value for `D` must be in the range `1..4`
abs(C-D)#\=1,  reads the difference of the values between `C` and `D` must not equal 1
C#\=D,         reads the value of `C` must not equal the value of `D`
abs(B-D)#\=2,  reads the difference of the values between `B` and `D` must not equal 2
B#\=D,         reads the value of `B` must not equal the value of `D`
C in 1..4,     reads the value for `C` must be in the range `1..4`
abs(B-C)#\=1,  reads the difference of the values between `B` and `C` must not equal 1
B#\=C,         reads the value of `B` must not equal the value of `C`
B in 1..4.     reads the value for `B` must be in the range `1..4`

可以接受一点，但这是逻辑，我们可以重新排列语句，其含义将相同。

因此，将类似的语句分组，按变量排序，然后按简单性对组进行排序，得出

`A in 1..4`    reads the value for `A` must be in the range `1..4`
`B in 1..4`    reads the value for `B` must be in the range `1..4`   
`D in 1..4`    reads the value for `D` must be in the range `1..4`
`C in 1..4`    reads the value for `C` must be in the range `1..4` 
`A#\=B`        reads the value of `A` must not equal the value of `B`
`A#\=C`        reads the value of `A` must not equal the value of `C`
`A#\=D`        reads the value of `A` must not equal the value of `D`
`B#\=C`        reads the value of `B` must not equal the value of `C`
`B#\=D`        reads the value of `B` must not equal the value of `D`
`C#\=D`        reads the value of `C` must not equal the value of `D`
`abs(A-B)#\=1` reads the difference of the values between `A` and `B` must not equal 1
`abs(A-C)#\=2` reads the difference of the values between `A` and `C` must not equal 2
`abs(A-D)#\=3` reads the difference of the values between `A` and `D` must not equal 3
`abs(B-C)#\=1` reads the difference of the values between `B` and `C` must not equal 1
`abs(B-D)#\=2` reads the difference of the values between `B` and `D` must not equal 2
`abs(C-D)#\=1` reads the difference of the values between `C` and `D` must not equal 1

现在解释约束并显示它们与方形板上的皇后有何关系；请注意，我说的是方形板，而不是国际象棋板，因为国际象棋板是8x8，并且此代码适用于不同尺寸的方形板。
A in 1..4
意味着 A皇后必须放置在4x4板上的位置。在处理约束问题时，您通常会发现我们作为人类所想当然的东西或对常识的思考需要作为特定的约束给出，以防万一。还学习添加常识规则有时是创建AI解决方案时最困难的任务之一。虽然我找不到参考，但是当 Cyc的创建者添加规则时，时间的概念花了很多时间才能正确(没有双关语)。其余约束(如 A in 1..4)仅确保没有女王放置在板上。
A#\=B
为了更好地理解此约束，让我们用约束定义的4x4板和白色皇后为有效位置，将黑色皇后为无效位置的图片制作。



因此， A是第1行中的白色皇后，而 B是第1行中的黑色皇后。由于A不能等于B，这表示如果Queen A在第1行中，则Queen B不能在第1行中。使用该规则如果使用变量，则表示 A皇后所在的任何行都不能位于 B皇后所在的行中。其余约束(如 A#\=B)仅确保没有两个皇后可以在同一行中。

将此约束视为女王的水平攻击。
abs(A-B)#\=1
为了更好地理解此约束，让我们用约束定义的4x4板和白色皇后为有效位置，将黑色皇后为无效位置的图片制作。
A 1,2,3,4有四个位置，但是由于该规则是水平对称的(1等于4，而2等于3)，所以我只会做两个。

当 A为1。



由于 A为1，因此 B不能为2。

1-2 = -1
ABS(-1) = 1
1 can not equal 1.

当 A为2。



由于 A为2，因此 B不能为1。

2 - 1 = 1
ABS(1) = 1
1 can not equal 1.

由于 A为2，因此 B不能为3。

2 - 3 = -1
ABS(-1) = 1
1 can not equal 1.

如果检查了使用Queen A和Queen D的约束
abs(A-D)#\=3
当 A为1。



由于 A为1，因此 D不能为4。

1-4 = -3
ABS(-3) = 3
3 can not equal 1.

当 A为2。

由于 A是2，因此 D可以是 1。

2-1 = 1
ABS(1) = 1
1 can not equal 3.

由于 A是2，因此 D可以是 2。

2-2 = 0
ABS(0) = 0
0 can not equal 3.

由于 A是2，因此 D可以是 3。

2-3 = -1
ABS(-1) = 1
1 can not equal 3.

由于 A是2，因此 D可以是 4。

2-4 = -2
ABS(-2) = 2
2 can not equal 3.

将此约束视为女王的对角线攻击。

但是等一下，女王可以水平，垂直和对角移动，垂直移动的约束在哪里？

尽管这在示例查询的输出中未显示为约束，但存在约束。到目前为止，我们有一些限制条件，将皇后区的位置限制在板上，水平攻击和对角线攻击是不同的限制，但是数据的结构，长度为N的列表也是一个限制，( [A,B,C,D])并将 A皇后限制到第一列，将 B皇后限制到第二列，依此类推。再次，这是学习AI编码的要点之一，就是我们作为人类的思维方式并不总是直接转化为如何用计算机解决问题的方式。因此，尽管此代码使用约束来解决问题，但它也使用数据结构。

将列表视为女王的纵队攻击。

在同一列中不能有两个皇后，并且受以下事实限制:在标量变量中不能有两个值。



在这一点上，您中的许多人都将代码的其余部分视为帮助程序和递归谓词 safe_queens/1以及递归谓词 safe_queens/3。

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

这是处理列表的标准递归调用，例如

safe_queens([], _, _).
safe_queens([H|T], _, _) :-
    % Process head of list (H)
    safe_queens(T, _, _). % Process tail of list (T)

这两个陈述

Q0 #\= Q
abs(Q0 - Q) #\= D0

上面已经解释了

和

D1 #= D0 + 1

将 D1设置为 D0 + 1
如果我们这样修改谓词

permutations([], _, _).
permutations([Q|Qs], Q0, D0) :-
    write(Q0),write('#\\='),writeln(Q),
    write('abs('),write(Q0),write('-'),write(Q),write(')#\\='),writeln(D0),
    D1 is D0 + 1,
    permutations(Qs, Q0, D1).

并运行这些查询，我们看到它生成了一些约束

?- permutations(['B','C','D'],'A',1).
A#\=B
abs(A-B)#\=1
A#\=C
abs(A-C)#\=2
A#\=D
abs(A-D)#\=3
true.

?- permutations(['C','D'],'B',1).
B#\=C
abs(B-C)#\=1
B#\=D
abs(B-D)#\=2
true.

?- permutations(['D'],'C',1).
C#\=D
abs(C-D)#\=1
true.

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

这是处理列表的标准递归调用，例如

safe_queens([]).
safe_queens([H|T]) :-
    % Process head of list (H)
    safe_queens(T). % Process tail of list (T)

也是 safe_queens/3的助手，因为此语句

    safe_queens(Qs, Q, 1)

将 safe_queens/3的第三个参数初始化为 1
如果我们这样修改谓词

generate_args([]).
generate_args([Q|Qs]) :-
    write('Qs: '),write(Qs),write(', Q: '),write(Q),writeln(', 1'),
    generate_args(Qs).

并运行此查询，我们看到它生成了 safe_queens/3所需的参数

?- generate_args(['A','B','C','D']).
Qs: [B,C,D], Q: A, 1
Qs: [C,D], Q: B, 1
Qs: [D], Q: C, 1
Qs: [], Q: D, 1
true.

但是，在您的问题中，您没有询问第一个谓词

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

其中有

length(Qs,N)

生成具有未绑定(bind)变量的长度N的列表

[A,B,C,D]

并具有关键的约束条件声明

Qs ins 1..N

产生像

A in 1..4

现在，关键差异附加到查询中

labels(Qs)

如果使用SWI-Prolog GUI跟踪器并运行代码直到 n_queens/2的末尾，您将在调试器中看到约束列表，但没有解决方案



这是因为这些谓词生成内部保留的约束，直到调用 labels/1才解决约束以生成结果。