python - 为什么偶数 Ns 比奇数 Ns 花费更长的时间？

Question

我在这里有一些代码可以使用 python 中的回溯解决 n 个皇后问题。当我运行它时，赔率总是比偶数花费的时间少得多。当 n 达到 20+ 左右时，这一点尤其明显。有人知道为什么是这样吗？

import time
global N
N = int(input("Enter N: "))


def display_solution(board):
    print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in 
    board]))


def safe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True


def solve_help(board, col):
    if col >= N:
        return True

    for i in range(N):
        if safe(board, i, col):
            board[i][col] = 1
            if solve_help(board, col + 1) is True:
                return True
            board[i][col] = 0
    return False


def solve():
    board = [[0 for x in range(N)] for y in range(N)]
    if solve_help(board, 0) is False:
        print("Solution does not exist")
        return False
    display_solution(board)
    return True


start = time.clock()
solve()
end = time.clock()
print(N, "\t", end-start)

我假设它一定与对角线的赔率不同而不是偶数有关。我也不确定这是否是针对此问题的所有回溯算法的问题，还是只是此特定代码的问题。不管怎样，谢谢你的帮助。

Answer 1

当在前一列中发生回溯并且必须尝试下一行时，该算法需要相当多的时间。比较奇数 N 板和 N-1 板确实表明，偶数板的解决方案通常需要做更多这样的回溯/尝试下一个处理。例如，N=19 解的左上角如下所示:

1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1*
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

前五列中的这 5 个皇后很快就会被找到，因为它们是第一个不与之前的皇后发生冲突的皇后。显然，无需重新考虑前五个皇后就可以放置其他皇后。
对于 N=18，解决方案的同一角如下所示:

1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0-
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1*

请注意标有减号的位置。这个看起来很有希望(就像 19 板一样):它的调查需要相当长的时间才能得出其他 Q 不能正确放置的结论。这种早期失败的成本。
因此，比 18 板更快地找到 19 板的解决方案。
请注意，27 的解决方案比 26 的解决方案花费的时间略多，尽管这并不重要:看起来时间复杂度是 O(2n)，因此要比较不同电路板尺寸的时间，最好在对数 Y 轴:

“work”表示函数 safe的次数被执行。
这个算法对于偶数板是否总是花费相对更多的时间(与 N+1 板所需的时间相比)尚不清楚，但对于这几个板尺寸，它似乎与该算法自然形成的骑士跳跃有关，开始从左上角。请注意这种模式如何完美地适用于尺寸为 5 和 7 的棋盘:下一个皇后可以坐的第一个位置而不干扰先前定位的皇后始终是解决方案的一部分。而对于 4 号和 6 号棋盘，在角落里甚至没有任何解决方案，这是该算法的起点。
备择方案
从程序员的角度来看这个问题，有一种补救措施可以使差异(平均而言)消失:以不同(甚至随机)的顺序选择列。事实证明，采用正常顺序是获得解决方案效率较低的方法之一。
换档选择
这个算法的一个简单转变，除非所有其他都失败，否则你不考虑前两行，已经大大改变了统计数据:
在 solve_help改变这个:

for i in range(N):

到:

for i in range(N):
   i = (i + 2) % N

看看现在平均性能是如何改进的:除 n=6 外，所有 log(work)/n 的测量值都低于 1。而且:现在更频繁地查看 N 的奇数值。
随机挑选

for i in random.sample(range(N), N):

这是一次这样的随机运行的结果:

比原始订单更好的统计数据!当然，你会时不时地得到一个糟糕的统计数据，......因为它是随机的。但平均而言，它的表现(好得多)。
其他非随机顺序的方式可能包括 col , 和 N//2具有不同系数，如 i = (i + col*2 + N//2) % N ， ...等等。但请参阅下面的最后评论。
其他备注
我将应用以下优化:跟踪哪些行、向前“对角线”和向后“对角线”已经被采用。您可以为此使用列表或集合。请注意，如果两个单元格的坐标之和相等，则它们位于相同的前对角线上。后对角线上的单元格的共同点是它们的坐标差相等。这样您就不必每次都在这些行中扫描“1”。
另外， board可能只是一个列号列表。没有必要存储所有这些零。保留它仅用于显示。
最后，有一些简单的方法可以在线性时间内获得解决方案。见 Wikipedia .