8皇后问题 - 使用Python递归

Question

我正在尝试解决8皇后问题，也称为n皇后算法。

我的函数应该计算在NxN棋盘上放置N个皇后的合法方式数量。

我差不多做到了，但是不得不进行一些丑陋的修补才能使其正常工作。你能帮我修复吗？

简要介绍一下我的做法： 为了找出在NxN表中设置N个皇后的合法方法数，我尝试使用对(N-1)xN情况的递归（删除第一列）进行求解。 由于不允许两个皇后在同一列上，我使用长度为N的列表。每个单元格表示一列，在每一列中，我设置皇后所在的行号。

例如，

[0, 4, 7, 5, 2, 6, 1, 3]

意思是：

• 第0列 - 皇后放置在第0行
• 第1列 - 皇后放置在第4行
• 第2列 - 皇后放置在第7行
• 第3列 - 皇后放置在第5行
• 第4列 - 皇后放置在第2行
• 第5列 - 皇后放置在第6行
• 第6列 - 皇后放置在第1行
• 第7列 - 皇后放置在第3行

让我困扰的是，我不知道如何省略非法的皇后放置。因此，为了使其正常工作，我使用了一个名为sum的全局变量，仅在递归达到合法的完全放置皇后的排列时将其增加。

def is_available(n, table, column, N):
    return not any(t in (n, n - i, n + i)
                   for t, i in zip(table, range(column, 0, -1)))

def queens_sum(N):
    table = [0]*N
    global sum
    sum = 0
    solve(N, table, 0, len(table))
    return sum

def solve(N, table, column, end):

    global sum

    if column == end:
        sum += 1
        return None

    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

< p >对于< code >N = 8，我得到了< code >sum = 92。因此我知道它有效，但我想避免使用全局变量计数器。

你能帮忙吗？

- Splash

---

小问题：sum是一个非常有用的内置函数的名称，因此不适合作为您自己变量的名称。 - DSM

当然，谢谢！ - Splash

Answer 1

您可以使用solve的返回值来跟踪总和：

def queens_sum(N):
    return solve(N, [0]*N, 0, N)

def solve(N, table, column, end):
    if column == end:
        return 1

    sum = 0
    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            sum += solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

    return sum

- bcorso

---

谢谢Gareth！问题已解决。 - bcorso