N皇后问题和回溯算法

N-Queens问题是将n-Queens放置在n x n棋盘上的方式, 使得没有Queens可以通过在同一行, 同一列或对角线上相互攻击。

可以看出, 对于n = 1, 该问题具有微不足道的解决方案, 对于n = 2和n = 3, 不存在任何解决方案。因此, 首先我们将考虑4个皇后问题, 然后将其生成为n个皇后问题。

给定一个4 x 4的棋盘, 并为棋盘的行和列编号1至4。

既然如此, 我们必须在棋盘上放置q1 q2 q3和q4等4个皇后, 这样就不会有两个皇后互相攻击。在这种条件下, 每个皇后必须放置在不同的行上, 即我们将皇后“ i”放在“ i”行上。

现在, 我们将皇后q1放在第一个可接受的位置（1, 1）。接下来, 我们放置皇后q2, 以使这两个皇后不会互相攻击。我们发现, 如果将q2放在第1列和第2列中, 则会遇到死角。因此, 第3列中q2的第一个可接受位置, 即（2, 3）, 但没有剩余位置可安全放置女王’q3’。因此, 我们回退了一步, 并将（2, 4）中的女王’q2’放置在下一个最佳解决方案中。然后我们获得放置“ q3”的位置, 即（3, 2）。但是后来这个位置也会导致死胡同, 并且找不到可以安全放置“ q4”的地方。然后我们必须回溯到’q1’并将其放置到（1, 2）, 然后通过将q2移到（2, 4）, q3移到（3, 1）和q4移到（4, 3）来安全放置所有其他皇后区）。也就是说, 我们得到了解（2, 4, 1, 3）。这是4皇后问题的一种可能解决方案。对于另一个可能的解决方案, 对所有部分解决方案重复整个方法。解决4-Queens问题的其他解决方案是（3, 1, 4, 4, 2）, 即

解决方案（2、4、1、3）的4-Queen问题的隐式树如下：

图显示了4-Queens问题的完整状态空间。但是我们可以使用回溯方法来生成必要的节点, 并在下一个节点违反规则时（即, 两个皇后在进攻时）停止。

4-Queens解决方案空间, 其节点在DFS中编号

可以看出, 所有4个皇后问题的解都可以表示为4个元组（x1, x2, x3, x4）, 其中xi表示放置“皇后”“ qi”的列。

图中显示了8个皇后问题的一种可能解决方案：

Thus, the solution for 8 -queen problem for (4, 6, 8, 2, 7, 1, 3, 5).
If two queens are placed at position (i, j) and (k, l).
Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.
The first equation implies that j - l = i - k.
The second equation implies that j - l = k - i.
Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|

如果可以将第k个皇后放在第i列中, 则Place（k, i）返回一个布尔值, 该值为true。它既测试i是否与之前的所有成本x1, x2, … xk-1不同, 又在同一对角线上是否没有其他皇后。

通过使用位置, 我们为n-皇后问题提供了精确的解决方案。

Place (k, i)
   {
     For j  ←  1 to k - 1
      do if (x [j] = i)
       or (Abs x [j]) - i) = (Abs (j - k))
    then return false;
     return true;
}

如果可以在第k行和第ith列中放置一个女王, 则place（k, i）返回true, 否则return为false。

x []是已设置最终k-1个值的全局数组。 Abs（r）返回r的绝对值。

N - Queens (k, n)
{
   For i  ←  1 to n
        do if Place (k, i) then
   {
      x [k]  ←  i;
      if (k ==n) then
        write (x [1....n));
      else
      N - Queens (k + 1, n);
   }
}

猜你喜欢