prolog - 提示了解解决皇后区的精彩程序

Question

在 序言的艺术 Sterling & Shapiro，行使第 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 行代码，快速解决了棋盘上皇后的定位问题。这很神奇:只有计数器、递归和越来越短的列表。我，即使在trace的帮助下，也不明白。有人可以向我解释吗？你如何编写这样的程序？例如，从其他(良好的标准解决方案)派生该程序的逻辑/心理过程是什么:

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).

Answer 1

由于先前的良好答案而理解了该程序，我尝试给出更具说明性的解释。
该程序的作者是 Thom Frühwirth(感谢 Jschimpf 提供的信息)。
我引用了他的 message 的摘录发布在 comp.lang.prolog 上:

Observing that no two queens can be positioned on the same row, column or diagonals, we place only one queen on each row. Hence we can identify the queen by its row-number. 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. We indicate that a field is attacked by a queen by putting the number of the queen there. Now we solve the problem by looking at one row at a time, placing one queen on the column and the two diagonal-layers. For the next row/queen we use the same column layer, to get the new up-diagonals we have to move the layer one field up, for the down-diagonals we move the layer one field down.

他的节目:

% -------- Meaning of Variables ------
% N, M  ... Size of the board
% I, J  ... Number of the row current queen is on
% Qs, L ... List of length N used to represent the solution
% Cs ... Column as a list of fields of length N
% Us ... Up-Diagonal as an open list of fields
% Ds ... Down-Diagonal as an open list of fields


queens(N,Qs):- gen_list(N,Qs), place_queens(N,Qs,_,_).

gen_list(0,[]).
gen_list(N,[_|L]):-
        N>0, M is N-1,
        gen_list(M,L).

place_queens(0,_,_,_).
place_queens(I,Cs,Us,[_|Ds]):-
        I>0, J is I-1,
        place_queens(J,Cs,[_|Us],Ds),
        place_queen(I,Cs,Us,Ds).

% place_queen(Queen,Column,Updiagonal,Downdiagonal) places a single queen
place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
                place_queen(I,Cs,Us,Ds).

让我们回到这个问题。
让我们让问题变得更容易。让我们只考虑行、列和上对角线。

queens(N,Qs) :-
    length(Qs,N),
    place_queens(N,Qs,_).

place_queens(0,_,_).    
place_queens(I,Qs,Ups) :-
    I > 0,
    I1 is I-1,
    place_queens(I1,Qs,[_|Ups]),
    place_queen(I,Qs,Ups).

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

?- queens(3,L).
L = [1, 2, 3];        
L = [3, 1, 2];       % row 3/col 1 -- row 1/col 2 -- row 2/col 3
L = [2, 3, 1];
false

带有上对角线的第 3 面棋盘:

    C1  C2  C3
    |   |   |     Row
  +---+---+---+
U1| / | / | / |-- 1
  +---+---+---+
U2| / | / | / |-- 2
  +---+---+---+
U3| / | / | / |-- 3
  +---+---+---+
   U3  U4  U5

以及与行/皇后、列/皇后列表和上对角线/皇后列表相关的谓词:

row_col_ups(1, [ 1,C2,C3], [ 1,U2,U3,U4,U5]). % row 1
row_col_ups(1, [C1, 1,C3], [U1, 1,U3,U4,U5]).
row_col_ups(1, [C1,C2, 1], [U1,U2, 1,U4,U5]).

row_col_ups(2, [ 2,C2,C3], [U1, 2,U3,U4,U5]). % row 2
row_col_ups(2, [C1, 2,C3], [U1,U2, 2,U4,U5]).
row_col_ups(2, [C1,C2, 2], [U1,U2,U3, 2,U5]).

row_col_ups(3, [ 3,C2,C3], [U1,U2, 3,U4,U5]). % row 3
row_col_ups(3, [C1, 3,C3], [U1,U2,U3, 3,U5]).
row_col_ups(3, [C1,C2, 3], [U1,U2,U3,U4, 3]).

考虑 place_queen/3 谓词:

% place_queen(Q,Cols,Ups)
% Q    -> queen/row
% Cols -> list of colunms/queens
% Ups  -> open list of up-diagonals/queens

place_queen(Q,[Q|_],[Q|_]).
place_queen(Q,[_|Qs],[_|Ups]):-
    place_queen(Q,Qs,Ups).

它的结构与 相同。成员(member)/2 :

member(X,[X|_]).
member(X,[_|L]):-
    member(X,L).

?- member(3,[1,2,3]).
true.
?- member(X,[1,2]).
X = 1;
X = 2.

但它以一种不寻常的方式使用:

?- L=[1,2,X,4], member(3,L).
L = [1, 2, 3, 4],
X = 3

?- member(3,L).
L = [3|_1388];
L = [_1178, 3|_1186];
L = [_1178, _1184, 3|_1192];

所以， place_queen 寻找一个空方格，如果有的话，把皇后放在哪里。

?- Col=[C1,C2,C3], place_queen(3,Col,UPS).
Col = [3, C2, C3],
UPS = [3|_]

?- Col=[C1,C2,C3], place_queen(1,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2).
Col = [3, C2, 2],
UPS = [3, 2|_],
UPS2 = [U2, 3, 2|_]

?- Col=[C1,C2,C3], place_queen(3,Col,UPS), UPS2=[U2|UPS], place_queen(2,Col,UPS2), UPS3=[U1|UPS2], place_queen(1,Col,UPS3).
Col = [3, 1, 2],
UPS = [3, 2|_],
UPS2 = [1, 3, 2|_],
UPS3 = [U1, 1, 3, 2|_]

对角线(上和下)由 open-list 表示，即如果需要，可以在队列中添加元素的列表。 place_queens 处理它们以及行和对角线之间的关系。

place_queens(0,_Qs,_Ups,_Downs). % usually pred(0,[],[],[]) for closed list
                                 % but with open-lists we have the variables.

place_queens(I,Qs,Ups,[_|Downs]) :-
    I > 0, I1 is I-1,
    place_queens(I1,Qs,[_|Ups] ,Downs), %  in next row/queen 
    place_queen(I,Qs,Ups,Downs).        %  for the up-diagonals we move the layer
                                        %  one field up.
                                        %  for the down-diagonals we move the layer
                                        %  one field down.

附言与第 3 面棋盘中的行/皇后、列/皇后列表和下对角线/皇后列表相关的谓词:

row_col_downs(1, [ 1,C2,C3], [D1,D2, 1,D4,D5]).
row_col_downs(1, [C1, 1,C3], [D1,D2,D3, 1,D5]).
row_col_downs(1, [C1,C2, 1], [D1,D2,D3,D4, 1]).

row_col_downs(2, [ 2,C2,C3], [D1, 2,D3,D4,D5]).
row_col_downs(2, [C1, 2,C3], [D1,D2, 2,D4,D5]).
row_col_downs(2, [C1,C2, 3], [D1,D2,D3, 2,D5]).

row_col_downs(3, [ 3,C2,C3], [ 3,D2,D3,D4,D5]).
row_col_downs(3, [C1, 3,C3], [D1, 3,D3,D4,D5]).
row_col_downs(3, [C1,C2, 3], [D1,D2, 3,D4,D5]).

P.P.S.Thom Frühwirth 给出了该程序的另外两个版本，其中一个是纯 Prolog:

% Pure version with successor function

queensp(N,Qs):- gen_listp(N,Qs), place_queensp(N,Qs,_,_).

gen_listp(0,[]).
gen_listp(s(N),[_|L]):-
        gen_listp(N,L).

place_queensp(0,_,_,_).
place_queensp(s(I),Cs,Us,[_|Ds]):-
        place_queensp(I,Cs,[_|Us],Ds),
        place_queen(s(I),Cs,Us,Ds).

place_queen(I,[I|_],[I|_],[I|_]).
place_queen(I,[_|Cs],[_|Us],[_|Ds]):-
        place_queen(I,Cs,Us,Ds).

?- queensp(Q,L).
L = [],
Q = 0 ;
L = [s(0)],
Q = s(0) ;
L = [s(s(s(0))), s(0), s(s(s(s(0)))), s(s(0))],
Q = s(s(s(s(0))))