[Math] Algorithm to solve Sokoban-like game on graphs – move chips from one set of vertices to another

Question

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details.

Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, chipe2,…, chipM). Put chips on some set of vertices 'Init1','Init2','Init3'…
And consider some other set of vertices 'Final1','Final2',…, 'FinalM'.

Question Propose an "efficient" algorithm which will determine is it possible to "MOVE" chips from positions "InitNN" to positions 'FinalNN'.

Where we are allowed to "MOVE" chip from a vertex to an outgoing edge and from incoming edge to corresponding vertex.
With the CONSTRAINT that two chips are NOT allowed to be at the same place.
One move – moves only ONE chip.
ChipK should go to position FinalK – same "K".

Question There can be many approaches to solve the problem, I am interested
in analysis their complexity. Any ideas are welcome. For example if graph is "random" in certain sense what can be the algorithm the least average complexity ?

Where complexity is counted in number of operations (write a C-code (I actually wrote a Matlab code), compile to and calculate the number of cycles – this is well-defined complexity measure, different compilers and CPU will give approximately same result).

Example of algorithm It seems the simplest way to solve a problem is the following.
Essentially it can be reduced to determining where two vertices are connected in some bigger graph, which in turn can be solved by "breadth-first search" ("wave algorithm" in Russian) (I mean let us enumerate all
possible chip configurations – it will give vertices of the "new graph". Let us connect two vertices (configurations) if there is a "MOVE" which goes form one to another.)
By "breadth-first search" ("wave algorithm" in Russian) I mean the following – take an initial vertex and find all connected to it; next step find all vertices connected to vertices found on the previous step; and so on….

Question What about efficiency of this algorithm ? Can one propose better ?

Answer 1

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:
   1. 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).
   2. 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.
   3. Find a perfect matching. If there is none, abort. The problem has no solution.
   4. The matching gives a 1-1 assignment between initial and final positions.
2. 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.