Python 实现棋盘游戏暴力求解算法：回溯与枚举详解

2. 执行某一种走法

输入为 (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])

3. 回退机制

如果程序发现不能再往下走了，即运行到叶子结点，而此时又没有达到完成游戏的条件，则说明这条路不正确。这时，需要回退到上一个做选择的位置。回退机制依赖于安全状态栈 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 层（每步减少一个空格）。

优化建议

1. 剪枝策略：在搜索过程中，如果发现当前状态无法到达目标（例如剩余空格不连通），可以提前终止该分支。
2. 记忆化搜索：如果存在重复的状态，可以使用哈希表记录已访问的状态，避免重复计算。
3. 启发式搜索：引入估价函数，优先搜索更有可能通向解法的分支（如 A*算法）。

总结

本文详细介绍了使用 Python 实现棋盘游戏暴力求解算法的过程。通过构建状态树和回溯机制，程序能够枚举所有可能的走法并找到完成游戏的解法。内容涵盖基本操作定义、主函数逻辑、代码实现细节以及算法复杂度分析，帮助读者理解回溯算法在组合搜索问题中的应用。在实际开发中，建议根据具体场景引入剪枝或启发式策略以提升效率。