最近使用Edge浏览器，目前有各种攒积分的任务，其中就有拼图游戏，就像这样：

玩过几次后我就思考有没有最优的解法，也就是步骤最少的复原方法。通过网上搜索，发现使用 A*（A-star）搜索算法 来找最短路径，是最常用的 8-puzzle 解法。

借助chatgpt，我这个编程入门选手也可以很快得到一个可执行的程序代码。

from heapq import heappush, heappop

# 目标状态
goal = "12345678_"

# 空格移动方向及其索引变化量
moves = {
    'U': -3,
    'D': 3,
    'L': -1,
    'R': 1,
}

# 特殊情况：哪些位置不能向左/右/上/下移动
invalid_moves = {
    'L': [0, 3, 6],
    'R': [2, 5, 8],
    'U': [0, 1, 2],
    'D': [6, 7, 8],
}

# 启发函数：曼哈顿距离
def manhattan(state):
    distance = 0
    for idx, val in enumerate(state):
        if val != "_":
            goal_idx = goal.index(val)
            distance += abs(idx // 3 - goal_idx // 3) + abs(idx % 3 - goal_idx % 3)
    return distance

# A* 求解函数
def solve_puzzle(start):
    visited = set()
    heap = []
    heappush(heap, (manhattan(start), 0, start, ""))  # (估值, 步数, 状态, 路径)

    while heap:
        priority, steps, state, path = heappop(heap)
        if state == goal:
            return steps, path

        if state in visited:
            continue
        visited.add(state)

        empty_idx = state.index("_")

        for move, delta in moves.items():
            new_idx = empty_idx + delta
            if empty_idx in invalid_moves[move] or not (0 <= new_idx < 9):
                continue
            # 交换空格与相邻数字
            state_list = list(state)
            state_list[empty_idx], state_list[new_idx] = state_list[new_idx], state_list[empty_idx]
            new_state = ''.join(state_list)
            if new_state not in visited:
                heappush(heap, (steps + 1 + manhattan(new_state), steps + 1, new_state, path + move))

    return -1, ""  # 无解

# 示例用法
if __name__ == "__main__":
    initial_state = "3754182_6"
    steps, solution = solve_puzzle(initial_state)
    print(f"最少步数: {steps}")
    print(f"操作路径: {solution}")

得到输出如下：

最少步数: 21
操作路径: ULDRUULDDRURULLDDRURD

🔁 操作说明（空格的移动方向）

每个字母代表一次点击使空格与相邻数字交换：