本文详细讲解了使用 Python 实现棋盘游戏暴力求解算法的过程。通过构建状态树和回溯机制，程序能够枚举所有可能的走法并找到完成游戏的解法。内容涵盖基本操作定义、主函数逻辑、代码实现细节以及算法复杂度分析，帮助读者理解回溯算法在组合搜索问题中的应用。
在之前的章节中，我们已经完成了对棋盘状态的建模工作。接下来是暴力求解程序的核心部分，即枚举算法的实现。本部分将详细讲解如何通过代码构建搜索树，并利用回溯机制找到游戏的解法。
要让程序能够尝试每一种可能的走法，需要设计一种高效的枚举算法。当第一颗棋子落定后，第二步对应的几种走法又各自对应若干种第三步的走法。因此，固定第一颗棋子，则在这个棋盘上，所有走法构成了一棵树。
考虑到对称性，第一颗棋子的位置有 16 个选择，但通过对称关系可以略去重复项，只剩 4 个特异的起点。因此，整个游戏的所有走法可以用一个含 4 棵树的森林来表示。而枚举算法的目的则是试图在所有叶子结点中找到完成游戏的那几个结点。
接下来，我们让算法从根结点开始，逐步探索、完善这棵树。这种策略本质上是一种深度优先搜索（DFS）配合回溯（Backtracking）的方法。
为了表示棋盘状态（哪些格子为空，哪些格子有棋子），我们定义两个列表：
NodesOccupied：占用列表，记录当前已被棋子占据的节点。NodesUnoccupied：未占用列表，记录当前空闲的节点。初始化代码如下：
from itertools import combinations
# 全局状态变量
NodesOccupied = []
NodesUnoccupied = list(range(15))
solution = []
safe_stack = []
该函数输入为棋子序号 n，遍历 NodesUnoccupied，得到该棋子所有的合法走法，即下一步占用哪两个格子。
def getRoads(n):
# 生成所有可能的两两组合
options_all = list(combinations(NodesUnoccupied, 2))
options = []
for option in options_all:
# 检查是否在同一行且符合移动规则（例如只能向相邻空位移动）
# 注意：isSameRow 的具体逻辑取决于棋盘几何结构定义
if isSameRow(n, option[0], option[1]) and \
((n < option[0] and n < option[1]) or (n > option[0] and n > option[1])):
options.append(option)
return options
输入为 (n, n1, n2)，分别为棋子序号 n、接下来要占用的两个位置 n1 和 n2。该操作用于更新 NodesOccupied 和 NodesUnoccupied，并记录该走法，用于最后程序输出。
def action(n, n1, n2):
global NodesOccupied, NodesUnoccupied, solution
# 更新占用状态
NodesOccupied += [n1, n2]
if n in NodesOccupied:
NodesOccupied.remove(n)
# 更新未占用状态
if n not in NodesUnoccupied:
NodesUnoccupied.append(n)
if n1 in NodesUnoccupied:
NodesUnoccupied.remove(n1)
if n2 in NodesUnoccupied:
NodesUnoccupied.remove(n2)
# 记录路径
temp_unoccupied = NodesUnoccupied[:]
solution.append([[n, n1, n2], temp_unoccupied])
如果程序发现不能再往下走了，即运行到叶子结点，而此时又没有达到完成游戏的条件，则说明这条路不正确。这时，需要回退到上一个做选择的位置。回退机制依赖于安全状态栈 safe_stack 来完成。
def get_back():
global NodesOccupied, NodesUnoccupied, solution
# 恢复之前的状态
prev_state = safe_stack[-1][0]
NodesOccupied = prev_state[:]
# 重新计算未占用列表
NodesUnoccupied = []
for i in range(15):
if i not in NodesOccupied:
NodesUnoccupied.append(i)
# 弹出错误的路径记录
if solution:
solution.pop()
主函数的逻辑相对清晰，依赖安全状态栈不断循环，直到棋盘中只剩一个空格时退出循环。程序会尝试四种不同的起始点，分别执行四次搜索。
def main():
global NodesOccupied, NodesUnoccupied, solution, safe_stack
# 重置全局状态
NodesOccupied = []
NodesUnoccupied = list(range(15))
solution = []
safe_stack = []
# 一共有四棵树，简单起见直接分四次执行
startPoints = [0, 1, 3, 4]
for startPoint in startPoints:
# 初始化起始状态
NodesOccupied = [startPoint]
NodesUnoccupied = list(range(15))
NodesUnoccupied.remove(startPoint)
solution = []
safe_stack = []
isAction = True
# 循环直到只剩一个空格
while len(NodesUnoccupied) > 1:
if isAction:
# 保存当前状态到栈中
temp_Occupied = NodesOccupied[:]
safe_stack.append([temp_Occupied, []])
# 收集当前所有可能的走法
for node in temp_Occupied:
options = getRoads(node)
for option in options:
safe_stack[-1][1].append([node] + list(option))
# 尝试执行第一步
if len(safe_stack[-1][1]):
move = safe_stack[-1][1][0]
action(move[0], move[1], move[2])
isAction = True
else:
# 无路可走，回退
if len(safe_stack) > 1:
safe_stack.pop()
safe_stack[-1][1].pop(0)
get_back()
isAction = False
else:
print('Fail.')
break
if len(NodesUnoccupied) == 1:
print('Success.')
for each in solution:
print(f'remove {each[0][0]}, append {each[0][1:]}, Unoccupied: {each[1]}')
break
else:
print(f'Failed to find solution starting at {startPoint}')
运行上述程序后，它会将自己摸索出来的第一种解法打印出来。示例输出如下：
Success.
remove 0, append [1, 3], Unoccupied: [2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0]
remove 1, append [4, 8], Unoccupied: [2, 5, 6, 7, 9, 10, 11, 12, 13, 14, 0, 1]
...
其中 remove 0, append [1, 3] 就表示移动编号为 0 的棋子，占用 1 和 3 号位置。Unoccupied 列表显示当前还有哪些格子没有被占。按照程序给出的攻略，最终只剩一个空格，游戏完成。
由于采用了暴力枚举，该算法的时间复杂度主要取决于搜索树的大小。在最坏情况下，每一步都有多个分支，导致指数级增长。对于 15 个节点的棋盘，虽然节点数不多，但组合数量依然庞大。
空间复杂度主要由递归栈或显式栈的深度决定，以及存储解法的列表大小。在本例中，最大深度约为 14 层（每步减少一个空格）。
本文详细介绍了使用 Python 实现棋盘游戏暴力求解算法的过程。通过构建状态树和回溯机制，程序能够枚举所有可能的走法并找到完成游戏的解法。内容涵盖基本操作定义、主函数逻辑、代码实现细节以及算法复杂度分析，帮助读者理解回溯算法在组合搜索问题中的应用。在实际开发中，建议根据具体场景引入剪枝或启发式策略以提升效率。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online