The question is close to the [Sokoban][1] 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.
**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 ?
[1]: http://en.wikipedia.org/wiki/Sokoban