回溯算法+对称剪枝——从八皇后问题到数独问题（二）

引入：

本节我们进一步完善八皇后问题，学习剪枝、八皇后残局问题 进一步领会逻辑编程的概念，深入体会回溯算法，回顾上一节提到的启发搜索策略。

回顾：

八皇后问题：我们需要在一个空棋盘上放置 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):获取键值对。

写在后面：

很开心你能耐着性子读到这里，很荣幸能将我的三脚猫知识分享给大家。

星马也是小白，因此更懂小白的心思，大佬认为一眼明白的代码和思路可能在我们眼中就是鸿沟。这篇文章也还有很多不足之处，或是纰漏，希望你发现了及时在评论区提醒我呀~

（人工智能学院就是每周四五天满课的啦，因此更新基本随缘~）

星马是刚入门的大菜比，有错望指正，有项目可以带带我