Skip to main content
2 of 3
fixed the 2nd reference
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

It is not hard to see that Sokoban is a particular case of this problem (the graphs arising in Sokoban are undirected and planar, of degree at most 4). Sokoban is known to be NP-complete. (thanks to my wife, who is a complexity theorist by training, and used to play Sokoban :-)).

Thus, in general, assuming that P is not equal to NP, any procedure to solve this problem will run in time exponential in $m$.

On the other hand, for any fixed $m$, this problem is solvable by repeated application of the shortest path algorithm, which need to iterate over all the possible assignments of chips in the initial configuration to the (ordered) elements of $F$ (i.e. the final nodes). If for no such an assignment the process of moving the chips completes, there is no solution. On the other hand, the procedure runs in polynomial time for $m$ fixed.

Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70