## Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

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 ?

-
 it's not clear what are moves allowed. Are you moving the 'init_j' vertices at the same time? By the way, "wave algorithm" seems to be what is called "breadth-first search" in English. – Dima Pasechnik Feb 15 at 7:56 One "MOVE" - moves ONLY ONE marker. Is the description clear now ? @Dima Thank you for you comment ! – Alexander Chervov Feb 15 at 8:02 IMHO it's better to formulate this in terms of $m$ chips placed on nodes of your digraph $G$, at most one chip on a node, and each move in this game, with the goal is to place chips on a fixed subset of "final" nodes, is to move a chip on a node $v$ to the other end $u$ of an arc $vu$, without violating the condition that there is at most one chip on a node. – Dima Pasechnik Feb 15 at 8:26 It seems to be a computationally hard problem, in the sense that every algorithm will need time exponential in $m$. – Dima Pasechnik Feb 15 at 8:30 @Dima do you mean the name "chip" is better than "marker" ? (по русски "фишки" стоят в вершинах - what should be translation of "фишка" ? "chip" ? – Alexander Chervov Feb 15 at 8:32

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.
-
how are you going to do 1) in polytime? – Dima Pasechnik Feb 16 at 2:34
@Dima: ignore the first sentence of step 1. It is step 2 which actually finds which chip goes where. Step 1 just finds candidate places for each chip. – Andrej Bauer Feb 16 at 7:53
Thank you very much for your answer ! What do think about the case wit NON-identical chips ? It seems Step 3 heavily relies on "identity". – Alexander Chervov Feb 16 at 10:11
Right, I gave up too quickly. Now, at least I know why these motion planning problems on graphs need a "pusher" to make them hard! – Dima Pasechnik Feb 16 at 11:44

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.

-

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.

-
I don't think so. In Sokoban, you cannot freely move any chip as you like (as in the Question). You must go there and push from a free square on the opposite side. In the Question, the only constraint is that the chips cover distinct positions. (I am not sure if the question is polynomially solvable.) – Günter Rote Feb 15 at 19:38
It might also be worth looking for a connection to sandpile models on digraphs, which also involve the movement of chips from node to node. – Sam Hopkins Feb 15 at 20:46
I'll blame my wife - I never played Sokoban myself ;) – Dima Pasechnik Feb 16 at 2:37
Thank you very much for your answer ! It is wonderful to know relation with Sokaban ! Still there are some differences 1) Gunter Rote mentioned 2) It implies (but not equivalent) that at least graph for Sokoban should be directed - cause boxes in the corners cannot be pushed (as far as I understand - I also never played it) 3) In Sokoban it seems chips are identical while in my question they are "marked". – Alexander Chervov Feb 16 at 10:08
SOKOBAN is even PSPACE-complete, see J. Culberson, in: Proc. Int. Conf. on FUN with Algorithms, pp. 76-74, 1999) webdocs.cs.ualberta.ca/~joe/Preprints/Sokoban/… – Günter Rote Feb 19 at 22:09
show 1 more comment

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).

-
 Thank you for your answer ! Let me mention that what I describe in "Example of algorithm" is based on similar idea - create a "big-new-graph" and reduce the problem to existence of the path between two vertices in the "big-new-graph". What seems to be quite interesting to understand - how specific are these "Sokoban-graphs" ? Can we say in advance that it is better to use deepth-search instead of breadth-search algorithms ? – Alexander Chervov Feb 17 at 12:17 A "given concrete Sokoban problem" can be always be solved in constant time. To meaningfully speak of polynomial time requires a problem with some inputs, some parameters, with an infinite family of instances. – Günter Rote Feb 17 at 13:23 Parameters are $k$ and the numbers of vertices and edges of the initial graph. – Roland Bacher Feb 18 at 9:49

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.

-
 Thank you very much ! – Alexander Chervov Feb 20 at 7:55