N个皇后算法 [英] Algorithm of N queens

问题描述

Algorithm NQueens ( k, n) //Prints all Solution to the n-queens problem
{
    for i := 1 to n do
    {
        if Place (k, i) then
        {
            x[k] := i;
            if ( k = n) then write ( x [1 : n]
            else NQueens ( k+1, n);
        }
    }
}

Algorithm Place (k, i)
{
    for j := 1 to k-1 do
        if (( x[ j ] = // in the same column
           or (Abs( x [ j ] - i) =Abs ( j – k ))) // or in the same diagonal
        then return false;
        return true;
}

上面的代码是通过回溯来解决N个皇后问题的，我认为它可以将两行的前2个皇后放在相应的列中，然后当涉及第3行皇后时就不能放置，因为没有皇后的需要被攻击，它将仅从算法N个皇后区退出...那么，该算法如何实现回溯?

The above code is for solving N Queens problem using backtracking.I think that it can place the first 2 queens of two rows in respective columns and then when it comes to 3rd row queen it can't be placed as no queen needs to be attacking and it will simply exit from Algorithm N queens...So how is this algorithm implements backtracking?

推荐答案

这里的秘密就是递归.

让每个缩进级别都表示递归级别.

Let each level of indentation below indicate a level of recursion.

(实际上不会发生什么，因为可以很容易地放置第三个皇后，但是要花更多的篇幅和/或思考才能得出实际上失败的案例)

(not what will actually happen, as the third queen can easily be placed, but it just would've taken quite a bit more writing and/or thinking to get to a case that will actually fail)

try to place first queen
success
   try to place second queen
   success
      try to place third queen
      fail
   try to place second queen in another position
   success
      try to place third queen
      success
         try to place fourth queen

更符合代码实际功能的东西:(仍然不是实际发生的事情)

Something more in line with what the code actually does: (still not what will actually happen)

first queen
i = 1
Can place? Yes. Cool, recurse.
   second queen
   i = 1
   Can place? No.
   i = 2
   Can place? No.
   i = 3
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      i = 2
      Can place? No.
      ... (can be placed at no position)
      fail
      back to second queen
   i = 4
   Can place? Yes. Cool, recurse.
      third queen
      i = 1
      Can place? No.
      ...

我希望能帮上忙.

这篇关于N个皇后算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！