n_queen Python 中递归的工作原理
How recursion worked in n_queen Python
我正在尝试解决 python 中的经典 n 皇后问题。不幸的是，输出与我的预期完全不同。我了解反向跟踪算法，但可能不清楚我在编写递归时可能在哪里出错。我尝试了 1.print 一种可能的解决方案。 2.打印所有可能的解决方案。 （这里我的解决方案被标记为 n 的列表，其中 list[i] 的值是第 i 行的选定列）
def n_queen_find1(n):
answer = [-1] * n
def dfs(depth,answer):
if depth == n:
print ("cur valid answer is ",answer)
return answer
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
print ("now the answer is ", answer)
print ("now depth move to ", depth + 1)
dfs(depth + 1,answer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
return dfs(0,answer)
我期望 n_queen_find1 在 n == 4 时输出 4 个元素的列表，例如 [1, 3, 0, 2]。在我的递归过程中，生成了正确的答案（如印刷品所示）。但是，函数 return 什么也没做。我添加了那些有助于调试的打印行，发现我不明白为什么 dfs 没有停止并且 return 当第一个正确答案被创建时？
trial1 = n_queen_find1(4)
print trial1
('now the answer is ', [0, -1, -1, -1])
('now depth move to ', 1)
('now the answer is ', [0, 2, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, 1, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 1)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 2)
('now the answer is ', [1, 3, 0, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 0, 2])
('now depth move to ', 4)
('cur valid answer is ', [1, 3, 0, 2])
('now the answer is ', [2, 3, 0, 2])
('now depth move to ', 1)
('now the answer is ', [2, 0, 0, 2])
('now depth move to ', 2)
('now the answer is ', [2, 0, 3, 2])
('now depth move to ', 3)
('now the answer is ', [2, 0, 3, 1])
('now depth move to ', 4)
('cur valid answer is ', [2, 0, 3, 1])
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 1)
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 2)
('now the answer is ', [3, 0, 2, 1])
('now depth move to ', 3)
('now the answer is ', [3, 1, 2, 1])
('now depth move to ', 2)
None
我稍微修改了 n_queen_find1 以生成所有可能的解决方案，但我也无法解释输出。
def n_queen_findall(n):
answer = [-1] * n
finalAnswer = []
def dfs(depth,answer,finalAnswer):
if depth == n:
print ("cur valid answer is ",answer)
finalAnswer.append(answer)
print ("after appending final answer is ", finalAnswer)
return
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
print ("now the answer is ", answer)
print ("now depth move to ", depth + 1)
dfs(depth + 1,answer,finalAnswer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
dfs(0,answer,finalAnswer)
return finalAnswer
这是我对 n_queen_findall 的测试。它也不正确。首先，为什么当深度不等于 n 时 finalAnswers 会追加结果？二、finalAnswer为什么重复了？
trial2 = n_queen_findall(4)
print trial2
('now the answer is ', [0, -1, -1, -1])
('now depth move to ', 1)
('now the answer is ', [0, 2, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, 1, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 1)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 2)
('now the answer is ', [1, 3, 0, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 0, 2])
('now depth move to ', 4)
('cur valid answer is ', [1, 3, 0, 2])
('now the final answer is ', [])
('now the answer is ', [2, 3, 0, 2])
('now depth move to ', 1)
('now the answer is ', [2, 0, 0, 2])
('now depth move to ', 2)
('now the answer is ', [2, 0, 3, 2])
('now depth move to ', 3)
('now the answer is ', [2, 0, 3, 1])
('now depth move to ', 4)
('cur valid answer is ', [2, 0, 3, 1])
('now the final answer is ', [[2, 0, 3, 1]])
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 1)
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 2)
('now the answer is ', [3, 0, 2, 1])
('now depth move to ', 3)
('now the answer is ', [3, 1, 2, 1])
('now depth move to ', 2)
[[3, 1, 2, 1], [3, 1, 2, 1]]
很抱歉提出问题 long.The 这个问题的起因在 python 中可能相当 simple.I 初级，尤其是 python backend.Maybe 我的对 python 通过引用传递的理解不正确？非常感谢对此的一些指导。非常感谢。
在您的 dfs 中，您只有在 n==4 时才会有 return，而当 n 为其他任何值时则没有。因此，无论 dfs return 用于 4，它们都会被父级调用者吸收，最终什么也不会 returned。
所以要解决你的第一个问题，因为我们知道答案 returns None 中失败的展示位置，（因为 if in for loop inside else 将失败），我们在递归 dfs 之前添加一个 if 来检查是否成功。如果是这样，我们 return answer。所以只要改变这个：
dfs(depth + 1,answer)
对此：
if dfs(depth + 1,answer): #false i.e None for failed dfs
return answer
在我们解决第二个问题之前，让我们想想，如果我们有5个解决方案，我们需要5个数组来存储它们，对吧？你有多少？一个 answer。在 finalAnswer.append(answer) 中，您没有附加包含数组的较新解决方案，您只是附加了我们旧 answer 的 reference，它不断被修改以及您想要附加的任何内容迷路了。
因此您需要在追加之前复制并创建新数组。此外，您还需要摆脱上述 return。
def n_queen_find1(n):
answer = [-1] * n
finalAnswer = []
def dfs(depth,answer):
if depth == n:
print ("cur valid answer is ",answer)
finalAnswer.append([i for i in answer]) #answer is copied
return answer
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
#print ("now the answer is ", answer)
#print ("now depth move to ", depth + 1)
dfs(depth + 1,answer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
dfs(0,answer)
return finalAnswer
打印：
cur valid answer is [1, 3, 0, 2]
cur valid answer is [2, 0, 3, 1]
[[1, 3, 0, 2], [2, 0, 3, 1]]
我正在尝试解决 python 中的经典 n 皇后问题。不幸的是，输出与我的预期完全不同。我了解反向跟踪算法，但可能不清楚我在编写递归时可能在哪里出错。我尝试了 1.print 一种可能的解决方案。 2.打印所有可能的解决方案。 （这里我的解决方案被标记为 n 的列表，其中 list[i] 的值是第 i 行的选定列）
def n_queen_find1(n):
answer = [-1] * n
def dfs(depth,answer):
if depth == n:
print ("cur valid answer is ",answer)
return answer
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
print ("now the answer is ", answer)
print ("now depth move to ", depth + 1)
dfs(depth + 1,answer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
return dfs(0,answer)
我期望 n_queen_find1 在 n == 4 时输出 4 个元素的列表，例如 [1, 3, 0, 2]。在我的递归过程中，生成了正确的答案（如印刷品所示）。但是，函数 return 什么也没做。我添加了那些有助于调试的打印行，发现我不明白为什么 dfs 没有停止并且 return 当第一个正确答案被创建时？
trial1 = n_queen_find1(4)
print trial1
('now the answer is ', [0, -1, -1, -1])
('now depth move to ', 1)
('now the answer is ', [0, 2, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, 1, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 1)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 2)
('now the answer is ', [1, 3, 0, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 0, 2])
('now depth move to ', 4)
('cur valid answer is ', [1, 3, 0, 2])
('now the answer is ', [2, 3, 0, 2])
('now depth move to ', 1)
('now the answer is ', [2, 0, 0, 2])
('now depth move to ', 2)
('now the answer is ', [2, 0, 3, 2])
('now depth move to ', 3)
('now the answer is ', [2, 0, 3, 1])
('now depth move to ', 4)
('cur valid answer is ', [2, 0, 3, 1])
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 1)
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 2)
('now the answer is ', [3, 0, 2, 1])
('now depth move to ', 3)
('now the answer is ', [3, 1, 2, 1])
('now depth move to ', 2)
None
我稍微修改了 n_queen_find1 以生成所有可能的解决方案，但我也无法解释输出。
def n_queen_findall(n):
answer = [-1] * n
finalAnswer = []
def dfs(depth,answer,finalAnswer):
if depth == n:
print ("cur valid answer is ",answer)
finalAnswer.append(answer)
print ("after appending final answer is ", finalAnswer)
return
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
print ("now the answer is ", answer)
print ("now depth move to ", depth + 1)
dfs(depth + 1,answer,finalAnswer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
dfs(0,answer,finalAnswer)
return finalAnswer
这是我对 n_queen_findall 的测试。它也不正确。首先，为什么当深度不等于 n 时 finalAnswers 会追加结果？二、finalAnswer为什么重复了？
trial2 = n_queen_findall(4)
print trial2
('now the answer is ', [0, -1, -1, -1])
('now depth move to ', 1)
('now the answer is ', [0, 2, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, -1, -1])
('now depth move to ', 2)
('now the answer is ', [0, 3, 1, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 1)
('now the answer is ', [1, 3, 1, -1])
('now depth move to ', 2)
('now the answer is ', [1, 3, 0, -1])
('now depth move to ', 3)
('now the answer is ', [1, 3, 0, 2])
('now depth move to ', 4)
('cur valid answer is ', [1, 3, 0, 2])
('now the final answer is ', [])
('now the answer is ', [2, 3, 0, 2])
('now depth move to ', 1)
('now the answer is ', [2, 0, 0, 2])
('now depth move to ', 2)
('now the answer is ', [2, 0, 3, 2])
('now depth move to ', 3)
('now the answer is ', [2, 0, 3, 1])
('now depth move to ', 4)
('cur valid answer is ', [2, 0, 3, 1])
('now the final answer is ', [[2, 0, 3, 1]])
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 1)
('now the answer is ', [3, 0, 3, 1])
('now depth move to ', 2)
('now the answer is ', [3, 0, 2, 1])
('now depth move to ', 3)
('now the answer is ', [3, 1, 2, 1])
('now depth move to ', 2)
[[3, 1, 2, 1], [3, 1, 2, 1]]
很抱歉提出问题 long.The 这个问题的起因在 python 中可能相当 simple.I 初级，尤其是 python backend.Maybe 我的对 python 通过引用传递的理解不正确？非常感谢对此的一些指导。非常感谢。
在您的 dfs 中，您只有在 n==4 时才会有 return，而当 n 为其他任何值时则没有。因此，无论 dfs return 用于 4，它们都会被父级调用者吸收，最终什么也不会 returned。
所以要解决你的第一个问题，因为我们知道答案 returns None 中失败的展示位置，（因为 if in for loop inside else 将失败），我们在递归 dfs 之前添加一个 if 来检查是否成功。如果是这样，我们 return answer。所以只要改变这个：
dfs(depth + 1,answer)
对此：
if dfs(depth + 1,answer): #false i.e None for failed dfs
return answer
在我们解决第二个问题之前，让我们想想，如果我们有5个解决方案，我们需要5个数组来存储它们，对吧？你有多少？一个 answer。在 finalAnswer.append(answer) 中，您没有附加包含数组的较新解决方案，您只是附加了我们旧 answer 的 reference，它不断被修改以及您想要附加的任何内容迷路了。
因此您需要在追加之前复制并创建新数组。此外，您还需要摆脱上述 return。
def n_queen_find1(n):
answer = [-1] * n
finalAnswer = []
def dfs(depth,answer):
if depth == n:
print ("cur valid answer is ",answer)
finalAnswer.append([i for i in answer]) #answer is copied
return answer
else:
for colNum in range(n): # check every col at cur depth
if is_safe(depth,colNum,answer):
answer[depth] = colNum
#print ("now the answer is ", answer)
#print ("now depth move to ", depth + 1)
dfs(depth + 1,answer)
def is_safe(i,j,answer_cur):
# given current queen placement , could we place the ith queen (at row i) at the col j
for prerow in range(i):
if answer_cur[prerow] == j or abs(prerow - i) == abs(answer_cur[prerow] - j):
return False
return True
dfs(0,answer)
return finalAnswer
打印：
cur valid answer is [1, 3, 0, 2]
cur valid answer is [2, 0, 3, 1]
[[1, 3, 0, 2], [2, 0, 3, 1]]