8皇后拼图-使用python的递归
8皇后拼图-使用python的递归
提问于 2013-12-21 23:49:35
我试图解决八皇后之谜，也称为n-皇后算法。
我的功能应该计算有多少种合法的方式将N个皇后放在NxN板上。
我差点就拿到了，但得做些难看的补丁才能让它正常工作。你能帮我修一下吗？
简单介绍一下我所做的工作:试图找出在NxN表中设置N个皇后的合法方法有多少种，我试图解决在(N1)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..。因此，我知道这是可行的，但我想避免这个全局计数器。
你能帮忙吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-12-21 23:59:34
您可以使用sum的返回值来跟踪和：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20724745
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号