N皇后的算法

Question

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 Queens 问题的进行攻击，它会简单地退出算法 N 皇后......那么这个算法是如何实现回溯的？

Answer 1

这里的 secret 是递归。

让下面的每个缩进级别表示递归级别。

(不是实际会发生什么，因为可以很容易地放置第三个女王，但要找到一个实际失败的案例需要更多的写作和/或思考)

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

一些更符合代码实际所做的事情:(仍然不是实际会发生的事情)

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

希望对您有所帮助。