CodeChef：3×3质数和相邻交换拼图游戏问题求解

嘿，这个问题挺有意思的——既帮Johnny巩固质数记忆，又是个典型的状态空间搜索问题！我来一步步拆解怎么解决它：

先理清规则与合法交换对 #

首先，咱们得明确游戏的核心限制：

• 只能交换有公共边的相邻格子（上下左右，斜着不算）
• 交换的两个数字之和必须是质数

这里有个小技巧帮Johnny（还有我们）快速判断：质数里除了2都是奇数，而奇数+偶数=奇数，奇数+奇数/偶数+偶数=偶数（大于2的偶数都不是质数）。所以只有「奇数+偶数」的组合才有可能满足和为质数的条件！

基于这个规律，我们可以提前列出1-9之间所有合法的交换对（双向的，比如1和2能换，2和1也能换）：

• 1（奇）可交换：2、4、6
• 3（奇）可交换：2、4、8
• 5（奇）可交换：2、6、8
• 7（奇）可交换：4、6
• 9（奇）可交换：2、4、8
• 偶数的可交换对象就是上面对应的奇数，比如2能和1、3、5、9交换

核心解法：广度优先搜索（BFS） #

要找到从初始状态到目标状态的最短路径（毕竟玩游戏肯定想最少步数完成），BFS是最合适的算法——它会按层遍历所有可能的状态，第一次到达目标状态时的路径就是最短的。

具体实现思路 #

1. 状态表示：把3×3棋盘转换成字符串（比如目标状态是"123456789"），这样既方便存储，又能快速判断是否重复访问。
2. 生成相邻状态：对当前状态的每个格子，检查它的上下左右邻居：
   • 取出当前格子和邻居的数字
   • 对照我们提前列好的合法交换对，判断能不能交换
   • 如果可以，交换后生成新的状态
3. 避免重复搜索：用一个集合记录已经处理过的状态，防止绕圈子死循环。
4. 记录路径：用队列存储路径的方式，记录每个状态的到达路径，最后直接返回完整步骤。

可运行的Python代码示例 #

from collections import deque

# 预定义所有合法的交换数字对（双向）
VALID_PAIRS = {
    (1,2), (2,1), (1,4), (4,1), (1,6), (6,1),
    (3,2), (2,3), (3,4), (4,3), (3,8), (8,3),
    (5,2), (2,5), (5,6), (6,5), (5,8), (8,5),
    (7,4), (4,7), (7,6), (6,7),
    (9,2), (2,9), (9,4), (4,9), (9,8), (8,9)
}

# 目标状态字符串
TARGET = "123456789"

def solve_puzzle(initial_state_str):
    # 把输入的空格分隔字符串转成连续字符串
    initial = initial_state_str.replace(" ", "")
    if initial == TARGET:
        return ["已经是目标状态啦！"]
    
    # BFS队列：每个元素是(当前状态字符串, 路径列表)
    queue = deque([(initial, [initial])])
    visited = set([initial])
    
    # 上下左右四个方向的偏移量（行，列）
    DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        current_state, path = queue.popleft()
        
        # 遍历每个格子的位置
        for idx in range(9):
            current_num = int(current_state[idx])
            row, col = idx // 3, idx % 3
            
            # 检查四个方向的邻居
            for dr, dc in DIRECTIONS:
                new_row, new_col = row + dr, col + dc
                # 判断邻居是否在棋盘范围内
                if 0 <= new_row < 3 and 0 <= new_col < 3:
                    neighbor_idx = new_row * 3 + new_col
                    neighbor_num = int(current_state[neighbor_idx])
                    
                    # 检查是否是合法交换对
                    if (current_num, neighbor_num) in VALID_PAIRS:
                        # 生成新状态
                        state_list = list(current_state)
                        state_list[idx], state_list[neighbor_idx] = state_list[neighbor_idx], state_list[idx]
                        new_state = "".join(state_list)
                        
                        # 找到目标状态，返回完整路径
                        if new_state == TARGET:
                            return path + [new_state]
                        
                        # 未访问过的状态加入队列
                        if new_state not in visited:
                            visited.add(new_state)
                            queue.append((new_state, path + [new_state]))
    
    # 遍历完所有可能都没找到，说明不可达
    return ["没有可行路径到达目标状态哦！"]

# 示例用法：输入初始状态，比如"2 1 3 4 5 6 7 8 9"
if __name__ == "__main__":
    initial = "2 1 3 4 5 6 7 8 9"
    solution_steps = solve_puzzle(initial)
    
    # 格式化输出每一步的棋盘
    for i, step in enumerate(solution_steps):
        print(f"第{i}步：")
        print(step[:3])
        print(step[3:6])
        print(step[6:])
        print("---")

额外提示 #

• 不可达状态：不是所有初始状态都能到达目标状态，比如某些状态的逆序数加上交换规则的限制，会导致无法连通。BFS会自动处理这种情况，返回不可达的提示。
• 帮Johnny记质数：让他记住上面列的奇偶数交换组合就行，不用每次算和是不是质数，玩多了自然就记住哪些组合的和是质数啦！

内容的提问来源于stack exchange，提问作者Rishi Sahu