This month's problem is to determine the longest possible solution (measured in single steps to a adjacent square) to a Sokoban problem having n squares. Let L(n) be the largest number of moves that a Sokoban problem with n squares requires to solve. What are the values of L(n) for small n? How does the function L(n) behave for large n?

Philippe Fondanaiche showed that L(20n+1) ≥ 24n²+37n–4. This gives L(n)/n² ≥ 3/50.

I can prove for large enough n, that L(3n+4) ≥ 3n²/2+18n+4. The proof is by constructing a tower (like below for 14 spaces) of height n using n/2 + 2 bags. This gives L(n)/n² ≥ 1/3.

Trevor Green has proved that L(4n) ≥ n(7n–11), which for large n gives a better lower bound. The proof is by constructing long rooms of height 2 (like below for 12 spaces). For large n, the man starts on the right hand side instead of the left hand side. This gives L(n)/n² ≥ 7/16.

John Hoffman showed that L(2n+1) ≤ (2n+1) (2n)! /(n!)², since this is the maximum number of possible positions with one man and 2n+1 squares.

Hoffman also gave the best known lower bound: L(n) ≥ 2^n/74, proving his long-standing suspicion that L(n) grows exponentially. To do so, he modified some constructions from the paper Sokoban is PSPACE-complete.

In particular, he repeats the following room in which the man can only enter from the top right, go through a one-way device, go up to move the leftmost bag one square left, and then leave through the bottom through another one-way device. This allows the man to go from top right to top left the next time through. (If the man leaves at the top left the first time through, the bags in middle are stuck in the wrong places.) Then he has one bag that needs to pushed onto the correct spot accessible only from the leftmost top left exit. If you put n of the rooms together, you need to go through the rooms 2ⁿ times.

Here are the best known lower bounds for small numbers of spaces:

And here are the longest known Sokoban positions with a fixed number of spaces:

3 spaces, 1 move	4 spaces, 2 moves	5 spaces, 3 moves
6 spaces, 5 moves	7 spaces, 9 moves	8 spaces, 14 moves
9 spaces, 17 moves	10 spaces, 22 moves	11 spaces, 26 moves (Zachary DeStefano)
12 spaces, 35 moves	13 spaces, 40 moves

Trevor Green also considered P(n), the largest number of pushes necessary to solve a Sokoban level with n spaces. He wonders whether the same levels that maximize L(n) would maximize P(n), for large enough n. My guess is no. The same construction as above shows that P(4n) ≥ (n–1)(2n–1).

In 2021, Zachary DeStefano extended and improved these results. His site can be found here.

8 spaces, 11 moves	9 spaces, 15 moves	10 spaces, 18 moves
11 spaces, 21 moves	12 spaces, 25 moves	13 spaces, 28 moves

Brendan Owen also programmed Sokoban on a hexagonal board with one bag:

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 10/24/12.