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

Question

I have 8 rows x 7 columns grid. There are 2 players and each player controls 5 colored blocks and 1 colored ball. Different player have different colored blocks and ball (i.e. player 0 has white colored blocks and white ball, player 1 has black colored blocks and black ball). Each square in the board is represented in integer, the most bottom row of the board are 0-6 from left to right, a row above it are 7-13 from left to right, the pattern continues like that until the most upper row of the board with 49-55 from left to right. The block pieces move like a knight in chess. A player’s ball can move from the block piece holding it to a block piece of the same color along vertical, horizontal, or diagonal channels (same as a queen in chess). In a single turn, a player may pass their ball between same color block pieces an unlimited number of times. This is what the grid looks like:

If I want to move white block from 1 to 23, this is the sequence move:

[(((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) : index 0-4 are white blocks initial position, index 5 is white ball initial position, index 6-10 are black blocks initial position, index 11 is black ball initial position.
• 0 or 1 in each of the sequence indicates player 0 turn or player 1 turn. Player 0 always start first and after that it's player 1 turns and so on and so forth. Each player must move either a block or a ball during each turn.
• (0,14), (11, 51), etc. : we move index 0 to position 14, we move index 11 to position 51, etc.
• If we have reached our goal (i.e. move white block from 1 to 23), but there are other pieces that is not mentioned in our goal and are not in it's initial position, we should put them back to it's initial position. In this case, we have to put the black ball back from 51 to 52. (e.g. previously we move the black ball from 52 to 51 because we have to move since it is player 1 turns, you can choose any piece you want to move, for this example, I choose to move the ball).
• None : we do nothing because we have reached our goal and all other pieces that are not mention in our goal are also in it's initial position.

The white ball from 3 can be at 22 in only one turn, because it can move from 3 to 1 and then from 1 to 22 (i.e. following the rule of ball movement in a single turn).

I have created a search function like this:

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

But when I test it using this:

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))

The output only shows part of the expected result:

[(((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))]

It still miss this part:

[(((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)]

What should I fix with my code so it can shows the complete sequences?

Answer 1

Turns out I need to restore the sequence in order to make the final sequence completed (i.e. this includes handling more than 1 goal task). So I add this function to help the existing search function:

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