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皇后问题.我认为它可以将两行的前两个皇后放在相应的列中,然后当它涉及到第三行皇后时,它不能被放置,因为没有女王需要攻击它将简单地从算法N皇后退出......那么这个算法如何实现回溯？

Answer 1

这里的秘密是递归.

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

(不会发生什么事情,因为第三个女王可以很容易地被放置,但它会花费更多的写作和/或思考来找到一个实际上会失败的案例)

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

我希望有所帮助.