Return to Answer

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions:
2. Set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the chips).
3. Find a perfect matching. If there is none, abort.
4. The matching gives a 1-1 assignment between initial and final positions.
5. Now we realize these movements one by one. Say, we want to move the chip $A$ from Init$_i$ to Final$_j$. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path, and it also works when all positions up to the target position Final$_j$ are occupied by chips.

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions:
2. Set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the chips).
3. If some Init$_i$ and some Final$_j$ coincide, it means that that some chip can be regarded as lying already on its target position. We take such pairs of vertices out of the graph.
4. Find a perfect matching. If there is none, abort. The problem has no solution.
5. The matching gives a 1-1 assignment between initial and final positions.
6. Now we realize these movements one by one. Say, we want to move chip $A$ from Init$_i$ to Final$_j$, which is not occupied. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path.

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions. Namely, set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the other chips).
2. Find a perfect matching. If there is none, abort.
3. Now we realize the movements one by one. Say, we want to move the chip $A$ from Init$_i$ to Final$_j$. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, start move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path, and it also works when all positions up to the target position Final$_j$ are occupied by chips.

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions:
2. Set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the chips).
3. Find a perfect matching. If there is none, abort.
4. The matching gives a 1-1 assignment between initial and final positions.
5. Now we realize these movements one by one. Say, we want to move the chip $A$ from Init$_i$ to Final$_j$. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path, and it also works when all positions up to the target position Final$_j$ are occupied by chips.

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions. Set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the other chips).
2. Find a perfect matching matching. If there is none, abort.
3. Now we realize the movements one by one. Say, we want to move the chip $A$ from Init$_i$ to Final$_j$. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, start move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path, and it also works when all positions up to the target position Final$_j$ are occupied by chips.

Here is a polynomial-time algorithm. I assume that the chips are identical, as in Dima's reformulation and in Sokoban. (Another version would be that the chip from Init$_i$ has to go to Final$_i$, for every $i$.)

1. Find out which chips should go to which target positions. Namely, set up a bipartite graph, with an arc from Init$_i$ to Final$_j$ if Final$_j$ is reachable from Init$_i$ in the graph (ignoring the other chips).
2. Find a perfect matching. If there is none, abort.
3. Now we realize the movements one by one. Say, we want to move the chip $A$ from Init$_i$ to Final$_j$. Find any path from Init$_i$ to Final$_j$ in the graph (ignoring the other chips). Try to push the chip along this path. It may happen that some other chip $B$ blocks the path. In this case, start move $B$ one step along the path, and then let $A$ take the previous place of $B$. Since the chips are identical, the effect is the same as if $A$ had jumped over $B$. The same trick can "jump" over several adjacent chips that block the path, and it also works when all positions up to the target position Final$_j$ are occupied by chips.