理解 N-queens 问题的 CLP(FD) Prolog 代码 [英] Understanding CLP(FD) Prolog code of N-queens problem
问题描述
我正在尝试理解 N 皇后问题的解决方案，如下所示:
:- use_module(library(clpfd)).n_queens(N, Qs) :-长度(Qs，N)，Qs ins 1..N,安全皇后(Qs).安全皇后([]).安全皇后([Q|Qs]):-safe_queens(Qs, Q, 1),安全皇后(Qs).安全女王([]，_，_).safe_queens([Q|Qs], Q0, D0) :-Q0 #= Q,绝对(Q0 - Q)#= D0，D1 #= D0 + 1,安全皇后(Qs，Q0，D1).我无法理解以下片段:
safe_queens([]).安全皇后([Q|Qs]):-safe_queens(Qs, Q, 1),安全皇后(Qs).安全女王([]，_，_).safe_queens([Q|Qs], Q0, D0) :-Q0 #= Q,绝对(Q0 - Q)#= D0，D1 #= D0 + 1,安全皇后(Qs，Q0，D1).请帮助我理解.任何帮助将不胜感激.
由于您没有给出任何示例查询，所以先从一些示例查询开始确定参数和输出格式.通常，要确定未知代码的参数和输出格式，需要查看参数结构的代码，然后尝试示例查询.另外请注意，此代码使用
为了解释结果，列表中的位置对应于板上的列，值对应于板上的一行，因此对于列表中的第一个值 (2)，它读取 第 2 行第 1 列中的一个皇后，对于列表中的第二个值 (4)，它读取 第 4 行第 2 列中的一个皇后
Qs = [3, 1, 4, 2]注意:使用
所以 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 = -1ABS(-1) = 11 不能等于 1.当A为2时.
由于A是2，所以B不可能是1.
2 - 1 = 1ABS(1) = 11 不能等于 1.由于A是2，所以B不可能是3.
2 - 3 = -1ABS(-1) = 11 不能等于 1.如果使用queen A和queen D的约束被检查
abs(A-D)#=3
当A为1时.
由于A是1，所以D不可能是4.
1-4 = -3ABS(-3) = 33不能等于1.当A为2时.
由于 A 是 2，所以 D 可以是 1.
2-1 = 1ABS(1) = 11不能等于3.由于 A 是 2，所以 D 可以是 2.
2-2 = 0ABS(0) = 00 不能等于 3.由于 A 是 2，所以 D 可以是 3.
2-3 = -1ABS(-1) = 11不能等于3.由于 A 是 2，所以 D 可以是 4.
2-4 = -2ABS(-2) = 22不能等于3.将此约束视为皇后的对角线攻击.
<小时>但是等一下，女王可以水平、垂直和对角移动，垂直移动的限制在哪里?
虽然这不会在示例查询的输出中显示为约束，但存在约束.到目前为止，我们有限制皇后在棋盘上的位置，水平攻击和对角线攻击作为不同的约束，但是数据的结构，长度为 N 的列表也是一个约束，([A,B,C,D]) 并将 A 女王限制在第一列，将 B 女王限制在第二列，依此类推.同样，在 AI 中学习编码的要点之一是，我们作为人类的思考方式并不总是直接转化为如何用计算机解决问题.因此，虽然这段代码使用约束来解决问题，但它也使用了数据结构.
将列表想象成对皇后的纵队攻击.
没有两个皇后可以在同一列中，这受到以下事实的限制:一个标量变量中不能有两个值.
<小时>此时，你们中的许多人将把代码的其余部分识别为辅助和递归谓词 safe_queens/1 和递归谓词 safe_queens/3.p><小时>
safe_queens([], _, _).safe_queens([Q|Qs], Q0, D0) :-Q0 #= Q,绝对(Q0 - Q)#= D0，D1 #= D0 + 1,安全皇后(Qs，Q0，D1).这是处理列表的标准递归调用，例如
safe_queens([], _, _).安全皇后([H|T]，_，_):-% 进程列表头 (H)安全女王(T，_，_).% 处理列表尾部 (T)这两条语句
Q0 #= Q绝对(Q0 - Q)#= D0上面已经解释过了
和
D1 #= D0 + 1将 D1 设置为 D0 + 1
如果我们这样修改谓词
排列([]，_，_).排列([Q|Qs]，Q0，D0):-写(Q0),写('#\='),writeln(Q),write('abs('),write(Q0),write('-'),write(Q),write(')#\='),writeln(D0),D1 是 D0 + 1，排列(Qs，Q0，D1).并运行这些查询，我们看到它生成了一些约束
?- 排列(['B','C','D'],'A',1).A#=B绝对(A-B)#=1A#=C绝对(A-C)#=2A#=D绝对(A-D)#=3真的.?- 排列(['C','D'],'B',1).B#=C绝对(B-C)#=1B#=D绝对(B-D)#=2真的.?- 排列(['D']，'C'，1).C#=D绝对(C-D)#=1真的.<小时>
safe_queens([]).安全皇后([Q|Qs]):-safe_queens(Qs, Q, 1),安全皇后(Qs).这是处理列表的标准递归调用，例如
safe_queens([]).安全皇后([H|T]):-% 进程列表头 (H)安全皇后(T).% 处理列表尾部 (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'),生成参数(Qs).并运行这个查询，我们看到它生成了 safe_queens/3 所需的参数
?- generate_args(['A','B','C','D']).问:[B，C，D]，问:A，1问:[C,D]，问:B，1问:[D]，问:C，1问:[]，问:D，1真的.<小时>
但是在你的问题中你没有问第一个谓词
n_queens(N, Qs) :-长度(Qs，N)，Qs ins 1..N,安全皇后(Qs).有
长度(Qs,N)生成具有未绑定变量的长度为 N 的列表
[A,B,C,D]并且有关键的约束声明
Qs ins 1..N生成类似的约束
1..4 中的 A现在附加到查询的关键区别
标签(Qs)如果您使用 SWI-Prolog GUI-tracer 并将代码运行到 n_queens/2 的末尾，您将在调试器中看到约束列表，但不是解决方案
那是因为这些谓词生成了内部维护的约束，直到调用 labels/1 才解决约束以生成结果.
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.
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.
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.
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.
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.
For a 1x1 board there is one solution.
?- n_queens(1,Qs),label(Qs).
Qs = [1].
For a 2x2 board there is no solution.
?- n_queens(2,Qs),label(Qs).
false.
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]
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]
Note: Images generated using Chess Diagram Setup
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]
...
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.
On with the dissection.
?- 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.
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`
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
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
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
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.
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
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.
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.
When A is 1.
Since A is 1, B can not be 2.
1-2 = -1
ABS(-1) = 1
1 can not equal 1.
When A is 2.
Since A is 2, B can not be 1.
2 - 1 = 1
ABS(1) = 1
1 can not equal 1.
Since A is 2, B can not be 3.
2 - 3 = -1
ABS(-1) = 1
1 can not equal 1.
If the constraint using queen A and queen D is examined
abs(A-D)#=3
When A is 1.
Since A is 1, D can not be 4.
1-4 = -3
ABS(-3) = 3
3 can not equal 1.
When A is 2.
Since A is 2, D can be 1.
2-1 = 1
ABS(1) = 1
1 can not equal 3.
Since A is 2, D can be 2.
2-2 = 0
ABS(0) = 0
0 can not equal 3.
Since A is 2, D can be 3.
2-3 = -1
ABS(-1) = 1
1 can not equal 3.
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?
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.
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)
These two statements
Q0 #= Q
abs(Q0 - Q) #= D0
are explained above
and
D1 #= D0 + 1
sets D1 to D0 + 1
If we modify the predicate as such
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)
and also a helper for safe_queens/3 because this statement
safe_queens(Qs, Q, 1)
initializes the third argument for safe_queens/3 to 1
If we modify the predicate as such
generate_args([]).
generate_args([Q|Qs]) :-
write('Qs: '),write(Qs),write(', Q: '),write(Q),writeln(', 1'),
generate_args(Qs).
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).
which has
length(Qs,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
that generates the constraints like
A in 1..4
Now the crucial difference appended to the query
labels(Qs)
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
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-queens 问题的 CLP(FD) Prolog 代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
