如何在Python中生成从初始状态到目标状态的移动序列？

Question

我有 8 行 x 7 列的网格。有 2 名玩家，每名玩家控制 5 个彩色块和 1 个彩色球。不同的玩家有不同颜色的块和球（即玩家 0 有白色块和白球，玩家 1 有黑色块和黑球）。棋盘上的每个方格都用整数表示，棋盘最下面一行从左到右是0-6，上面一行从左到右是7-13，如此下去，直到最上面一行董事会从左到右为49-55。方块的移动就像国际象棋中的骑士一样。玩家的球可以沿着垂直、水平或对角线通道从容纳它的块移动到相同颜色的块（与国际象棋中的皇后相同）。在一个回合中，玩家可以在相同颜色的块之间传递球，次数不受限制。这就是网格的样子：

如果我想将白块从 1 移动到 23，这是顺序移动：

[(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), (0, 14)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 1), (11, 51)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 51), 0), (0, 23)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 51), 1), (11, 52)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]

• (1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52) ：索引0-4是白块初始位置，索引5是白球初始位置，索引6-10是黑球初始位置，索引11为黑球初始位置。
每个序列中的 0 或 1 表示玩家 0 回合或玩家 1 回合。玩家 0 总是先开始，然后是玩家 1 轮流，依此类推。每个玩家在每个回合中必须移动一个方块或一个球。
(0,14)、(11, 51) 等：我们将索引 0 移动到位置 14，将索引 11 移动到位置 51，等等
如果我们已经达到了我们的目标（即将白块从 1 移动到 23），但是还有其他棋子没有在我们的目标中提到并且不在其初始位置，我们应该将它们放回其初始位置。在这种情况下，我们必须将黑球从 51 放回到 52。（例如，之前我们将黑球从 52 移动到 51，因为我们必须移动，因为这是玩家 1 回合，您可以选择任何您想要移动的棋子，对于这个例子，我选择移动球）。
无：我们什么也不做，因为我们已经达到了我们的目标，并且我们目标中未提及的所有其他部分也处于其初始位置。

从 3 开始的白球只需一回合即可到达 22，因为它可以从 3 移动到 1，然后从 1 移动到 22（即遵循单回合球移动的规则）。

我创建了一个这样的搜索功能：

def find_sequence(initial_state, end_state):    
    queue = deque([(initial_state, None, None, 0)])
    visited = set([initial_state])
    parents = {}    
    while queue:
        state, prev_state, move, player_turn = queue.popleft()    
        if state[:5] == end_state[:5] and state[5] == end_state[5]:            
            path = []
            while state is not None:
                path.append((state, player_turn, move))
                state, move, player_turn = parents.get(state, (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]
            return formatted_sequence        
        for next_state in get_next_states(state, player_turn):
            if next_state not in visited:
                visited.add(next_state)
                parents[next_state] = (state, (player_turn, find_move(state, next_state)), 1 - player_turn)
                queue.append((next_state, state, (player_turn, find_move(state, next_state)), 1 - player_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))

输出仅显示部分预期结果：

[(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), (0, 14)), 
(((14, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 1), (6, 37)), 
(((14, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 0), (0, 23))]

还缺这一部分：

[(((23, 2, 3, 4, 5, 3, 37, 51, 52, 53, 54, 52), 1), (6, 50)), 
(((23, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]

我应该对我的代码进行哪些修改才能显示完整的序列？

Answer 1

结果我需要恢复序列才能完成最终序列（即这包括处理超过 1 个目标任务）。所以我添加这个功能来帮助现有的搜索功能：

def find_sequence_with_restore(self):
        print(self.initial_board_state.state)
        print(self.goal_board_state.state)
        initial_state = tuple(self.initial_board_state.state)
        end_state = tuple(self.goal_board_state.state)   
        differences = sum(1 for a, b in zip(tuple(self.initial_board_state.state), tuple(self.goal_board_state.state)) if a != b)
        if differences < 2:
            sequence = self.find_sequence(initial_state, end_state)
            if sequence:
                final_state = sequence[-1][0][0]
                restore_sequence = self.restore_initial_positions(end_state, final_state, initial_state)
                sequence.extend(restore_sequence)
                if all(pos in initial_state or pos in end_state for pos in sequence[-1][0][0]):
                    sequence.append(((sequence[-1][0][0], 1 - sequence[-1][0][1]), None))
                else:
                    sequence.append(((sequence[-1][0][0], sequence[-1][0][1]), None))
            return sequence
        elif differences == 0:
            return [(((1, 2, 3, 4, 5, 3, 50, 51, 52, 53, 54, 52), 0), None)]
        else:
            return None