python - 使用回溯和递归的 N 皇后问题中的错误
问题描述
我首先实现了一个零矩阵,表示棋盘的所有位置最初都是可用的
n=int(input())
answer=[]
restrictedIndices=[[0 for i in range(n)] for j in range(n)]
dp(n,0,restrictedIndices,answer)
然后我实现了三个函数来填充restrictedIndices
def columnFill(restrictedIndices,row,column,n):
o=column
restrictedIndices[row][o]=1
while o+1<n:
o+=1
restrictedIndices[row][o]=1
o=column
while o-1>=0:
o-=1
restrictedIndices[row][o]=1
o=column
return restrictedIndices
def rowFill(restrictedIndices,row,column,n):
o=row
restrictedIndices[o][column]=1
while o+1<n:
o+=1
restrictedIndices[o][column]=1
o=row
while o-1>=0:
o-=1
restrictedIndices[o][column]=1
o=row
return restrictedIndices
def diagonalFill(restrictedIndices,row,column,n):
o=row
p=column
restrictedIndices[o][column]=1
while o+1<n and p+1<n:
o+=1
p+=1
restrictedIndices[o][p]=1
o=row
p=column
while o-1>=0 and p+1<n:
o-=1
p+=1
restrictedIndices[o][p]=1
o=row
p=column
while o+1<n and p-1>=0:
o+=1
p-=1
restrictedIndices[o][p]=1
o=row
p=column
while o-1>=0 and p-1>=0:
o-=1
p-=1
restrictedIndices[o][p]=1
o=row
p=column
return restrictedIndices
然后是递归函数
def dp(n,row,restrictedIndices,answer):
print(restrictedIndices)
if row==n:
print("yes i got a solution")
return -1
print(restrictedIndices)
for i in range(n):
if restrictedIndices[row][i]==1:
print("rejected",(row,i))
continue
else:
x=[i for i in restrictedIndices]
print(row,i)
columnFill(restrictedIndices,row,i,n)
rowFill(restrictedIndices,row,i,n)
diagonalFill(restrictedIndices,row,i,n)
dp(n,row+1,restrictedIndices,answer)
我得到了错误的输出,我想知道我们是否可以通过这种方式解决问题,以及是否有更好的选择。 我希望我能理解递归和回溯是如何通过解决方案工作的
解决方案
由于以下问题,这将不起作用:
answer
永远不会被填充:因此它只能是它的初始值,一个空列表- 尽管您
dp
在找到解决方案时让返回 -1,但调用者永远不会检查此值。所以调用者不知道它并进入其for
循环的下一次迭代 - 当递归调用
dp
返回时,restrictedIndices
列表不会返回到之前的状态。这意味着在for
循环的下一次迭代中,条件[row][i]==1
将始终为真——在第一次迭代期间,该单元格被设置为 1。您应该确保循环的每次迭代都for
以完全相同的状态开始restrictedIndices
。
我不会发布一个可行的解决方案,因为这在 Internet 上有大量文档,并且 Python 的递归解决方案也可以在 Stack Overflow 上找到:
推荐阅读
- ruby-on-rails - Rails 生成模型引用但不生成belongs_to
- python-3.x - IndexError:与单个值相比,列表索引超出范围
- mysql - 将段落文档拆分为句子
- postgresql - 使用 pg_dump 只能获取表中的一部分数据(例如 created_on> "2020-01-01")
- angular - 验证并在数据库中添加新项目
- docker - 合并请求后自动运行管道清理
- scala - 通过 spark-shell 以静默模式执行 scala 脚本
- excel - 表(已过滤)为空时的 DataBodyRange 副本
- plugins - 来自相关实体的插件更新字段
- image - 如何使扭曲的纹理看起来更平滑?