Python递归回溯算法详解：八皇后问题完美解决方案
本文详细解析如何使用Python的递归回溯算法解决经典的八皇后问题。通过生成器yield优化代码结构，深入讲解冲突判断逻辑、递归调用机制及回溯过程，并提供从4皇后到8皇后的完整代码实现与执行流程分析，帮助开发者掌握这一核心算法思想。
八皇后问题描述与规则分析
八皇后问题的核心挑战在于：在8×8的国际象棋棋盘上放置8个皇后棋子，使得任意两个棋子均不处于同一行、同一列或同一条斜线上。我们需要找出所有满足该条件的合法摆放方案数量。
规则分析：
确保任意两个棋子不在同一行相对容易实现。我们可以维护一个队列（列表），队列中的每个元素索引代表棋盘的行号，从而天然保证每行只有一个棋子。
确保任意两个棋子不在同一列同样可以通过数据结构处理。队列中每个元素的值代表该行棋子所在的列号。例如，元组(0, 7, 3)表示第1行棋子位于第1列（索引0），第2行位于第8列（索引7），第3行位于第4列（索引3）。这里列号从0开始计数。
对于斜线约束，可将棋盘视为XOY坐标系，原点设在左上角。斜线的斜率为1或-1，其中X代表列号，Y代表行号。斜线方程可表示为Y=X+n或Y=-X+n（n为常数，由具体斜线决定）。由此推导出Y-X=n或Y+X=n。这意味着，若两个棋子位于同一条斜线上，它们的行号与列号之和（Y+X）或差值（Y-X）必然相等。即：X1+Y1=X2+Y2 或 X1-Y1=X2-Y2。经过变换可得|X1-Y1|=|Y1-Y2|（注：原文此处推导有笔误，实际应为行号差绝对值等于列号差绝对值）。因此，判断两个棋子是否在同一条斜线上，只需检查它们列号之差的绝对值是否等于行号之差的绝对值。
如下图：
将上述逻辑转化为代码，即可实现棋子冲突检测（abs(num)用于获取num的绝对值）。
def is_rule(queen_tup, new_queen):
"""
:param queen_tup: 棋子队列，用于保存已经放置好的棋子，数值代表相应棋子列号
:param new_queen: 被检测棋子，数值代表列号
:return: True表示符合规则，False表示不符合规则
"""
num = len(queen_tup)
for index, queen in enumerate(queen_tup):
if new_queen == queen: # 判断列号是否相等
return False
if abs(new_queen-queen) == num-index: # 判断列号之差绝对值是否与行号之差相等
return False
return True实际上，这段代码可以进一步简化。判断列号之差是否等于行号之差，可以转化为判断列号之差的绝对值是否存在于特定集合中（即行号差或0）。利用Python的in运算符即可完成整体判断。修改后的代码如下。
def is_rule(queen_tup, new_queen):
"""判断棋子是否符合规则"""
for index, queen in enumerate(queen_tup):
if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判断表达式
return False
return True递归回溯算法实现
接下来编写放置棋子的核心函数。
放置棋子主要有两种思路。第一种是生成8×8棋盘上每行放置一个棋子的所有全排列，然后逐一使用冲突函数检测是否符合规则，符合则加入结果队列。
第二种思路是逐行放置：在当前行放置一个棋子，检测是否符合规则；若符合，则进入下一行；若下一行所有位置均不符合规则，则回溯到上一行，尝试放置该行的下一个位置，再重新进入下一行检测。这种方法称为递归回溯法，每一行的尝试点即为一个回溯点。
本文采用第二种方法编写函数，先展示代码，随后进行详细解释。
def arrange_queen(num, queen_tup=list()):
"""
:param num:棋盘的的行数，当然数值也等于棋盘的列数
:param queen_tup: 设置一个空队列，用于保存符合规则的棋子的信息
"""
for new_queen in range(num): # 遍历一行棋子的每一列
if is_rule(queen_tup, new_queen): # 判断是否冲突
if len(queen_tup) == num-1: # 判断是否是最后一行
yield [new_queen] # yield关键字
else:
# 若果不是最后一行，递归函数接着放置棋子
for result in arrange_queen(num, queen_tup+[new_queen]):
yield [new_queen] + result若能理解上述函数，可跳过后续分析；若仍有疑问，将通过具体代码示例进一步说明。
生成器与递归函数详解
首先涉及Python关键字yield，带有yield的函数被称为生成器函数。函数执行时，遇到yield会暂停执行，并返回yield右侧的对象给调用处；下次执行时，从yield处继续运行。若函数执行完毕未再遇到yield，则抛出StopIteration异常。生成器函数需通过next()方法驱动。以下代码演示生成器的执行过程：
def demo():
yield 1
yield 2
print('end')
b = demo() # 将生成器函数的引用传递给变量b
print(next(b)) # 第一次执行生成器函数，返回 1 同时函数暂停，打印结果
print(next(b)) # 第二次执行生成器函数，返回 2 同时函数暂停，打印结果
print(next(b)) # 第三次执行生成器函数，因为没有再遇到yield，函数执行完毕，抛出异常StopIteration然而，在放置棋子的代码中，并未直接调用next()，而是使用for循环遍历，且执行完毕后未抛出StopIteration错误。这是因为for循环内部会自动不断调用next()，并在捕获StopIteration异常时终止循环。以下代码模拟了for循环驱动生成器的过程：
def demo():
yield 1
yield 2
print('end')
# 模拟的for循环
b = demo()
while True:
try:
next(b)
"""
此段区域写for下的代码块
"""
except StopIteration:
break
# 实际的for循环
for i in demo():
"""
for 下的代码块
"""
pass由此可知，当使用for循环驱动生成器时，若函数执行完毕未再遇到yield，for循环将直接退出，不执行循环体下方的代码。值得注意的是，上述两个示例分别调用了两次生成器函数。生成器函数在一次完整执行完毕后，再次调用将无法得到结果。
理解生成器与for循环的驱动机制后，再看棋子摆放函数中的另一个关键概念：递归函数。以往教学中，递归常用于计算数值阶乘，此处亦以阶乘为例解释递归执行过程。阶乘定义：给定正整数n，n!=n(n-1)(n-2)...1，即从1到n的累乘。（注：0!=1为数学规定）。
def a(num):
result = num*b(num-1)
return result
def b(num):
result = num*c(num-1)
return result
def c(num):
if num == 1:
result = 1
return result
result = a(3)
print(result)上述代码展示了函数嵌套，仅用于计算3的阶乘，此处借其理解递归逻辑。
调用a(3)时，传入参数3，进而调用b(2)，b再调用c(1)。c执行判断，若参数符合则返回result至c的调用处，与b的参数2相乘，得到新result赋值给b，再返回至a的调用处，与a的参数3相乘，最终返回a的结果并打印。
这是通过函数嵌套计算3!的过程。若需计算10000!，难道要编写10000个函数吗？
观察发现，a、b、c函数除变量名外结构完全相同。因此，可直接在a内部调用a自身，形式如下：
def a(num):
result = num*a(num-1)
return result但这样会导致无限递归。因此需添加终止条件，修改为：
def a(num):
if num == 1:
return 1
else:
return num*a(num-1)
result = a(3)
print(result)这就是最基础的递归函数结构。
分析函数运行：首次调用传递参数3，不满足终止条件，继续执行；再次调用a(2)，仍不满足；第三次调用a(1)，满足终止条件，第三次调用的函数结束，返回1至调用处，与2相乘；第二次调用结束，结果返回至第一次调用处，与3相乘，最终返回。
这便是简单递归函数的执行流程。总结而言，递归函数不断调用自身，直至满足终止条件。
四皇后执行过程演示
明确了含yield的生成器、for循环驱动机制及递归调用后，再回顾八皇后摆放函数。为便于观察，将“八皇后”简化为“四皇后”，即计算4×4棋盘上放置4个棋子的方案。
def arrange_queen(num, queen_tup=list()):
"""
:param num:棋盘的的行数，当然数值也等于棋盘的列数
:param queen_tup: 设置一个空队列，用于保存符合规则的棋子的信息
"""
for new_queen in range(num): # 遍历一行棋子的每一列
if is_rule(queen_tup, new_queen): # 判断是否冲突
if len(queen_tup) == num-1: # 判断是否是最后一行
yield [new_queen] # yield关键字
else:
# 若果不是最后一行，递归函数接着放置棋子
for result in arrange_queen(num, queen_tup+[new_queen]):
yield [new_queen] + result
for i in arrange_queen(4):
print(i)执行结果为：
[1,3,0,2]
[2,0,3,1]
以下描述函数执行过程：
1. 放置第一行棋子。函数首次调用，传递参数4及空列表。尝试将棋子置于第一行第一列，检测符合规则，且非最后一行，将位置信息[0]存入列表。
2. 放置第二行棋子。函数二次调用，传递参数4及列表[0]。尝试第二行第一列，冲突；尝试第二列，冲突；尝试第三列，符合规则，将[0, 2]存入列表。
3. 放置第三行棋子。函数三次调用，传递参数4及列表[0, 2]。依次尝试第三行各列：第一列冲突，第二列冲突，第三列冲突，第四列仍冲突。第三次调用结束。
4. 回溯至第二次调用处。该函数继续尝试放置棋子，上次停在第三列，现尝试第四列，符合规则，将[0, 3]存入列表。
5. 函数再次调用，用于放置第三行，从第一列依次检测至最后一列，若符合则存入信息，生成新列表[0, 3, 1]。
6. 函数调用，用于放置第四行，从第一列检测至最后一列，均不符合规则，函数执行完毕，回溯至上一级。
.......
N. 当前三行棋子均符合规则，且第四行也找到合法位置时，首次遇到yield关键字。第四级函数暂停，将棋子信息[2]存入列表，返回至第三级；第三级函数将符合规则的信息存入列表，并与第四级返回的列表合并，得到新列表；随后遇到第三级的yield，暂停并返回[0, 2]至第二级……直至第一级函数暂停，返回结果[1, 3, 0, 2]并打印。
随后，第一级函数继续执行，驱动二级函数，二级驱动三级，三级驱动四级……
直至所有结果打印完毕，整个函数执行结束。
完整代码与总结
完整代码如下：
def is_rule(queen_tup, new_queen):
"""判断棋子是否符合规则"""
for index, queen in enumerate(queen_tup):
if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判断表达式
return False
return True
def arrange_queen(num, queen_tup=list()):
"""
:param num:棋盘的的行数，当然数值也等于棋盘的列数
:param queen_tup: 设置一个空队列，用于保存符合规则的棋子的信息
"""
for new_queen in range(num): # 遍历一行棋子的每一列
if is_rule(queen_tup, new_queen): # 判断是否冲突
if len(queen_tup) == num-1: # 判断是否是最后一行
yield [new_queen] # yield关键字
else:
# 若果不是最后一行，递归函数接着放置棋子
for result in arrange_queen(num, queen_tup+[new_queen]):
yield [new_queen] + result
for i in arrange_queen(8):
print(i)代码的核心在于递归回溯思想。若能真正理解此逻辑，无论使用何种语法或函数形式，均可轻松解决八皇后问题。
接下来展示一个八皇后的终极版代码（来源百度百科），未使用yield关键字。读者可自行理解其实现：
def queen(A, cur=0):
if cur == len(A):
print(A)
return 0
for col in range(len(A)):
A[cur], flag = col, True
for row in range(cur):
if A[row] == col or abs(col - A[row]) == cur - row:
flag = False
break
if flag:
queen(A, cur+1)
queen([None]*8)八皇后的所有解：
[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
[0, 6, 4, 7, 1, 3, 5, 2]
[1, 3, 5, 7, 2, 0, 6, 4]
[1, 4, 6, 0, 2, 7, 5, 3]
[1, 4, 6, 3, 0, 7, 5, 2]
[1, 5, 0, 6, 3, 7, 2, 4]
[1, 5, 7, 2, 0, 3, 6, 4]
[1, 6, 2, 5, 7, 4, 0, 3]
[1, 6, 4, 7, 0, 3, 5, 2]
[1, 7, 5, 0, 2, 4, 6, 3]
[2, 0, 6, 4, 7, 1, 3, 5]
[2, 4, 1, 7, 0, 6, 3, 5]
[2, 4, 1, 7, 5, 3, 6, 0]
[2, 4, 6, 0, 3, 1, 7, 5]
[2, 4, 7, 3, 0, 6, 1, 5]
[2, 5, 1, 4, 7, 0, 6, 3]
[2, 5, 1, 6, 0, 3, 7, 4]
[2, 5, 1, 6, 4, 0, 7, 3]
[2, 5, 3, 0, 7, 4, 6, 1]
[2, 5, 3, 1, 7, 4, 6, 0]
[2, 5, 7, 0, 3, 6, 4, 1]
[2, 5, 7, 0, 4, 6, 1, 3]
[2, 5, 7, 1, 3, 0, 6, 4]
[2, 6, 1, 7, 4, 0, 3, 5]
[2, 6, 1, 7, 5, 3, 0, 4]
[2, 7, 3, 6, 0, 5, 1, 4]
[3, 0, 4, 7, 1, 6, 2, 5]
[3, 0, 4, 7, 5, 2, 6, 1]
[3, 1, 4, 7, 5, 0, 2, 6]
[3, 1, 6, 2, 5, 7, 0, 4]
[3, 1, 6, 2, 5, 7, 4, 0]
[3, 1, 6, 4, 0, 7, 5, 2]
[3, 1, 7, 4, 6, 0, 2, 5]
[3, 1, 7, 5, 0, 2, 4, 6]
[3, 5, 0, 4, 1, 7, 2, 6]
[3, 5, 7, 1, 6, 0, 2, 4]
[3, 5, 7, 2, 0, 6, 4, 1]
[3, 6, 0, 7, 4, 1, 5, 2]
[3, 6, 2, 7, 1, 4, 0, 5]
[3, 6, 4, 1, 5, 0, 2, 7]
[3, 6, 4, 2, 0, 5, 7, 1]
[3, 7, 0, 2, 5, 1, 6, 4]
[3, 7, 0, 4, 6, 1, 5, 2]
[3, 7, 4, 2, 0, 6, 1, 5]
[4, 0, 3, 5, 7, 1, 6, 2]
[4, 0, 7, 3, 1, 6, 2, 5]
[4, 0, 7, 5, 2, 6, 1, 3]
[4, 1, 3, 5, 7, 2, 0, 6]
[4, 1, 3, 6, 2, 7, 5, 0]
[4, 1, 5, 0, 6, 3, 7, 2]
[4, 1, 7, 0, 3, 6, 2, 5]
[4, 2, 0, 5, 7, 1, 3, 6]
[4, 2, 0, 6, 1, 7, 5, 3]
[4, 2, 7, 3, 6, 0, 5, 1]
[4, 6, 0, 2, 7, 5, 3, 1]
[4, 6, 0, 3, 1, 7, 5, 2]
[4, 6, 1, 3, 7, 0, 2, 5]
[4, 6, 1, 5, 2, 0, 3, 7]
[4, 6, 1, 5, 2, 0, 7, 3]
[4, 6, 3, 0, 2, 7, 5, 1]
[4, 7, 3, 0, 2, 5, 1, 6]
[4, 7, 3, 0, 6, 1, 5, 2]
[5, 0, 4, 1, 7, 2, 6, 3]
[5, 1, 6, 0, 2, 4, 7, 3]
[5, 1, 6, 0, 3, 7, 4, 2]
[5, 2, 0, 6, 4, 7, 1, 3]
[5, 2, 0, 7, 3, 1, 6, 4]
[5, 2, 0, 7, 4, 1, 3, 6]
[5, 2, 4, 6, 0, 3, 1, 7]
[5, 2, 4, 7, 0, 3, 1, 6]
[5, 2, 6, 1, 3, 7, 0, 4]
[5, 2, 6, 1, 7, 4, 0, 3]
[5, 2, 6, 3, 0, 7, 1, 4]
[5, 3, 0, 4, 7, 1, 6, 2]
[5, 3, 1, 7, 4, 6, 0, 2]
[5, 3, 6, 0, 2, 4, 1, 7]
[5, 3, 6, 0, 7, 1, 4, 2]
[5, 7, 1, 3, 0, 6, 4, 2]
[6, 0, 2, 7, 5, 3, 1, 4]
[6, 1, 3, 0, 7, 4, 2, 5]
[6, 1, 5, 2, 0, 3, 7, 4]
[6, 2, 0, 5, 7, 4, 1, 3]
[6, 2, 7, 1, 4, 0, 5, 3]
[6, 3, 1, 4, 7, 0, 2, 5]
[6, 3, 1, 7, 5, 0, 2, 4]
[6, 4, 2, 0, 5, 7, 1, 3]
[7, 1, 3, 0, 6, 4, 2, 5]
[7, 1, 4, 2, 0, 6, 3, 5]
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]
最后，对比其他语言解决八皇后问题的代码量：
以上关于Python使用递归回溯完美解决八皇后问题的内容分享到此结束，希望能为读者提供参考，也欢迎大家支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
