引入：
本节我们进一步完善八皇后问题，学习剪枝、八皇后残局问题 进一步领会逻辑编程的概念，深入体会回溯算法，回顾上一节提到的启发搜索策略。
回顾：
八皇后问题：我们需要在一个空棋盘上放置 n 个皇后，使得任意两个皇后不能在同一行、同一列或同一对角线上。
我们使用回溯算法逐行尝试放置皇后，并通过冲突检测剪枝无效的分支实现。
def spin(row): # 回溯算法def is_valid(row, col): def prt():# 主程序入口
spin(0) # 从第 0 行开始求解
print(f"总共有 {sol_num} 种解法。")现在问题在于，当我们输入n=10时，解已经输出2680个了， 跑了大概十几秒钟才出来。这时我们发现，这其中很大一部分解之间是可以通过旋转对称得到的，如果能消除这些由旋转对称得到的解，是否能提高速度呢？
显然是可以的，在应用“对称剪枝”后，n=10的输出几乎是一瞬间的事。
那么，剪枝是什么呢？
剪枝
剪枝就是在搜索或计算过程中提前终止无效路径，从而减少不必要的计算。
我们在上一节似乎做过这件事！
# 尝试在当前行的每一列放置皇后
for col in range(n):if is_valid(row, col): # 如果当前位置有效board[row] = col # 放置皇后spin(row + 1) # 递归处理下一行board[row] = -1 # 回溯，撤销放置没错，上一节设定is_valid()函数的手段就是剪枝！
通过is_valid()函数判断该节点是否有解，若无解返回 False，则直接跳过后续递归，因为从这个树杈长出去的其他枝干都无解，就剪枝了。
剪枝的类型
可行性剪枝：
当前节点不满足约束条件，则剪枝。
最优性剪枝：
求最优解时，若当前局部解已劣于已知最优解，则剪枝。
启发式剪枝：
利用经验规则（启发式函数）优先剪掉低概率分支。
还有接下来的
对称剪枝：
若两个解（或部分解）可以通过旋转、镜像、置换等对称操作相互转换，则它们是对称等价的。
对称剪枝的实现
显然，将棋盘沿对称轴分两半，从第一行看两侧的遍历路径总是一样的，因此我们考虑只计算一半情况的解。
但棋盘并不总是偶数X偶数的，遇到奇数怎么办？
很简单，单独计算中间这一行即可！
因此，当棋盘为偶数时，我们只计算第一行一半的解，如果是奇数，则加上中间一列产生的解：
# 对称性剪枝：限制第一行的皇后位置if n > 0:for col in range(n // 2): # 只考虑第一行的一半列board[0] = colspin(1) # 从第二行开始递归# 如果 n 是奇数，单独处理中间列if n % 2 == 1:board[0] = n // 2spin(1)静态剪枝 VS 动态剪枝
你可能想问：为什么只对第一行剪枝，第二行第三行呢？是不是剪得越多算得越快呢？
实则不然，这就是对称剪枝策略的核心——通常我们只对搜索树的浅层（如第一行）进行静态剪枝。
我们之所以能对第一行对称剪枝是因为其对称性未被破坏，
而一旦放置皇后后，后续的对称性就会被破坏：例如第一行皇后放在列0，棋盘就会失去90°旋转对称性。
因此进行深层剪枝时，往往需要动态判断是否有某种对称性，其计算成本（包括分解和递归）和动态存储空间都是阶乘级的上涨。
结论：虽然动态剪枝减少了节点数，但增加的判断时间反而导致总耗时上升。
因此我们只对已知初始状态的第一行进行对称剪枝！
完整代码仅仅是在之前代码上添加了对称性剪枝这一部分：
def solve_n_queens(n):def is_valid(board, row, col):"""检查当前位置 (row, col) 是否有效"""for i in range(row): if board[i] == col or abs(i - row) == abs(board[i] - col):return Falsereturn Truedef spin(row):"""回溯函数"""nonlocal sol_numif row == n: # 如果所有行都放置了皇后sol_num += 1returnfor col in range(n):if is_valid(board, row, col): # 剪枝：只有有效位置才继续board[row] = col # 放置皇后spin(row + 1) # 递归处理下一行board[row] = -1 # 回溯，撤销放置# 初始化board = [-1] * n # board[i] 表示第 i 行中皇后所在的列号sol_num = 0# 对称性剪枝：限制第一行的皇后位置if n > 0:for col in range(n // 2): # 只考虑第一行的一半列board[0] = colspin(1) # 从第二行开始递归# 如果 n 是奇数，单独处理中间列if n % 2 == 1:board[0] = n // 2spin(1)return sol_numn = int(input("请输入棋盘大小 n："))
sol_num = solve_n_queens(n)
print(f"总共有 {sol_num} 种解法。")皇后残局问题
在一个 n x n 的国际象棋棋盘上，已放置若干皇后且互不攻击，需继续放置剩余皇后至 n 个，满足任意两皇后不在同一行、列或对角线上。
输入：
- 输入一个n，代表棋盘的大小。
- 输入一个二维 n x n 的棋盘状态，其中部分格子已经有皇后（用‘Q’表示），其余格子为空（用 '.' 表示）。
4
.Q..
...Q
....
....输出：
- 如果存在解，则输出所有可能的完整解（即棋盘上放置了
n个互不攻击的皇后）。 - 如果无解，则输出“无解”。
解法 1:
.Q..
...Q
Q...
..Q.共找到 1 种解法。实现思路
我们考虑相较于一般皇后问题，残局问题做了哪些改变？我们应该如何应对？
(1) 初始棋盘状态
棋盘已经部分皇后——遍历棋盘，保留在board中。
(2) 约束条件
固定的皇后增加了约束条件：新皇后不仅要满足自身约束规则，还须与已固定的皇后兼容——输入时先对残局检查冲突，放入新皇后时直接跳过这些行。
(3) 解空间
固定的皇后减少了搜索空间——直接跳过。
若固定皇后间存在冲突，则直接无解。
因此，修改原思路：
① 初始化与解析：首先初始化容器并解析棋盘。
② 初始检查：检查初始棋盘自身是否冲突
③ 调用回溯函数：不冲突则调用回溯函数
④ 结束判断：回溯函数先检查当前是否满足结束条件（所有行都有皇后）
⑤ 遍历每一列：若这一列有固定皇后则跳过
⑥ 约束条件：否则判断是否满足约束条件。若满足，则保存当前状态，同时为了下一次遍历到这里时这一层是空的（有皇后就会被略过）要将这一层还原为空，接着处理下一行。
⑦ 如果不满足约束条件则自动判断当前是否是这一行的最后一个元素，如果是，证明这一行无论皇后放在哪都无解，因此自动返回上一行重新找解
⑧ 如果不是，就继续遍历下一列直到找到可以放皇后的位置。
代码实现：
一、初始化与解析：
初始化列表参考上一节：
# 初始化
board = [-1] * n # 当前棋盘状态（-1 表示未放置皇后）
solutions = [] # 存储所有解
sol_num = 0首先考虑如何接收这个残局，
在上一节中，我们用列表board[]保存每一行皇后的位置，
因此我们的任务是如何从nxn的输入中读取Q的位置存进board[]列表中。
由于输入是 n x n 的，我们使用for_in_range(n)循环n次接收n行的输入，并将其存入初始表格initial_board[]中。
initial_board = [input().strip() for _ in range(n)] # 接收一维数组其中 for _ in 仅表示循环 n 次，不关心当前迭代的索引，strip()去掉每一行输入的换行符。
输入后initial_board的内容是：
initial_board = ['.Q..', '...Q', '....', '....']接着直接调用问题解决函数：
if __name__ == "__main__":n = int(input("请输入棋盘大小 n："))print("请输入初始棋盘状态（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)] # 接收一维数组solve_n_queens_with_given_board(n, initial_board)接着是如何解析initial_board[]中皇后的位置，我们考虑遍历每一个元素“字符串”，在这个字符串中寻找是否有'Q'字符，如果有就在board对应位置保存，没有就跳过。
# 解析初始棋盘
for r in range(n):if initial_board第r元素有'Q'：c = 'Q'的位置board[第r元素] = 'Q'的位置else:pass那么如何从字符串中找指定字符呢？
我们想到index()函数，他会返回对象中与要找字符匹配的第一个元素的下标。
X = '1919810'
print(X.index('9'))
#输出1代码也就很容易想到了：
# 解析初始棋盘for r in range(n):try:c = initial_board[r].index('Q') # 找到 'Q' 的列索引board[r] = c # 固定该位置except ValueError:pass # 如果该行没有 'Q'，跳过二、初始检查：检查初始棋盘自身是否冲突
由于上一节的约束条件在这里不变，因此保留is_valid()判断函数。
那么接下来的任务就是检查初始棋盘是否冲突了
刚刚我们将initial_board的内容放到了board中，因此我们对board每一元素遍历，如果其值不为-1证明这一行有固定皇后，触发冲突判断
is_valid()的参数列表是
def is_valid(board, row, col):因此我们还要把当前位置传给他，假设遍历到第r行，且有'Q'元素，则其位置为board[r]，即纵坐标为board[r]：
def is_valid(board, r, board[r]):完整代码：
# 检查初始棋盘是否有冲突for r in range(n):if board[r] != -1: # 如果当前行有固定皇后if not is_valid(board, r, board[r]):print("无解")return三、回溯算法：
由于固定皇后的存在，解空间减小了，因此遍历行时，会有两种情况：
①该行已有固定皇后，则检测是否冲突。
②该行为空，则和普通皇后问题一样进行列遍历找地方放皇后。
当然，在执行遍历行前，还要优先进行终点判定：
如果当前行是最后一行则将棋盘状态保存在result中，[:]代表选择全部。同时解数量加一。
if row == n: # 如果所有行都放置了皇后result.append(board[:])sol_num += 1return对于情况①，如果固定皇后存在，则进行冲突判断。
由于我们在解析initial_board[]的时候已经记录过固定皇后的位置了，其实if下面那一行是多余的，但为了与情况②保存代码对称，我们依然保留。
if initial_board[row] != -1: # 如果当前行已经有固定的皇后if is_valid(board, row, initial_board[row]): # 检查是否冲突board[row] = initial_board[row]spin(row + 1)board[row] = -1else: # 如果冲突，则无解return对于情况② ，如果该行为空，则正常进行列遍历，找合适位置放入皇后。
else: # 如果当前行没有固定的皇后for col in range(n):if is_valid(board, row, col): # 剪枝：只有有效位置才继续board[row] = col # 放置皇后spin(row + 1) # 递归处理下一行board[row] = -1 # 回溯，撤销放置四、输出函数
你可能已经注意到了，我们找到解后并没有立马输出，而是保存在result[]中。
因此输出函数就是要从result[]中迭代输出解（用上一节的prt()也是可以的，星马想稍稍讲讲enumerate的用法）
首先先判断有没有解，直接看sol_num是否为零即可。
如果有解，就考虑如何从result中输出解。
在使用enumerate前，最重要的事就是确定迭代对象的结构是什么样的，即result是如何存储解的状态的？
还记得result是如何来的吗？我们直接将board的全部状态装载进去了。
result.append(board[:])
其结构就是由board[]构成的解空间。
result = [[1, 3, 0, 2], # 解法 1[2, 0, 3, 1] # 解法 2
]接下来，我们的输出要求也是“解法X：解的结构”。
而result的存储格式正好是“解法：解的结构”的键值对结构！
enumerate迭代器用于在遍历容器时同时获取元素的索引和值，也就是说他能同时返回我们想要的东西。
语法为：
for index, value in enumerate(iterable, start=0):index是索引键，value是对应值，我们分别取idx和sol。
后面的逻辑和皇后问题一样，先初始化 输出行 为“...........”，从对应解取对应存放Q的位置，更改为'Q'
for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()完整代码：
# 输出结果
if sol_num == 0:print("无解")
else:for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()print(f"共找到 {sol_num} 种解法。")至此，所有核心代码结束，接下来的任务就是装在一起就好啦~
我们将回溯函数、约束条件函数和执行逻辑全部封装在solve_n_queens_with_given_board这个函数中，由于我们要获取输入n和残局情况initial_board，因此要作为参数传入。
def solve_n_queens_with_given_board(n, initial_board):def is_valid(board, row, col):#约束条件判断def spin(row):#回溯函数#################################################################
调用solve_n_queens_with_given_board()后从这里开始执行，前面是函数声明# 初始化board = [-1] * n # 初始化当前棋盘状态（-1 表示未放置皇后）result = [] # 存储所有解sol_num = 0# 解析初始棋盘for r in range(n):# 检查初始棋盘是否有冲突for r in range(n):# 开始回溯spin(0)# 输出结果if sol_num == 0:无解else:输出解# 示例调用
if __name__ == "__main__":n = int(input("请输入棋盘大小 n："))print("请输入初始棋盘状态（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)] # 接收一维数组solve_n_queens_with_given_board(n, initial_board)完整代码：
def solve_n_queens_with_given_board(n, initial_board):def is_valid(board, row, col):"""检查当前位置 (row, col) 是否有效"""for i in range(row): # 检查当前行之前的行if board[i] == col or abs(i - row) == abs(board[i] - col):return Falsereturn Truedef spin(row):"""回溯函数"""nonlocal sol_numif row == n: # 如果所有行都放置了皇后result.append(board[:])sol_num += 1returnif initial_board[row] != -1: # 如果当前行已经有固定的皇后if is_valid(board, row, initial_board[row]): # 检查是否冲突board[row] = initial_board[row]spin(row + 1)board[row] = -1else: # 如果冲突，则无解returnelse: # 如果当前行没有固定的皇后for col in range(n):if is_valid(board, row, col): # 剪枝：只有有效位置才继续board[row] = col # 放置皇后spin(row + 1) # 递归处理下一行board[row] = -1 # 回溯，撤销放置# 初始化board = [-1] * n # 当前棋盘状态（-1 表示未放置皇后）result = [] # 存储所有解sol_num = 0# 解析初始棋盘for r in range(n):try:c = initial_board[r].index('Q') # 找到 'Q' 的列索引board[r] = c # 固定该位置except ValueError:pass # 如果该行没有 'Q'，跳过# 检查初始棋盘是否有冲突for r in range(n):if board[r] != -1: # 如果当前行有固定皇后if not is_valid(board, r, board[r]):print("无解")return# 开始回溯spin(0)# 输出结果if sol_num == 0:print("无解")else:for idx, sol in enumerate(result):print(f"解法 {idx + 1}:")for r in range(n):line = ['.'] * nline[sol[r]] = 'Q'print(' '.join(line))print()print(f"共找到 {sol_num} 种解法。")# 示例调用
if __name__ == "__main__":n = int(input("请输入棋盘大小 n："))print("请输入初始棋盘状态（'Q' 表示皇后，'.' 表示空位）：")initial_board = [input().strip() for _ in range(n)] # 接收一维数组solve_n_queens_with_given_board(n, initial_board)小结：
残局问题就是提前固定了几个皇后，只要合理解决冲突就能简单找到答案。本节还是希望诸位能体会回溯函数的变体和处理范式。
Ⅰ 剪枝就是提前终止，分为 可行 最优 启发 对称剪枝。
Ⅱ 一般对称剪枝只处理第一行，因为深层剪枝会破坏对称性。动态剪枝的开销反而更大。
Ⅲ 接收二维数组可以用一维字符串数组：[input().strip() for _ in range(n)]，n为接收批次数。
Ⅳ 从字符串找某字符索引用index('X')
Ⅴ Enumerate的用法：
① 确定存储对象的结构。
② 根据for 索引, 对应值 in enumerate(result):获取键值对。
写在后面：
很开心你能耐着性子读到这里，很荣幸能将我的三脚猫知识分享给大家。
星马也是小白，因此更懂小白的心思，大佬认为一眼明白的代码和思路可能在我们眼中就是鸿沟。这篇文章也还有很多不足之处，或是纰漏，希望你发现了及时在评论区提醒我呀~
（人工智能学院就是每周四五天满课的啦，因此更新基本随缘~）
星马是刚入门的大菜比，有错望指正，有项目可以带带我