理解N-queens问题的CLP(FD)Prolog代码

Question

我试图了解N-queens问题的解决方案,如下所示:

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

由于您未提供任何示例查询,因此请从一些示例查询开始,以确定参数和输出格式.通常,要确定未知代码的参数和输出格式,需要查看参数结构的代码,然后尝试示例查询.另请注意,此代码使用约束逻辑编程库clpfd ; 当我读到的时候,我完全停止思考句法统一并开始思考约束.我认为它是Prolog中嵌入的独立系统而不是其他谓词.您会注意到,在这个constraint经常使用的答案中,predicate或者rule即使这是Prolog也是如此.

由于N-Queens问题众所周知是一个逻辑问题,因此快速谷歌搜索(clpfd n queens)会出现SWI-Prolog 示例:八个皇后拼图.注意添加关键字clpfd对于理解代码的这种变化至关重要; 其他编程语言中有许多解决方案.

这给出了一个示例查询n_queens(8, Qs), label(Qs),其中label/1返回系统生成的变量的值.这也告诉我们第一个参数是一个正整数,第二个参数是第一个参数的长度列表.还通过具有这个问题的工作之前,第一个参数是所述板的尺寸大小,所以1是1x1板,8是8x8板等,和王后,这将是在板的数量.
接下来要做的就是知道有效解决方案是什么,或者至少知道一组参数的计数.

八维女王拼图的维基百科文章提供了计数解决方案部分.这表明,对于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] 
...

既然我们知道代码运行并提供有效的解决方案,我们就可以开始剖析它了.
通常情况下,SWI-Prolog trace/0或SWI-PRolog GUI-tracer开始使用gtrace/0将是一个选择的工具,但在我知道它不是Constraint Logic Programming的首选工具之前已经在clpfd上使用了它.试试吧,你会明白为什么.

随着解剖.

?- 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本说,如果女王A是第1行中王后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.

如果检查使用女王A和王后的约束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/3to 的第三个参数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)

生成带有未绑定变量的长度为N的列表

[A,B,C,D]

并有关键的约束声明

Qs ins 1..N

产生像这样的约束

A in 1..4

现在,附加到查询的关键差异

labels(Qs)

如果您使用SWI-Prolog GUI跟踪器并运行代码到最后,n_queens/2您将在调试器中看到约束列表但不是解决方案

这是因为这些谓词生成了内部维护的约束,直到labels/1调用约束才能生成结果.