{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.manongdao.com/data/attach/logo/logo.png', '推荐 Ridiculous、 的问题《Hints to understand splendid program to solve Quee》','https://www.manongdao.com/q-1245730.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
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).
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).
As an intermediate step to understanding the original program, you might consider the following, which is based on the same underlying idea. There is a variable for
These variables get instantiated with the column number of the queen that occupies the corresponding location on the board (because each queen covers a column, a row, an up-diagonal and a down-diagonal).
Instead of the clever list manipulation in the orginal program, this one uses "arrays" for the rows and diagonals, and is probably easier to understand:
Let us first look at the top predicate. Here we solve the N×N queens problem by calling
queens(N,Qs). The first call in the bodylength(Qs, N)constructs a list of variables with lengthN. Next it callsplace_queens/4withplace_queens(N, Qs, _, _). It thus passes two free variables to theplace_queens/4. Later we will, by unfication, construct a list.The
place_queens/4first is called recursively until we hit zero forI, if we for example "unfold" the program forN = 4, we get:(the above is not a Prolog code, it is an illustration to show the call structure.)
The
place_queensthus does two things:[U1, U2, U3, U4|_]and downs[D1, D2, D3, D4|_]; andplace_queenwith a specific value, and certain parts of the ups and downs list.The task of the
place_queenis to fill in the columnIsomewhere in the list. It always gets the entire list of queen positions[Q1, Q2, Q3, Q4]and parts of the ups and downs list. These ups and downs represent diagonals moving in the up and down direction.In case we fill in a value for a given queen position, we also mark that value for the given ups and downs list, and thus "claim" these diagonals for that queen. If we do the bookkeeping properly that is sufficient, since if another queen wants to take a place that is on a diagonal that is already claimed, it aims to attach that value to the corresponding diagonal, but it will fail, since its value differs from the already assigned value.
Let us demonstrate that with an example. When we call the first
place_queen(1, [Q1, Q2, Q3, Q4], [U2, U3, U4|_], _), we can assign that tho the first position, this is the basecase, so this results in the fact that:so that means that now our
[Q1, Q2, Q3, Q4]looks like[1, Q2, Q3, Q4], for the up diagonals it looks like[U1, U2, U3, U4|_] = [U1, 1, U3, U4|_]and for[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1|_].Now we aim to assign the next
place_queen(2, [1,Q2,Q3,Q4],[U3,U4|_], [D4, 1|_]). We know we can not assign that value to the first item of theQlist, since that value is occupied by1, and thus that would mean that two queens have the same column and attack each other, so that will not work.We thus perform recursion, and hereby we pop both the up and down list, so:
So now we aim to put the queen for row two on the second column of the board, but there is again a problem: the diagonal of that square is already claimed, again by queen
1, we can derive that form the fact that down has[1|_]. So again we have to perform recursion, like:Here we can safely place the queen, here, none of the lists are blocking. So when we do that, the lists now look like
[Q1, Q2, Q3, Q4] = [1, Q2, 2, Q4],[U1, U2, U3, U4|_] = [U1, 1, U3, U4, 2|_]and[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, 2|_]. If we look at the board we have assigned, the diagonals indeed make sense:So as we can see the first queen claims
D5andU2, and the second queen claimsD6andU5.Now we can place the third queen on the board, or at least we can try to do that, we thus make a call with
place_queen(3,[1,Q2,2,Q4],[U4,2|_],[D3,D4,1,2|_]).Here we will fail to place it at the first column (since it is occupied by queen
1), fail to put it on the second column (the up diagonal is claimed by queen2), the third column (the column is occupied by queen2and the down diagonal is claimed by queen1), and the last column (the down diagonal is claimed by queen2). Eventually we run out of theQlist, so we will have to backtrack over the previous queen's assignment.So now we continue with placing the second queen, the only option left, is to place it at the last column:
In that case the
[Q1, Q2, Q3, Q4] = [1, Q2, Q3, 2],[U1, U2, U3, U4|_] = [U1, 1, U3, U4, U5, 2|_]and[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, D6, 2|_]. So now the question is where to put the next queen (queen3):we can again assign the third queen, and we thus call the predicate now with
place_queen(3,[1,Q2,Q3,2],[U4,U5,2|_],[D3,D4,1,D6,2|_]). We can not assign that queen to the first location, since queen1occupies that column, we thus recursively call it withplace_queen(3,[Q2,Q3,2],[U5,2|_],[D4,1,D6,2|_]). Here there is no problem to put the queen, since the head of all three the lists is a free variable. We thus setQ2 = U5 = D4 = 3, and thus obtain the following board:So now our lists look like
[Q1, Q2, Q3, Q4] = [1, 3, Q3, 2],[U1, U2, U3, U4|_] = [U1, 1, U3, U4, 3, 2|_]and[D1, D2, D3, D4|_] = [D1, D2, D3, 3, 1, D6, 2|_]. Now we can eventually assign the last queen to the board, we thus call theplace_queen/4withplace_queen(4,[1,3,Q3,2],[3,2|_],[D2,D3,3,1,D6,2|DT]).. The first two places are rejected (occupied both by column and by up diagonal), so after two recursive calls, we end up withplace_queen(4,[Q3,2],_,[3,1,D6,2|DT]), but that one is occupied by queen3(down diagonal), indeed, the situation looks like this:So again we found that this does not yield a sulution. Prolog will keep backtracking, and eventually will come up with the solution:
Then the lists look like
Qs = [3, 1, 4, 2],U = [1, 3, _, 2, 4|_]andD = [_, _, 3, 4_, 1, 2|_].So we can conclude that the values in the up and downlist are not relevant on itself, it is used to prevent to assign a different number (queen) on these diagonals.
Whitespace can help increase readability of a program greatly. Variables naming is also very important in that regard:
The illustration from Willem's answer, again tweaked for whitespace:
Thus the recursion builds
NnestedN-long loops which theplace_queencalls in effect are, working on the same lists with starting positions shifted in a certain scheme.It will also make it so that
UT = [U5,U6,U7,U8|_](because ofplace_queen(4)) andDT = [D5,D6,D7,D8|_](because ofplace_queen(1)), so the four loops will be equivalent toIndeed it produces the same results as
queens(4, QS).And we can kind of see the diagonals there.... Right? When a first queen is put at, say,
Q3, it becomes1=Q3=U4=D7,Having understood the program thanks to previous good answers, I try to give a more declarative explanation.
The author of the program is Thom Frühwirth (thanks to Jschimpf for the information).
I quote an extract from his message posted on comp.lang.prolog:
His program:
Let's go back to the question. Let's make the problem easier. Let's just consider the rows, the columns and the up-diagonals.
Chessboard of side 3 with up-diagonals:
and the predicate that relates rows/queens, lists of columns/queens and lists of up-diagonals/queens:
Consider the place_queen/3 predicate:
It has the same structure as member/2:
But it is used in an unusual way:
So, place_queen looks for an empty square, if it exists, where to put the Queen.
The diagonals (up and down) are represented by open-list, that is, lists to which elements can be added, if necessary, in the queue. place_queens handles them and the relationship between rows and diagonals.
P.S. Predicate that relates rows/queens, lists of columns/queens and lists of down-diagonals/queens in chessboard of side 3:
P.P.S.Thom Frühwirth gives two other versions of the program, one of which is in pure Prolog:
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.
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
To understand this requires understanding what the meaning of the arguments as related to this statement from here
The first argument represents a queen identified by a positive integer and which is bound.
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.
Note: Images generated using Chess Diagram Setup
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.
So for the test
which is the same as this written for clarity and documentation
then if
Q is 1
R_1 is unbound
U_1 is unbound
D_1 is unbound
The test past and 1 is bound to the variables R_1, U_1, and D_1.
and an example of a test that fails
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 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.
The diagonal arguments can be seen being generated by running this variation of the code.
This small part
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
QstoRsto 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
An example run up to the first solution.
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.