如何修复Python棋盘游戏状态搜索函数的序列缺失问题

核心问题分析 #

你的代码当前仅以白色方块和白球的位置匹配作为终止条件，导致搜索在目标方块到位后立即停止，无法覆盖非目标棋子归位的步骤。同时缺少最终的无操作步骤，不符合完整序列的要求。

修改步骤与完整代码 #

1. 关键修改点

• 严格终止条件：改为检查整个状态完全匹配目标状态，确保所有棋子（包括非目标的白色方块、黑色棋子）都归位。
• 优化访问记录：记录(状态, 当前回合玩家)的组合，避免同一状态在不同回合被误判为已访问，允许归位所需的状态循环。
• 添加无操作步骤：在生成的序列末尾补充无操作动作，满足完整序列要求。

修改后的完整代码

from collections import deque

def find_sequence(initial_state, end_state):    
    queue = deque([(initial_state, None, None, 0)])
    # 记录(状态, 当前回合玩家)，避免跨回合的状态误判
    visited = set([(initial_state, 0)])
    parents = {}    
    while queue:
        state, prev_state, move, player_turn = queue.popleft()    
        # 修改为完整状态匹配，确保所有棋子归位
        if state == end_state:            
            path = []
            while state is not None:
                path.append((state, player_turn, move))
                # 按(状态, 玩家回合)索引父节点
                state, move, player_turn = parents.get((state, player_turn), (None, None, None))
            sequence = list(reversed(path[1:]))
            sequence_without_turn = [(state, move) for state, _, move in sequence]
            formatted_sequence = [((state, move[0]), move[1]) for state, move in sequence_without_turn]
            # 添加最终无操作步骤，标记为(None, None)
            formatted_sequence.append(((end_state, None), None))
            return formatted_sequence        
        for next_state in get_next_states(state, player_turn):
            next_turn = 1 - player_turn
            if (next_state, next_turn) not in visited:
                visited.add((next_state, next_turn))
                # 父节点存储(状态, 玩家回合)的关联
                parents[(next_state, next_turn)] = (state, (player_turn, find_move(state, next_state)), player_turn)
                queue.append((next_state, state, (player_turn, find_move(state, next_state)), next_turn))    
    return None
        
def find_move(state1, state2):
    for i in range(len(state1)):
        if state1[i] != state2[i]:
            return (i, state2[i])
    return None

# 测试代码
initial_state = (1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52)
end_state = (23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52)
print(find_sequence(initial_state, end_state))

补充说明 #

• 请确保get_next_states函数能正确生成所有合法动作，包括：
  • 白色方块的马式移动
  • 白色球在己方方块间的无限传递
  • 黑色玩家的合法移动（若需考虑对方回合）
• 无操作步骤的标记((end_state, None), None)可根据你的规则调整为符合需求的格式。

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