# Problem of the Month (March 2000)

The computer game Sokoban was invented in 1982 for Thinking Rabbit by Hiroyuki Imabayashi, and was immensely popular during the 1980's. In this game, a man walks around a square grid pushing bags of money to certain desired locations . The man cannot pull the bags, or push more than one bag at a time. For those of you who are unfamiliar with the game, download it here: OS/2, Windows, Macintosh.

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?

Using results for positions with only one bag (see below), Brendan Owen has shown that L(10+2n) ≥ 20+5n, and L(11+2n) ≥ 23+5n, where n > 0.

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

I can prove for large enough n, that L(3n+4) ≥ 3n2/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)/n2 ≥ 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)/n2 ≥ 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) ≥ 2n/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 2n times.

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

Length of Longest Sokoban Game with n Spaces
 n L(n) 3 4 5 6 7 8 9 10 11 12 13 14 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:

 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

 12 spaces, 35 moves

 13 spaces, 40 moves

 14 spaces, 49 moves (Trevor Green)

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

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)

Length of Longest Sokoban Game with n Spaces and 1 Bag
 n L(n) 3 4 5 6 7 8 9 10 11 12 13 1 2 3 5 9 11 15 18 21 25 28

 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:

Length of Longest Sokoban Game with
n Spaces and 1 Bag on a Hexagonal Board
 n L(n) 3 4 5 6 7 8 9 10 11 1 2 4 7 9 13 15 18 20

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.