提示了解解决皇后区精彩计划的方法 [英] Hints to understand splendid program to solve Queens
问题描述
Sterling&的序言的艺术夏皮罗(Shapiro)，练习第14.1(v)节:
In Art of Prolog of Sterling & Shapiro, exercise Section 14.1 (v):
queens(N,Qs) :-
length(Qs,N),
place_queens(N,Qs,_,_).
place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
I > 0, I1 is I-1,
place_queens(I1,Qs,[_|Ups] ,Downs),
place_queen(I,Qs,Ups,Downs).
place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
place_queen(Q,Qs,Ups,Downs).
这是一个出色的程序，共有11行，可以快速解决在棋盘上放置皇后的问题.这很神奇:只有一个计数器，递归和列表变得越来越长.我，即使在跟踪的帮助下，也不了解它.有人可以向我解释吗?您如何编写这样的程序?导致从例如另一个(好的标准解决方案)派生该程序的逻辑/心理过程是什么?
It is a splendid program, in 11 lines, which quickly solves the problem of positioning queens on a chessboard. It's magical: there is only a counter, recursion, and lists that get longer and shorter. I, even with the help of trace, don't understand it. Can someone explain it to me? How do you get to write such a program? What is the logical / mental process that leads to derive this program from, for example, this other (good standard solution):
queens(N,Qs) :-
numlist(1,N,Ns),
queens(Ns,[ ],Qs).
queens(UnplacedQs,SafeQs,Qs) :-
select(Q,UnplacedQs,UnplacedQs1),
\+ attack(Q,SafeQs),
queens(UnplacedQs1,[Q|SafeQs] ,Qs).
queens([ ],Qs,Qs).
attack(X,Xs) :-
attack(X,1,Xs).
attack(X,N,[Y|_]) :-
X is Y+N ; X is Y-N.
attack(X,N,[_|Ys]) :-
N1 is N+1,
attack(X,N1,Ys).
推荐答案
问题的第一部分中的代码是此处的解释.此处将代码重新发布，以确保读者不会错误地看错代码.
The code in the first part of the question is what is explained here. The code is reposted here to ensure a reader doesn't mistakenly look at the wrong code.
queens(N,Qs) :-
length(Qs,N),
place_queens(N,Qs,_,_).
place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
I > 0, I1 is I-1,
place_queens(I1,Qs,[_|Ups] ,Downs),
place_queen(I,Qs,Ups,Downs).
place_queen(Q,[Q|_],[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
place_queen(Q,Qs,Ups,Downs).
此代码与大多数Prolog解决N皇后问题的方法一样，是生成和测试的.该代码生成一个可能的解决方案并对其进行测试.但是，皇后位置不是一次生成一个可能答案的所有位置，而是逐步设置并在部分失败时更改，直到找到完整的解决方案.
This code as is most Prolog solutions to the N-Queens problem a generate and test. The code generates a possible solution and test it. However instead of generating all positions for one possible answer at once, the queen positions are set incrementally and changed upon a partial failure until a complete solution is found.
代码中有一项书面测试，
There is one written test in the code which is
place_queen(Q,[Q|_],[Q|_],[Q|_]).
To understand this requires understanding what the meaning of the arguments as related to this statement from here
现在想象一下，国际象棋棋盘分为三层，一层 分别处理对列的攻击和对角线分别在向上和向下的攻击.</p>
Now imagine that the chess-board is divided into three layers, one that deals with attacks on columns and two for the diagonals going up and down respectively.
第一个参数表示由正整数标识并绑定的皇后.
The first argument represents a queen identified by a positive integer and which is bound.
第二个参数表示一列，并且始终是板子尺寸的列表，其中列表中的每个部分代表板子的列之一. 代码使用变量Qs来表示，但对我来说，它更像Rs，意味着行.因此，如果列表中某个位置有任何绑定值，那么该列将成为皇后攻击.
The second argument represents a column and is always a list the size of the board where each potion in the list represents one of the columns of the board. The code uses the variable Qs for but to me it makes more sense as Rs, meaning rows. So if there is any bound value in a position in the list that would be a queen attacking in that column.
第三个和第四个参数的原理相同，并负责女王的对角线攻击.一种是对角线上升，另一种是对角线下降.由于它们再次是对角线，因此它们被表示为列表，但取决于在检查板上的皇后的魔力，对角线上升的大小可能与对角线下降的大小不同.
The third and fourth arguments work in principal in the same way and take care of the diagonal attack for the queen. One is for the diagonals going up and one the diagonals going down. Since they are diagonals again they are represented as list but depending upon the potion of a queen on the board that is being checked, the size of the diagonal going up may be different than the size of the diagonal going down.
例如，在下面的图像中，白色皇后代表被选中的皇后的位置，黑色皇后对角向上代表的是对角线列表，另一个皇后则代表向下对角线的列表.
For example in the image below the white queen represents the position of a queen being checked and the black queens going diagonally up represent the up going diagonal list and the other queen represents the down going diagonal list.
注意:使用棋盘图设置
对角线的长度为2，而对角线的长度为1.
The going up diagonal is length of two while the going down diagonal is length of one.
测试表明，如果可以将第一个参数中给出的女王/王后与列攻击自变量统一，则对角上升/下降对角线攻击然后接受该位置的女王/王后以得到部分答案或完整答案回答女王是否在第二个参数中列表的最后位置.
What the test states is that if a queen given in the first argument can be unified with the column attack argument, the going up diagonal attack and the going down diagonal attack then accept the queen in that position for a partial answer or complete answer if the queen is in the last position of the list in the second argument.
因此进行测试
place_queen(Q,[Q|_],[Q|_],[Q|_]).
与为清晰起见和文档而写的文字相同
which is the same as this written for clarity and documentation
place_queen(Q,Rs,Ups,Downs) :-
Rs = [R_1|_],
Ups = [U_1|_],
Downs = [D_1|_],
Q = R_1, Q = U_1, Q = D_1
然后，如果
Q为1
R_1未绑定
U_1未绑定
D_1未绑定
Q is 1
R_1 is unbound
U_1 is unbound
D_1 is unbound
测试过去和1绑定到变量R_1，U_1和D_1.
The test past and 1 is bound to the variables R_1, U_1, and D_1.
以及失败的测试示例
Q是3
R_1是1
U_1未绑定
D_1未绑定
Q is 3
R_1 is 1
U_1 is unbound
D_1 is unbound
现在是因为列表中没有值而导致测试失败的呼叫.
Now for a call that fails as a test because of no value in the list.
Q为2
R_1为[]
U_1未绑定
D_1未绑定
Q is 2
R_1 is []
U_1 is unbound
D_1 is unbound
其余代码仅会生成用于测试的案例.
The rest of the code just generates cases for testing.
可以看到第二个参数是通过运行此代码变体生成的.
The second argument can be seen being generated by running this variation of the code.
queens(N) :-
length(Qs,N),
format("N: ~w, Qs: ~w~n",[N,Qs]).
?- queens(4).
N: 4, Qs: [_6476,_6482,_6488,_6494]
true.
通过运行此代码变体可以看到对角参数.
The diagonal arguments can be seen being generated by running this variation of the code.
queens(N) :-
length(Qs,N),
place_queens(N,Qs,_,_).
place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
I > 0,
I1 is I-1,
place_queens(I1,Qs,[_|Ups] ,Downs),
format('I1: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I1,Qs,Ups,Downs]).
?- queens(4).
I1: 0, Qs: [_6474,_6480,_6486,_6492], Ups: [_6528,_6516,_6504|_6506], Downs: _6536
I1: 1, Qs: [_6474,_6480,_6486,_6492], Ups: [_6516,_6504|_6506], Downs: [_6534|_6536]
I1: 2, Qs: [_6474,_6480,_6486,_6492], Ups: [_6504|_6506], Downs: [_6522,_6534|_6536]
I1: 3, Qs: [_6474,_6480,_6486,_6492], Ups: _6506, Downs: [_6510,_6522,_6534|_6536]
true ;
false.
这小部分
place_queen(Q,[_|Rs],[_|Ups],[_|Downs] ):-
place_queen(Q,Rs,Ups,Downs).
只是说如果下一个女王的位置在该列中的某一行上不起作用，则选择另一行.请注意，上面的示例将第二个参数的变量名称从Qs更改为Rs，以表示它是要更改的行.
just says that if the position for the next queen did not work for a row in the column, then pick another row. Note that the example of above change the variable name of the second argument from Qs to Rs to say that it is row that is being changed.
要使生成和测试更容易看到，请修改代码
To make it easier to see the generate and test in action, modify the code as such
queens(N,Qs) :-
length(Qs,N),
place_queens(N,Qs,_,_).
place_queens(0,_Qs,_Ups,_Downs).
place_queens(I,Qs,Ups,[_|Downs]) :-
I > 0,
I1 is I-1,
place_queens(I1,Qs,[_|Ups] ,Downs),
format('Generate 1 - I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]),
place_queen(I,Qs,Ups,Downs),
format('Result -> I: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[I,Qs,Ups,Downs]).
place_queen(Q,Rs,Ups,Downs) :-
Rs = [R_1|_],
Ups = [U_1|_],
Downs = [D_1|_],
format('Test - Q : ~w, R_1: ~w, U_1: ~w, D_1: ~w~n',[Q,R_1,U_1,D_1]),
(
Rs = [Q|_],
Ups = [Q|_],
Downs = [Q|_]
->
format('Test success~n')
;
format('Test failure~n'),
fail
).
place_queen(Q,[_|Qs],[_|Ups],[_|Downs] ):-
format('Generate 2 - Q: ~w, Qs: ~w, Ups: ~w, Downs: ~w~n',[Q,Qs,Ups,Downs]),
place_queen(Q,Qs,Ups,Downs).
第一个解决方案的示例.
An example run up to the first solution.
?- queens(4,Qs).
Generate 1 - I: 1, Qs: [_6488,_6494,_6500,_6506], Ups: [_6542,_6530,_6518|_6520], Downs: _6550
Test - Q : 1, Q_1: _6488, U_1: _6542, D_1: _6596
Test success
Result -> I: 1, Qs: [1,_6494,_6500,_6506], Ups: [1,_6530,_6518|_6520], Downs: [1|_6598]
Generate 1 - I: 2, Qs: [1,_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: [_6548,1|_6598]
Test - Q : 2, Q_1: 1, U_1: _6530, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [_6494,_6500,_6506], Ups: [_6518|_6520], Downs: [1|_6598]
Test - Q : 2, Q_1: _6494, U_1: _6518, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: _6598
Test - Q : 2, Q_1: _6500, U_1: _6746, D_1: _6752
Test success
Result -> I: 2, Qs: [1,_6494,2,_6506], Ups: [_6530,_6518,2|_6748], Downs: [_6548,1,2|_6754]
Generate 1 - I: 3, Qs: [1,_6494,2,_6506], Ups: [_6518,2|_6748], Downs: [_6536,_6548,1,2|_6754]
Test - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,2,_6506], Ups: [2|_6748], Downs: [_6548,1,2|_6754]
Test - Q : 3, Q_1: _6494, U_1: 2, D_1: _6548
Test failure
Generate 2 - Q: 3, Qs: [2,_6506], Ups: _6748, Downs: [1,2|_6754]
Test - Q : 3, Q_1: 2, U_1: _6902, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [_6506], Ups: _6898, Downs: [2|_6754]
Test - Q : 3, Q_1: _6506, U_1: _6932, D_1: 2
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6928, Downs: _6754
Generate 2 - Q: 2, Qs: [_6506], Ups: _6742, Downs: _6748
Test - Q : 2, Q_1: _6506, U_1: _6782, D_1: _6788
Test success
Result -> I: 2, Qs: [1,_6494,_6500,2], Ups: [_6530,_6518,_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Generate 1 - I: 3, Qs: [1,_6494,_6500,2], Ups: [_6518,_6740,2|_6784], Downs: [_6536,_6548,1,_6746,2|_6790]
Test - Q : 3, Q_1: 1, U_1: _6518, D_1: _6536
Test failure
Generate 2 - Q: 3, Qs: [_6494,_6500,2], Ups: [_6740,2|_6784], Downs: [_6548,1,_6746,2|_6790]
Test - Q : 3, Q_1: _6494, U_1: _6740, D_1: _6548
Test success
Result -> I: 3, Qs: [1,3,_6500,2], Ups: [_6518,3,2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Generate 1 - I: 4, Qs: [1,3,_6500,2], Ups: [3,2|_6784], Downs: [_6524,_6536,3,1,_6746,2|_6790]
Test - Q : 4, Q_1: 1, U_1: 3, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [3,_6500,2], Ups: [2|_6784], Downs: [_6536,3,1,_6746,2|_6790]
Test - Q : 4, Q_1: 3, U_1: 2, D_1: _6536
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6784, Downs: [3,1,_6746,2|_6790]
Test - Q : 4, Q_1: _6500, U_1: _7070, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [2], Ups: _7066, Downs: [1,_6746,2|_6790]
Test - Q : 4, Q_1: 2, U_1: _7100, D_1: 1
Test failure
Generate 2 - Q: 4, Qs: [], Ups: _7096, Downs: [_6746,2|_6790]
Generate 2 - Q: 3, Qs: [_6500,2], Ups: [2|_6784], Downs: [1,_6746,2|_6790]
Test - Q : 3, Q_1: _6500, U_1: 2, D_1: 1
Test failure
Generate 2 - Q: 3, Qs: [2], Ups: _6784, Downs: [_6746,2|_6790]
Test - Q : 3, Q_1: 2, U_1: _6962, D_1: _6746
Test failure
Generate 2 - Q: 3, Qs: [], Ups: _6958, Downs: [2|_6790]
Generate 2 - Q: 2, Qs: [], Ups: _6778, Downs: _6784
Generate 2 - Q: 1, Qs: [_6494,_6500,_6506], Ups: [_6530,_6518|_6520], Downs: _6586
Test - Q : 1, Q_1: _6494, U_1: _6530, D_1: _6626
Test success
Result -> I: 1, Qs: [_6488,1,_6500,_6506], Ups: [_6542,1,_6518|_6520], Downs: [_6584,1|_6628]
Generate 1 - I: 2, Qs: [_6488,1,_6500,_6506], Ups: [1,_6518|_6520], Downs: [_6548,_6584,1|_6628]
Test - Q : 2, Q_1: _6488, U_1: 1, D_1: _6548
Test failure
Generate 2 - Q: 2, Qs: [1,_6500,_6506], Ups: [_6518|_6520], Downs: [_6584,1|_6628]
Test - Q : 2, Q_1: 1, U_1: _6518, D_1: _6584
Test failure
Generate 2 - Q: 2, Qs: [_6500,_6506], Ups: _6520, Downs: [1|_6628]
Test - Q : 2, Q_1: _6500, U_1: _6776, D_1: 1
Test failure
Generate 2 - Q: 2, Qs: [_6506], Ups: _6772, Downs: _6628
Test - Q : 2, Q_1: _6506, U_1: _6806, D_1: _6812
Test success
Result -> I: 2, Qs: [_6488,1,_6500,2], Ups: [1,_6518,_6770,2|_6808], Downs: [_6548,_6584,1,2|_6814]
Generate 1 - I: 3, Qs: [_6488,1,_6500,2], Ups: [_6518,_6770,2|_6808], Downs: [_6536,_6548,_6584,1,2|_6814]
Test - Q : 3, Q_1: _6488, U_1: _6518, D_1: _6536
Test success
Result -> I: 3, Qs: [3,1,_6500,2], Ups: [3,_6770,2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Generate 1 - I: 4, Qs: [3,1,_6500,2], Ups: [_6770,2|_6808], Downs: [_6524,3,_6548,_6584,1,2|_6814]
Test - Q : 4, Q_1: 3, U_1: _6770, D_1: _6524
Test failure
Generate 2 - Q: 4, Qs: [1,_6500,2], Ups: [2|_6808], Downs: [3,_6548,_6584,1,2|_6814]
Test - Q : 4, Q_1: 1, U_1: 2, D_1: 3
Test failure
Generate 2 - Q: 4, Qs: [_6500,2], Ups: _6808, Downs: [_6548,_6584,1,2|_6814]
Test - Q : 4, Q_1: _6500, U_1: _7070, D_1: _6548
Test success
Result -> I: 4, Qs: [3,1,4,2], Ups: [_6770,2,4|_7072], Downs: [_6524,3,4,_6584,1,2|_6814]
Qs = [3, 1, 4, 2] .
如果您发现此处难以阅读此输出，因为它的宽度很大，并且也很难将其作为顶级输出(swipl.exe)进行查看，那么请参阅如何使用
If you find it hard to read this output here because it is to wide and also hard to view as output to the top level (swipl.exe), then see how to use protocol/1 to capture the output to file for viewing and analysis.
这篇关于提示了解解决皇后区精彩计划的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
