了解N皇后问题的CLP(FD)Prolog代码 [英] Understanding CLP(FD) Prolog code of N-queens problem
问题描述
我正在尝试理解N-queens问题的解决方案，如下所示:
I am trying to understand N-queens problem's solution as given below:
:- 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).
我无法理解以下代码段:
I am not able to understand the below snippet:
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).
请帮助我理解.任何帮助将不胜感激.
Please help me to understand. Any help would be greatly appreciated.
推荐答案
由于您没有提供任何示例查询，因此请从一些示例查询开始以确定参数和输出格式.
通常，要确定未知代码的参数和输出格式，需要查看代码以了解参数的结构，然后尝试执行示例查询.另外请注意，此代码使用约束逻辑编程库 clpfd ;当我读到我实际上停止思考语法统一并开始思考约束.我将其视为Prolog中嵌入的独立系统，而不是其他谓词.您会注意到，在此答案中，尽管经常使用constraint，并且即使是Prolog，也很少使用predicate或rule.
Since you did not give any example queries, start with some example queries to determine the parameters and output format.
Normally to determine the parameters and output format for unknown code requires looking at the code for the structure of the arguments and then trying sample queries. Additionally note that this code uses the Constraint Logic Programming library clpfd; when I read that I literally stop thinking syntactic unification and start thinking constraints. I think of it as a separate system embedded within Prolog and not additional predicates. You will notice that in this answer that constraint is used very often and predicate or rule is quite absent even though this is Prolog.
由于N皇后问题众所周知是逻辑问题，因此可以快速进行Google搜索(示例:八个皇后难题.注意，添加关键字clpfd对于理解代码的这种变化至关重要.在其他编程语言中，有许多解决方案.
Since the N-Queens problem is so well known as a logic problem a quick Google search (clpfd n queens) turns up SWI-Prolog Example: Eight queens puzzle. Note the addition of the keyword clpfd it is crucial for understanding this variation of the code; there are many solutions in other programming langues.
这给出了示例查询n_queens(8, Qs), label(Qs)，其中 label/1 返回系统生成的变量的值.
这也告诉我们第一个参数是一个正整数，第二个参数是第一个参数的长度列表.
同样，通过之前解决此问题，第一个参数是木板的尺寸，因此1是1x1木板，8是8x8木板，依此类推，等等.在董事会上.
接下来的事情是知道什么是有效的解决方案，或者至少对于一组参数而言是有效的解决方案.
This gives an example query n_queens(8, Qs), label(Qs) for which label/1 returns values for the system generated variables.
This also tells us that the first argument is a positive integer and the second argument is a list of length of the first argument.
Also by having worked with this problem before, the first argument is the dimensional size of the board, so 1 is 1x1 board, 8 is an 8x8 board, etc., and the number of queens that will be on the board.
The next thing that helps is to know what the valid solutions are or at least a count of them for a set of parameters.
八皇后之谜的Wikipedia文章在
The Wikipedia article for Eight queens puzzle provides that in the counting solutions section. This shows that for a board of 1x1 there is one solution, no solutions for a board of 2x2, or 3x3, two solutions for 4x4 and so on.
对于1x1电路板，只有一种解决方案.
For a 1x1 board there is one solution.
?- n_queens(1,Qs),label(Qs).
Qs = [1].
对于2x2的主板，没有解决方案.
For a 2x2 board there is no solution.
?- n_queens(2,Qs),label(Qs).
false.
对于4x4电路板，有两种解决方案.
For a 4x4 board there are two solutions.
?- 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
To interpret the results the positions in the list correspond with the columns on the board and the values with a row on the board, so for the first value in the list (2) it reads a queen in row 2, column 1, for the second value in the list (4) it reads a queen in row 4, column 2
Qs = [3, 1, 4, 2]
注意:使用棋盘图设置
如果我们使用值作为变量运行查询，则结果将是有效答案的无休止游行.
If we run the query with the values as a variables the result is an endless parade of the valid answers.
?- 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
Now that we know the code runs and gives valid solutions we can start to dissect it.
Normally SWI-Prolog trace/0 or SWI-PRolog GUI-tracer started with gtrace/0 would be a tool of choice but having used that on clpfd before I know that is not a tool of first choice with Constraint Logic Programming. Try it and and you will see why.
剖析.
?- 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.
这很有趣.
为了使这一点更容易理解，请将系统生成的变量替换为用户友好的变量，并人工理解该语句的含义.
This is something of interest.
To make this easier to understand, swap out the system generated variables with user friendly variables and give a human reading to the meaning of the statement.
?- n_queens(2,Qs).
Qs = [A, B],
A in 1..2,
abs(A-B)#\=1,
A#\=B,
B in 1..2.
请注意，对于其中带有#的CLP(FD)运算符，通常是约束条件，例如#\ = 和#= 的读取方式类似于普通运算符，而不是#
Note that with CLP(FD) operators with # in them are typically constraints, e.g. #\= and #= are read like the normal operators less the #
`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`
因此，这些只是一组约束.如果您尝试手动解决约束条件，则会发现没有解决方案，例如
So these are just a set of constraints. If you try to solve the constraints by hand you will find that there is no solution, e.g.
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板进行相同操作
Doing the same for a 4x4 board
?- 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`
要接受一点，但这是逻辑，我们可以重新排列语句，其含义将相同.
That is a bit to take in but this being logic we can rearrange the statements and the meaning will be the same.
因此将类似的语句分组，按变量排序，然后按简单性对组进行排序
So grouping like statements, sorting by variable, then ordering groups by simplicity gives
`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，并且此代码适用于不同尺寸的方形板.
Now to explain the constraints and show how they relate to queens on a square board; note I say square board and not chess board because a chess board is 8x8 and this code works with different dimensional square boards.
A in 1..4
表示A皇后必须放置在4x4板上的位置.在处理约束问题时，您经常发现我们作为人类所理所当然的东西或对常识的思考需要作为特定的约束给出，以防万一.还学习添加常识性规则有时是创建AI解决方案时最困难的任务之一.虽然找不到参考，但是当 Cyc 的创建者添加规则时，时间的概念花了很多时间才做对(没有双关语).其余的约束，例如A in 1..4只是确保没有皇后被放置在棋盘外的位置.
Means that the A queen has to be placed in a position on the 4x4 board. When working with constraint problems you often find that what we as humans take for granted or think of a common sense need to be given as specific constraints, this is a point in case. Also learning that adding rules for common sense is sometimes one of the hardest task when creating AI solutions. While I can not find a reference, when the creators of Cyc were adding rules, the concept of time took a lot of time to get right (no pun intended). The remainder of the constraints like A in 1..4 just ensure that no queen is placed in a position off the board.
A#\=B
为更好地理解此约束，让我们以约束条件定义的4x4板和白色皇后为有效位置，以黑色皇后为无效位置的图片进行制作.
To better understand this constraint lets do a picture with a 4x4 board and white queens as a valid position and the black queen as an invalid position as defined by the constraint.
因此，A是第1行中的白色皇后，而B是第1行中的黑色皇后.由于A不能等于B，这表示如果女王A在第1行中，则女王B可以不在行1中.由于该规则与变量一起使用，这意味着对于B皇后在任何行中，A皇后都不能在该行中.其余的约束，例如A#\=B只是确保没有两个皇后可以在同一行中.
So A is the white queen in row 1 and B is the black queen in row 1. Since A can not equal B this says that if queen A is in row 1 then queen B can not be in row 1. As the rule is used with variables it means that for any row the A queen is in the B queen can not be in that row. The remainder of the constraints like A#\=B just ensure that no two queens can be in the same row.
将此约束视为女王的水平进攻.
Think of this constraint as the horizontal attack for a queen.
abs(A-B)#\=1
为更好地理解此约束，让我们以约束条件定义的4x4板和白色皇后为有效位置，以黑色皇后为无效位置的图片进行制作.
To better understand this constraint lets do a picture with a 4x4 board and white queens as a valid position and the black queen as an invalid position as defined by the constraint.
A 1,2,3,4有四个位置，但是由于该规则是水平对称的(1等于4，而2等于3)，所以我只会做两个.
There are four positions for A 1,2,3,4 but since the rule is symmetric horizontally (1 is the same a 4, and 2 is the same as 3) I will only do two of them.
A为1时.
由于A为1，B不能为2.
1-2 = -1
ABS(-1) = 1
1 can not equal 1.
A为2时.
由于A为2，所以B不能为1.
Since A is 2, B can not be 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的约束
If the constraint using queen A and queen D is examined
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.
Since A is 2, D can be 1.
2-1 = 1
ABS(1) = 1
1 can not equal 3.
由于A为2，所以D可以为2.
Since A is 2, D can be 2.
2-2 = 0
ABS(0) = 0
0 can not equal 3.
由于A为2，所以D可以为3.
Since A is 2, D can be 3.
2-3 = -1
ABS(-1) = 1
1 can not equal 3.
由于A为2，所以D可以为4.
Since A is 2, D can be 4.
2-4 = -2
ABS(-2) = 2
2 can not equal 3.
将此约束视为女王的对角线攻击.
Think of this constraint as the diagonal attack for a queen.
但是等一下，女王可以水平，垂直和对角移动，垂直移动的约束在哪里?
But wait a minute, a queen can move horizontally, vertically and diagonally, where is the constraint for moving vertically?
尽管这在示例查询的输出中未显示为约束，但存在约束.到目前为止，我们有一些限制条件，这些限制条件将皇后的位置限制在棋盘上，水平攻击和对角攻击作为不同的限制，但是数据的结构，长度为N的列表也是一个限制，(A皇后限制到第一列，将B皇后限制到第二列，依此类推.同样，这是学习AI编码的要点之一，就是我们作为人类的思维方式并不总是直接转化为如何用计算机解决问题的方式.因此，尽管此代码使用约束来解决问题，但同时也使用了数据结构.
While this does not appear as a constraint in the output from the example query, there is a constraint. So far we have constraints that limit the positions of the queens to being on the board, the horizontal attack, and the diagonal attack as distinct constraints, however the structure of the data, the list of length N is also a constraint, ([A,B,C,D]) and constrains the A queen to the first column, the B queen to the second column and so on. Again this is one of points of learning to code in AI is that how we think as humans does not always directly translate into how to solve a problem with a computer. So while this code uses constraints to solve a problem, it also uses a data structure.
将列表视为女王的纵队攻击.
Think of the list as the column attack for a queen.
在同一列中不能有两个女王/王后，并且受标量变量中不能有两个值的限制.
No two queens can be in the same column and that is limited by the fact that no two values can be in a scalar variable.
在这一点上，你们中的许多人都将代码的其余部分识别为辅助和递归谓词safe_queens/1以及递归谓词safe_queens/3.
At this point many of you will recognize the remainder of the code as a helper and recursive predicate safe_queens/1 and as a recursive predicate 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).
这是处理列表的标准递归调用，例如
This is a standard recursive call to process a list, e.g.
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).
并运行这些查询，我们看到它生成了一些约束
and run these queries we see that it generates some of the constraints
?- 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).
这是处理列表的标准递归调用，例如
This is a standard recursive call to process a list, e.g.
safe_queens([]).
safe_queens([H|T]) :-
% Process head of list (H)
safe_queens(T). % Process tail of list (T)
以及safe_queens/3的帮助者，因为该语句
and also a helper for safe_queens/3 because this statement
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
and run this query we see that it generates the arguments needed for 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.
但是在您的问题中，您没有询问第一个谓词
However in your question you did not ask about the first predicate
n_queens(N, Qs) :-
length(Qs, N),
Qs ins 1..N,
safe_queens(Qs).
具有
length(Qs,N)
生成具有未绑定变量的长度N的列表
that generates the list of length N with unbound variables
[A,B,C,D]
并具有关键的约束条件声明
and has the crucial constraint statement
Qs ins 1..N
生成类似
A in 1..4
现在，关键差异添加到查询中
Now the crucial difference appended to the query
labels(Qs)
如果使用SWI-Prolog GUI跟踪器并运行代码直到n_queens/2的末尾，您将在调试器中看到约束列表，但没有解决方案
If you use the SWI-Prolog GUI-tracer and run the code up to the end of n_queens/2 you will see in the debugger a list of constraints but not a solution
那是因为那些谓词生成内部维护的约束，直到调用labels/1才解决约束以生成结果.
that is because those predicates generate constraints that are maintained internally, it is not until labels/1 is called that the constraints are solved to generate a result.
这篇关于了解N皇后问题的CLP(FD)Prolog代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
