Skip to main content
 首页 » 编程设计

python之8 皇后难题之使用 python 递归

2024年11月01日12zdz8207

我正在尝试解决 8-queens puzzle ,也称为 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 

对于 N = 8,我得到 sum = 92.. 因此我知道它有效,但我想避免使用这个全局计数器。

你能帮忙吗?

请您参考如下方法:

您可以使用 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