Python 中 n 皇后拼图的 2 个解决方案之间的差异

Question

对于 n 皇后问题，我有 2 个看似相同的解决方案。两者产生完全相同的结果（我在网上找到的），但第二个花费的时间是第一个的两倍多。你能帮我解释一下，有什么不同吗？

from itertools import permutations
import time

punkt1 = time.time()
N=8
sol=0
cols = range(N)
for combo in permutations(cols):                      
    if N==len(set(combo[i]+i for i in cols))==len(set(combo[i]-i for i in cols)):
        sol += 1
        print('Solution '+str(sol)+' : '+str(combo)+'\n')  
        #print("\n".join(' o ' * i + ' X ' + ' o ' * (N-i-1) for i in combo) + "\n\n\n\n")
punkt2 = time.time()
czas = punkt2 - punkt1




###################################
def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions

def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))
punkt3 = time.time()
i = 1

for solution in queensproblem(8, 8):
    print('Solution', i,':', solution, '\n')
    i = i + 1

punkt4 = time.time()
czas2 = punkt4 - punkt3
print ("Czas wykonania pierwszej metody:")
print (czas,'\n')
print ("Czas wykonania drugiej metody:")
print (czas2)

Answer 1

乍一看，您似乎是在说这些算法产生相同的结果，但在时间上相差一个常数因子，这在谈论算法时是无关紧要的。

但是，如果您将 N 设为函数参数并检查 N=9 或 N=10 的时序，您会发现它们明显不同。在 N=11 时，itertools.permutations 版本用了 12 分钟，而另一个版本用了 28 秒。如果它们以不同的速度增长，这将成为一个算法问题。

调用"for combo in permutations"的函数实际上是在查看每一个可能的棋盘，所以你可以将三个皇后排成一行，它仍然认为"I gotta keep adding queens and see if it works out"。（这是符号表示的所有可能的棋盘。符号本身消除了很多，但还不够。）

另一个功能可以停止检查不良组合，从而一次性消除许多不良候选。查看 N=4 的决策树打印输出，通过在 queensproblem for 循环中添加 print (row, solutions) 生成：

0 [[0], [1], [2], [3]]
1 [[0, 2], [0, 3], [1, 3], [2, 0], [3, 0], [3, 1]]
2 [[0, 3, 1], [1, 3, 0], [2, 0, 3], [3, 0, 2]]
3 [[1, 3, 0, 2], [2, 0, 3, 1]]

在逻辑的早期，它查看了 [0, 0] 和 [0, 1] 并简单地消除了它们。因此它从不查看 [0, 0, 0] 或......许多其他的。它继续为通过早期检查的解决方案添加新皇后。由于 "all" 和 "and".

的短路布尔逻辑，它甚至不查看它在 no_conflit 中消除的所有子问题，从而节省了大量时间

Python 中 n 皇后拼图的 2 个解决方案之间的差异

Difference between 2 solutions for n-queen puzzle in Python

python

n-queens