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.

Answer 2

Not an answer, but an improved version of the question:

Consider a directed graph $G=(V,A)$, and a subset $F\subset V$ of final nodes. Let $m=|F|$ and consider the following game: one is given a configuration of $m$ chips on $V$, with not more than one chip per node (or, more formally, an injective function $c:[1,2,\dots, m]\to V$), and the following moves are allowed:

• choose an arc $vu\in A$ with a chip on $v$ no chip on $u$;
• move the chip from $v$ onto $u$.

(i.e., with the formalism of functions, we modify $c$ so that $u$ enters $c^{-1}(V)$, and $v$ leaves $c^{-1}(V)$.)

The goal: cover $F$ with chips. (i.e., achieve $c([1,2,\dots, m])=F$).

Question: what is the complexity of deciding whether the goal can be reached.

Answer 3

Edit: Sokoban is a harder problem than this one!

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.

Answer 4

Not an answer but a reformulation of Sokoban in terms of oriented graphs: A Sokoban-problem of order $k$ on a finite directed graph with vertices $V$ and directed edges $E$ (with $(s,t)$ denoting an edge from $s$ to $t$) consists of two (perhaps intersecting) subsets $V_I,V_F$ of $k$ vertices (defining initial and final positions of the $k$ boxes), of a marked vertex $*$ of $V\setminus V_I$ and of a set $P=\cup_{e\in E}P_e$ of "possible pushes" where $P_e$ is a subset of edges starting at the final vertex $t$ of the oriented edge $e=(s,t)$.

A Sokoban-problem is solved if $V_F=V_I$.

A move consists either by a choice of a new marked vertex $*'\in V\setminus V_I$ adjacent to $*$ by an edge $(*,*')$ or by a choice of a new marked vertex $*'\in V_i$ adjacent to $*$ by an edge $(*,*')$ together with a new set $V'_I$ of initial vertices of the form $V'_I=(V_I\setminus\lbrace *'\rbrace)\cup \lbrace v\rbrace$ with $v\in V\setminus V_I$ such that $(*',v)$ is an element of the set $P_{(*,*')}$ of possible pushes associated to the oriented edge $(*,*')$. (The sets $V_F$ of final positions and $P$ of possible pushes remain the same.)

The Sokoban-graph $(V,E,V_F,P)$ with possible moves $P$ and $k$ final positions $V_F$ is the directed graph with vertices given by all ${\sharp(V)\choose k}(\sharp(V)-k)$ possible choices of $k$ initial vertices $V_I$ and of a marked vertex $*$ in $V\setminus V_I$. Moves define oriented edges of the Sokoban-graph. A solution of a Sokoban problem $(V,E,V_I,V_F,*,P)$ is a path in the Sokoban-graph $(V,E,V_F,P)$ starting at the vertex $(V,E,V_I,V_F,*,P)$ and ending at one of the $(\sharp(V)-k)$ solutions $(V,E,V_F,V_I=V_F,*,P)$ (with $*\in V\setminus V_F$).

The Sokoban graph $(V,E,V_F,P)$ has thus $<\sharp(V)^{k+1}$ vertices and it is of degree $\leq m^2$ where $m$ is the maximum over all in-degrees and out-degrees of $(V,E)$. I have the impression that this implies that a given concrete Sokoban problem can be solved in polynomial time (since $m\leq 4$ for Sokoban).

Answer 5

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.