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

问：

我有 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)]

我应该用我的代码修复什么，以便它可以显示完整的序列？

Python 搜索逻辑序列规划

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

上一个：如何在坐标列表中找到起点和终点？

下一个：为什么我的 PDI 可以访问其他数据库对象时无法访问 Oracle 序列？

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

How to generate move sequences from initial state to goal state in python?

评论