我正在尝试解决 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
关于python - 8 皇后难题 - 使用 python 递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20724745/