Note: I have posted a hugely expanded version of this question on cstheory.

Since a Sokoban instance with only $k$ boxes has at most $n^{O(k)}$ possible states, the problem lies in $\operatorname{NSPACE}$$[O(k \cdot \log (n))]$. Since the region

X    X
X  X  X
XX    X

has neither boxes nor storage locations and is such that a box can be pushed from the top to exit out the bottom but can't be pushed from the bottom to the top, the problem "Is there a matching from one given set of $k$ vertices to another given set of $k$ vertices in the transitive closure of the given directed grid graph?" can easily be reduced to the problem I am asking about.

Is anything else known about the complexity of Sokoban with only $k$ boxes?

In particular, is it the case that solvable instances always have solutions of length $n^{o(k)}$?

I tried to construct a bounded-counter gadget, but aside from realizing that such a gadget would require a box being moved along it when the counter's value is sufficiently large (since otherwise the player could just "pretend" to have incremented or decremented the counter), I wasn't able to get anywhere with that.

  • $\begingroup$ I didn't mean to sound that annoyed; I've toned down the intro (as you apparently noticed). $\:$ I personally like having spacing correspond somewhat with parsing, and otherwise in general making lines in the same paragraph have roughly the same lengths. $\;\;\;\;$ $\endgroup$
    – user12859
    Apr 9, 2015 at 21:25
  • 2
    $\begingroup$ I asked a question on Meta about formatting in general, see here. $\endgroup$
    – Juho
    Apr 9, 2015 at 21:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.