N个皇后算法

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

最佳答案

这里的 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.
      ...

希望对您有所帮助。