2

我已经尝试通过回溯解决这个问题，它会打印所有可能的解决方案。

提出了两个问题：

1.我可以使用其他技术实现 nqueen 吗？

2.是否可以让下面的代码只打印第一个解决方案然后终止？

我当前的代码使用回溯：

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
        if k == n-1:
            print "SOLUTION", x
        else:
            nqueen(k+1)

nqueen(0)

注意：我对不依赖于特定编程语言的技术感兴趣。

4

2 回答 2

3

根据Wikipedia，您可以使用启发式方法：

这种启发式求解任意 N ≥ 4 的 N 个皇后。它形成了皇后的垂直位置（行）的数字列表，水平位置（列）只是增加。N 是 8 八皇后拼图。

  1. 如果将 N 除以 6 的余数不是 2 或 3，那么列表就是所有偶数，后跟所有奇数 ≤ N
  2. 否则，编写单独的偶数和奇数列表（即 2,4,6,8 - 1,3,5,7）
  3. 如果余数为 2，则将奇数列表中的 1 和 3 交换，并将 5 移到末尾（即 3,1,7,5）
  4. 如果余数为 3，则将 2 移动到偶数列表的末尾，将 1,3 移动到奇数列表的末尾（即 4,6,8,2 - 5,7,9,1,3）
  5. 将奇数列表附加到偶数列表中，并将皇后放在这些数字给出的行中，从左到右（即 a2、b4、c6、d8、e3、f1、g7、h5）

这种启发式是O(n)因为它只是在一些if语句之后打印结果。

关于您的第二个问题：“是否可以使下面的代码仅打印第一个解决方案然后终止？”

您可以sys.exit(0)在打印后调用：

import sys
n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                sys.exit(0)
            else:
                nqueen(k+1)

nqueen(0)

或者，您也可以返回一个值，然后在它指示终止时传播该值：

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                return True # Found a solution, send this good news!
            else:
                if nqueen(k+1): # Good news!
                    return True # Share the good news to parent!
    return False # We have searched every possible combinations, and I regret to tell you that I could not find any solution.

nqueen(0)

至于时间复杂度，因为是全搜索，所以是n^n. 虽然由于修剪（使用safe(k,i)），但实际上它要快得多。

于 2013-09-04T09:47:29.967 回答
2

在不回溯的情况下求解 N-queens 的问题还有另一个有趣的问题。是否存在几乎完美的女王放置启发式方法，使得在回溯框架中，您几乎总能找到有效的配置？这相当于说启发式几乎总是告诉你正确的方格来放置下一个皇后在棋盘上。这种启发式比已知的封闭形式解决方案更有趣，它为所有 N 值提供有效配置（显然 N=2 和 3 除外）。

几乎完美的最小回溯启发式分析是文献中研究的一个问题。最重要的参考文献是[Kalé 90]和[San Segundo 2011]。将下一个皇后放置在回溯框架中的最佳启发式方法似乎如下：

  1. 选择最受限制的行来放置下一个皇后（即可用方格较少的行）
  2. 从 (1) 中的行中选择闭合对角线数量最少的正方形（最小限制策略）。

这里关闭对角线是指取消其所有可用的正方形。

于 2014-07-23T20:11:05.087 回答