Return to Answer

The better analogy when the markers are distinct is not Sokoban, but the 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. ADDITION: At the end there is a remark about the application to the directed case. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general biconnected $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) extended these results to the case when fewer vertices are occupied and to more general graphs, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper. Anyway, Röger and Helmert recommend to find more details in the tech-report, which contains Daniel Kornhauser's Master's theses. Let me mention that I don't believe the $\Omega(n^3)$ lower bound proof given there, Theorem 5 on p.42. This is just too close to bubblesort.)

For directed graphs which are biconnected and strongly connected, one can apply the characterizations of the undirected graph case, because a "backward move" can always be simulated: Let $ab$ be an arc and suppose we would like to move a pebble $X$ from $b$ to $a$. Find a directed cycle through $ab$ and push the vertices on this cycle through, but don't make the last move of pebble $X$ from $a$ to $b$. This realizes a backward move by $O(n^2)$ forward moves. This yields a linear-time decision algorithm and an $O(n^5)$ upper bound on the number of moves (when a solution exists) for this digraph class.

The better analogy when the markers are distinct is not Sokoban, but the 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. ADDITION: At the end there is a remark about the application to the directed case. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general biconnected $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) extended these results to the case when fewer vertices are occupied and to more general graphs, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper. Anyway, Röger and Helmert recommend to find more details in the tech-report, which contains Daniel Kornhauser's Master's theses.)

For directed graphs which are biconnected and strongly connected, one can apply the characterizations of the undirected graph case, because a "backward move" can always be simulated: Let $ab$ be an arc and suppose we would like to move a pebble $X$ from $b$ to $a$. Find a directed cycle through $ab$ and push the vertices on this cycle through, but don't make the last move of pebble $X$ from $a$ to $b$. This realizes a backward move by $O(n^2)$ forward moves. This yields a linear-time decision algorithm and an $O(n^5)$ upper bound on the number of moves (when a solution exists) for this digraph class.

The better analogy when the markers are distinct is not Sokoban, but the well-known 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) have extended these results to the case when fewer vertices are occupied, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper.)

The better analogy when the markers are distinct is not Sokoban, but the 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. ADDITION: At the end there is a remark about the application to the directed case. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general biconnected $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) extended these results to the case when fewer vertices are occupied and to more general graphs, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper. Anyway, Röger and Helmert recommend to find more details in the tech-report, which contains Daniel Kornhauser's Master's theses. Let me mention that I don't believe the $\Omega(n^3)$ lower bound proof given there, Theorem 5 on p.42. This is just too close to bubblesort.)

For directed graphs which are biconnected and strongly connected, one can apply the characterizations of the undirected graph case, because a "backward move" can always be simulated: Let $ab$ be an arc and suppose we would like to move a pebble $X$ from $b$ to $a$. Find a directed cycle through $ab$ and push the vertices on this cycle through, but don't make the last move of pebble $X$ from $a$ to $b$. This realizes a backward move by $O(n^2)$ forward moves. This yields a linear-time decision algorithm and an $O(n^5)$ upper bound on the number of moves (when a solution exists) for this digraph class.

The better analogy when the markers are distinct is not Sokoban, but the well-known 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on an $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) have extended these results to the case when fewer vertices are occupied, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper.)

The better analogy when the markers are distinct is not Sokoban, but the well-known 15-puzzle. It is even on an undirected graph.

All my remarks below are about the undirected version. (My brief literature search turn up only one paper with directed graphs, for a single pebble (robot) with obstacles whose final position is irrelevant.) The upshot is:

On undirected graphs, the decision version ("Does a solution exist?") is solvable in polynomial time, but minimizing the number of moves is NP-hard.

There is a short paper by Oded Goldreich, dating back to 1984 but published only in 2011, "Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard". Ratner and Warmuth showed (Journal of Symbolic Computation, 1990) that this is true even for the extension of the 15-puzzle to larger squares.

Richard Wilson has characterized in 1974 the cases when a solution is possible, in the case when there are $n-1$ tokens on a general $n$-vertex graph, like in the 15-puzzle. According to a recent paper by Gabriele Röger and Malte Helmert, Kornhauser, Miller, and Spirakis ("Coordinating pebble motion on graphs, the diameter of permutation groups, and applications", 1984) have extended these results to the case when fewer vertices are occupied, and showed that there is a solution with $O(n^3)$ moves if there is a solution at all. (I haven't looked at this paper.)