提示了解解决皇后区精彩计划的方法

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行，可快速解决将皇后放在棋盘上的问题。这很神奇：只有计数器，递归和列表变得越来越长。我，即使在跟踪的帮助下，也不了解它。有人可以向我解释吗？您如何编写这样的程序？导致从（例如，另一个）（好的标准解决方案）派生该程序的逻辑/心理过程是什么？

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

让我们首先看一下顶部谓词。这里我们通过调用 来解决N×Nqueens(N,Qs)皇后问题。正文中的第一个调用length(Qs, N)构造了一个包含 length 的变量列表N。接下来它place_queens/4调用place_queens(N, Qs, _, _). 因此，它将两个自由变量传递给place_queens/4. 稍后我们将通过统一构建一个列表。

第place_queens/4一个被递归调用，直到我们达到零I，例如，如果我们“展开”程序N = 4，我们得到：

place_queens(4, [Q1,Q2,Q3,Q4], UT, [D1,D2,D3,D4|DT]) :-
    place_queens(3, [Q1,Q2,Q3,Q4], [U4|UT], [D2,D3,D4|DT]) :-
        place_queens(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D3,D4|DT]) :-
            place_queens(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], [D4|DT]) :-
                place_queens(0, [Q1,Q2,Q3,Q4], [U1,U2,U3,U4|UT], DT),
                %% ---
                place_queen(1, [Q1,Q2,Q3,Q4], [U2,U3,U4|UT], DT),
            place_queen(2, [Q1,Q2,Q3,Q4], [U3,U4|UT], [D4|DT]),
        place_queen(3, [Q1,Q2,Q3,Q4], [U4|UT], [D3,D4|DT]),
    place_queen(4, [Q1,Q2,Q3,Q4], UT, [D2,D3,D4|DT]).

（上面不是Prolog代码，只是一个调用结构的示意图。）

因此，它place_queens做了两件事：

1. 它“展开”了一系列的起起落落 ；和[U1, U2, U3, U4|_] [D1, D2, D3, D4|_]
2. 它调用place_queen特定值以及涨跌列表的某些部分。

的任务place_queen是填写I列表中某处的列。它总是获取皇后位置的完整列表[Q1, Q2, Q3, Q4]以及涨跌列表的部分内容。这些起伏代表向上和向下移动的对角线。

如果我们为给定的皇后位置填写一个值，我们还会为给定的涨跌列表标记该值，从而为该皇后“声明”这些对角线。如果我们正确地记账就足够了，因为如果另一个皇后想要占据已经声明的对角线上的位置，它的目标是将该值附加到相应的对角线上，但它会失败，因为它的值不同于已经分配的值。

让我们用一个例子来证明这一点。当我们调用第一个时place_queen(1, [Q1, Q2, Q3, Q4], [U2, U3, U4|_], _)，我们可以将其分配给第一个位置，这是基本情况，因此这会导致以下事实：

place_queen(1,[Q1,Q2,Q3,Q4],[U2,U3,U4|_], _D) :-
    Q1 = 1,
    U2 = 1,
    _D = [1|_].

所以这意味着现在我们的[Q1, Q2, Q3, Q4]看起来像[1, Q2, Q3, Q4], 向上对角线看起来像[U1, U2, U3, U4|_] = [U1, 1, U3, U4|_]和[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1|_]。

现在我们的目标是分配下一个place_queen(2, [1,Q2,Q3,Q4],[U3,U4|_], [D4, 1|_])。我们知道我们不能将该值分配给列表的第一项Q，因为该值被 占据1，因此这意味着两个皇后具有相同的列并互相攻击，因此这是行不通的。

因此，我们执行递归，从而弹出向上列表和向下列表，因此：

place_queen(2, [1,Q2,Q3,Q4], [U3,U4|UT], [D4, 1|DT]) :-
    place_queen(2, [Q2,Q3,Q4], [U4|UT], [1|DT]).

所以现在我们的目标是将第二行的皇后放在棋盘的第二列上，但又出现了一个问题：该正方形的对角线已经被皇后声明了1，我们可以从向下有 的事实中得出这一点[1|_]。所以我们必须再次执行递归，例如：

place_queen(2, [1,Q2,Q3,Q4], [U4|UT], [1|DT]) :-
    place_queen(2, [Q3,Q4], UT, DT).

在这里我们可以安全地放置皇后，这里没有任何列表被阻塞。因此，当我们这样做时，列表现在看起来像[Q1, Q2, Q3, Q4] = [1, Q2, 2, Q4]、[U1, U2, U3, U4|_] = [U1, 1, U3, U4, 2|_]和[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, 2|_]。如果我们看看我们分配的棋盘，对角线确实有意义：

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   | Q |   |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

所以我们可以看到第一个皇后声称D5和U2，第二个皇后声称D6和U5。

现在我们可以将第三个皇后放在棋盘上，或者至少我们可以尝试这样做，因此我们用 进行跟注place_queen(3,[1,Q2,2,Q4],[U4,2|_],[D3,D4,1,2|_])。

在这里，我们将无法将其放置在第一列（因为它被 queen 占据1），无法将其放置在第二列（上对角线被 queen 占据2）、第三列（该列被 queen 占据2，并且下对角线由 queen 声明1），最后一列（下对角线由 queen 声明2）。最终我们用完了Q列表，所以我们将不得不回溯上一个女王的分配。

所以现在我们继续放置第二个皇后，剩下的唯一选择就是将其放置在最后一列：

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   |   |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

在这种情况下[Q1, Q2, Q3, Q4] = [1, Q2, Q3, 2]， ,[U1, U2, U3, U4|_] = [U1, 1, U3, U4, U5, 2|_]和[D1, D2, D3, D4|_] = [D1, D2, D3, D4, 1, D6, 2|_]. 所以现在的问题是把下一个皇后（queen 3）放在哪里：

我们可以再次分配第三个皇后，因此我们将谓词 now 称为place_queen(3,[1,Q2,Q3,2],[U4,U5,2|_],[D3,D4,1,D6,2|_])。我们不能将该皇后分配给第一个位置，因为皇后1占据该列，因此我们用 递归地调用它place_queen(3,[Q2,Q3,2],[U5,2|_],[D4,1,D6,2|_])。在这里放置皇后是没有问题的，因为所有三个列表的头部都是一个自由变量。我们由此设置Q2 = U5 = D4 = 3，从而得到如下棋盘：

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   |   |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

现在我们的列表看起来像[Q1, Q2, Q3, Q4] = [1, 3, Q3, 2],[U1, U2, U3, U4|_] = [U1, 1, U3, U4, 3, 2|_]和[D1, D2, D3, D4|_] = [D1, D2, D3, 3, 1, D6, 2|_]。现在我们最终可以将最后一个皇后分配给棋盘，因此我们将其称为place_queen/4with place_queen(4,[1,3,Q3,2],[3,2|_],[D2,D3,3,1,D6,2|DT]).。前两个位置被拒绝（同时被列和上对角线占据），所以在两次递归调用之后，我们最终得到place_queen(4,[Q3,2],_,[3,1,D6,2|DT])，但是那个位置被皇后3（下对角线）占据，事实上，情况如下所示：

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /| Q |   |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /|   | Q |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

所以我们再次发现这并不能产生解决方案。Prolog会不断回溯，最终会得出解决方案：

 \D5 \D6 \D7 \ D8\
  +---+---+---+---+
 /|   | Q |   |   |
U2+---+---+---+---+
 /|   |   |   | Q |
U3+---+---+---+---+
 /| Q |   |   |   |
U4+---+---+---+---+
 /|   |   | Q |   |
  +---+---+---+---+
  U5 /U6 /U7 / U8/

然后列表看起来像Qs = [3, 1, 4, 2],U = [1, 3, _, 2, 4|_]和D = [_, _, 3, 4_, 1, 2|_]。

所以我们可以得出结论，上列表和下列表中的值本身不相关，它用于防止在这些对角线上分配不同的数字（皇后）。