# Sokoban Maximum Moves

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

## Current Results for Small Boards

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 ? ? ? ? ? ? ? ?
2 Boxes 1 3 4 9 14 17 22 27 35 40 45 59 65 70 81 96 97 111 113 123 123 139 ? ? ? ? ? ? ?
3 Boxes 1 3 5 9 14 20 26 34 40 48 59 77 81 108 120 146 164 ? 222 ? ? ? ? ? ? ? ? ?
4 Boxes 1 3 5 9 14 20 26 37 41 52 70 88 97 124 143 174 195 212 241 ? 310 ? ? ? ? ? ?
5 Boxes 1 3 5 9 14 20 26 37 43 59 73 96 105 136 180 183 212 263 353 ? ? 420 ? 466 ? ?
6 Boxes 1 3 5 9 14 20 26 37 43 59 73 96 105 136 180 183 289 ? ? ? ? ? ? ? ?
7 Boxes 1 3 5 9 14 20 26 37 43 59 73 96 105 136 180 206 289 ? ? ? ? 509 ? ?
8 Boxes 1 3 5 9 14 20 26 37 43 59 73 96 105 136 180 206 305 ? ? ? ? 509 ?

The only known diagonal maximums are 1, 3, 5, 9, 14, 20, 26, 37, 43, 59, 73.

## Current Extremal Results

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

## Theorems and Conjectures

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.

## Other Webpages and Results

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.

## Q / A

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.