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 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^{2} + 37*n  4. This gives L(n)/n^{2} ≥ 3/50.
I can prove for large enough n, that L(3n+4) ≥ 3n^{2}/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^{2} ≥ 1/3.
Trevor Green has proved that L(4n) ≥ n(7n11), 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^{2} ≥ 7/16.
John Hoffman showed that L(2n+1) ≤ (2n+1) (2n)! /(n!)^{2}, 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 longstanding suspicion that L(n) grows exponentially. To do so, he modified some constructions from the paper Sokoban is PSPACEcomplete.
In particular, he repeats the following room in which the man can only enter from the top right, go through a oneway device, go up to move the leftmost bag one square left, and then leave through the bottom through another oneway 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^{n} times.

Here are the best known lower bounds for small numbers of spaces:
n  3  4  5  6  7  8  9  10  11  12  13  14 

L(n)  1  2  3  5  9  14  17  22  26  35  40  48 
And here are the longest known Sokoban positions with a fixed number of spaces:

 

 

 

 

 


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) ≥ (n1)(2n1).
Brendan Owen wrote a computer program to calculate the best longest possible games for one bag. His results are below (the answers for 3 to 7 spaces are the same)
n  3  4  5  6  7  8  9  10  11  12  13 

L(n)  1  2  3  5  9  11  15  18  21  25  28 

 

 


Brendan Owen also programmed Sokoban on a hexagonal board with one bag:
n  3  4  5  6  7  8  9  10  11 

L(n)  1  2  4  7  9  13  15  18  20 
If you can extend any of these results, please email me. Click here to go back to Math Magic. Last updated 10/24/12.