The goal of this site is to find lower bounds for questions of the form, "Which Sokoban boards have the longest shortest solutions?"
For more information on this website and sources for other max moves Sokoban results, scroll to the bottom.
To build your own puzzles or to import a puzzle in standard Sokoban format click HERE
To find the optimal box placement for a particular puzzle, check out the optimizer tool HERE.
Please send all additional results to me to have them added to this page (email at bottom of page)!
Here are the best known results (best moves and boards). Best guesses are in italics and proven best for the column are in bold.
| Spaces | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 Box | 1 | 2 | 3 | 5 | 9 | 11 | 15 | 18 | 21 | 25 | 28 | 32 | 35 | 41 | 42 | 48 | 50 | 57 | 59 | 65 | 69 | 73 | 77 | 81 | 85 | 89 | 93 | 97 | 101 | 105 |
| 2 Boxes | 1 | 3 | 4 | 9 | 14 | 17 | 22 | 27 | 35 | 40 | 45 | 59 | 65 | 70 | 81 | 96 | 97 | 111 | 113 | 124 | 127 | 139 | 142 | 152 | 156 | 166 | 169 | 180 | 183 | |
| 3 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 34 | 40 | 48 | 59 | 77 | 81 | 108 | 120 | 146 | 164 | 165 | 222 | 223 | 248 | 248 | 274 | 274 | 300 | 300 | 326 | 326 | ||
| 4 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 37 | 41 | 52 | 70 | 88 | 97 | 124 | 143 | 174 | 195 | 212 | 241 | 257 | 344 | 344 | 384 | 384 | 425 | 425 | 466 | |||
| 5 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 37 | 43 | 59 | 73 | 96 | 105 | 136 | 180 | 183 | 218 | 263 | 353 | 354 | 381 | 420 | 421 | 466 | 467 | 512 | ||||
| 6 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 37 | 43 | 59 | 73 | 96 | 105 | 136 | 180 | 183 | 289 | 290 | 353 | 381 | 382 | 420 | 421 | 466 | 467 | |||||
| 7 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 37 | 43 | 59 | 73 | 96 | 105 | 136 | 180 | 206 | 289 | 290 | 353 | 381 | 396 | 509 | 510 | 511 | ||||||
| 8 Boxes | 1 | 3 | 5 | 9 | 14 | 20 | 26 | 37 | 43 | 59 | 73 | 96 | 105 | 136 | 180 | 206 | 305 | 306 | 353 | 381 | 396 | 509 | 510 | |||||||
The only known diagonal maximums are 1, 3, 5, 9, 14, 20, 26, 37, 43, 59, 73.
Here are the current, best known, extremal values for the number of steps as a function of the number of spaces for fixed numbers of boxes.
| Extremal Bounds | Lower Bounds | Upper Bounds |
|---|---|---|
| 1 Box | \(\frac{3n^2}{49}\) | \(n^2\) |
| 2 Boxes | \(?\) | \(\frac{n^3}{2}\) |
| Any Fixed Number of Boxes (b) | \(?\) | \(\frac{n^{b+1}}{b!}\) |
| Any Number of Boxes | \(\frac{9+\sqrt{5}}{\phi^{\frac{7}{3}}}\phi^{\frac{n}{3}}\) | \(\frac{\sqrt{n}2^n}{\sqrt{2\pi}}\) |
This table contains the order of growth, best known constant, and in some cases, a link to the full derivation and more info (Coming Soon).
The following is a list of theorems and conjectures relating spaces, boxes, and moves.
Statements with a particular relevance/importance to speeding up true value calculation are listed first
Define \(\max_p(k)\) to be the highest possible movecount for a polyomino \(p\) and a number of blocks \(k\).
Define \(\max(n)\) to be the highest possible movecount for all polyominoes with exactly \(n\) spaces.
Define \(\max(n, k)\) to be the highest possible movecount for all polyominoes with exactly \(n\) spaces with exactly \(k\) blocks.
Note, when we mention cycles in a polyomino \(p\), we are refering to \(|faces|-1\) in the grid graph of \(p\).
| Status | Statement |
|---|---|
| Conjecture | \(\max_p(k) > \max_p(k+1)\) implies \(\max_p(k) > \max_p(j)\) for all \(j>k\). |
| Conjecture | The number of boxes in the \(\max(n)\) puzzle is at most one greater than the number of boxes in the \(\max(n-1)\) puzzle. |
| Proved | The polyominoes \(p\) where \(\max_p(k) = \max(n)\) cannot contain bent arms or Ts not part of a larger cycle. |
| Proved | The polyominoes \(p\) with \(n\) spaces where \(\max_p(k) = \max(n)\) will always have at least two cycles, at least above a certain size. |
| Conjecture | The polyominoes \(p\) with \(n\) spaces where \(\max_p(k) = \max(n)\) will always have at least three cycles, at least above a certain size. |
| Conjecture | The polyominoes \(p\) with \(n\) spaces where \(\max_p(k) = \max(n)\) are likely to have almost as many cycles as possible. |
| Conjecture | For every \(k\), there is some \(n\) such that all maximal puzzles with \(m\) squares, for \(m \geq n\), have at least \(k\) cycles. |
| Proved | For every \(k\), there is some \(n\) such that all maximal puzzles with m squares, for \(m \geq n\), have at least \(k\) boxes. |
| Proved | \(\max(n,k) \geq \max(n-1, k-1)\). |
| Proved | \(\max(n,k) \geq \max(n-1, k)\). |
| Conjecture | The maximum length of a puzzle in a \(3 \times N\) polyomino grows polynomially. |
| Proved | The maximum length of a puzzle in a \(5 \times N\) polyomino grows exponentially. |
| Conjecture | There are an infinite number of spaces \(n\) such that \(\max(n+1, j) = \max(n, k)\), \(j\neq k\), and \(\max(n+1, j)\neq 0\). |
| Conjecture | There are a finite number of spaces \(n\) such that \(\max(n+1, k)-\max(n, k)\) is 1 or 3. |
Here are a few selected results for long Sokoban solutions given various constraints on the board.
Longest small Sokoban boards: https://erich-friedman.github.io/mathmagic/0300.html
Longest rectangular Sokoban boards: https://mzrg.com/sokoban/
Sokoban is PSPACE Complete (Finite Tape Turing Machine emulation in Sokoban): https://webdocs.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html
And A Tool For Optimizing Sokoban Level Solutions
Sokoban YASC: https://sourceforge.net/projects/sokobanyasc/
And A Few Sites With Puzzle Collections
Sokoban Online: https://www.sokobanonline.com
Let's Logic: https://www.letslogic.com/
Sokoban MF8: http://sokoban.ws/current_comp.php
If you believe that there is another resource which fits on this list, please send it over to me.
I have a new result. I have a question. I found an error on the site. What should I do?
Send me an email here: zachdestefano (at) gmail (dot) com
For small boards, I will validate the minimum number of moves with YASC.
How did you calculate the true results?
The true results were calculated locally by qqwref and I using a few programs which we wrote in C++.
The general process was the following:
(1) enumerate all polyominoes with a specific number of spaces,
(2) eliminate ones that we could prove were not optimal),
(3) search through all goal placements to deteremine the maximum steps.
For the diagonals the process is more complex:
We enumerate something we call antipolyominos and perform the same search.
We are working on a proper writeup and code so anyone can replicate these results.