Sokoban!

Sokoban is an interesting and deep puzzle that I've been interested in for a couple of years. Solving and designing puzzles by hand is a lot of fun, and with computers, there is an added level of depth. There are some very powerful puzzle solvers and solution optimizers out there, as well as a program called YASGen that uses a genetic algorithm to generate difficult puzzles. I use JSoko and Sokoban YASC and play on Sokoban Online.

My contribution to the computer side of things is a program that finds the longest puzzles with a given goal position or a given start position. It will search the entire graph of possible positions, if enough memory is available, and print the positions it finds at the edge of its universe as well as how many moves it takes to get there. Let's call it the "pessimal program" - pessimal means worst possible, as in furthest from the goal.

Here is a collection of all the different puzzles I have made. As of 2018/09/24 they include 22 handmade puzzles already published on Sokoban Online, 56 rectangular puzzles as seen below, 31 puzzles found with the pessimal program, 17 handmade puzzle variants or ideas that weren't my best, 32 puzzles made with YASGen, for a total of 159. Note that I have a few puzzles on Sokoban Online that aren't in here, because they use that site's Modern elements like colored blocks and ice.

Longest Rectangular Puzzles

I've used a variant of my pessimal program to determine the longest possible Sokoban puzzle, in move count, that fits in a rectangular grid of a particular size. I only considered grids with no internal walls, because allowing internal walls would vastly increase the search space, and I haven't found a way to efficiently deal with that yet.

The actual algorithm is pretty simple. For a given size, loop through every possible placement of goals. For each goal, run an optimized version of the pessimal program to find out how many moves away a start position can be. The goal position with the largest possible distance, plus a start position at that distance, is the longest puzzle of that size. For the biggest of these, it took some hundreds of hours on my machine to check all possibilities.

I've also included a lot of puzzles that I haven't proved to be optimal - a lot of them probably aren't. Those puzzles are marked with a ? in the chart. Most of these sizes can't plausibly be completely searched, but these are the best positions I could find so far, using my pessimal program and trying alot of possible goal positions. To find good goal positions, I tried techniques such as manually extending a pattern, using YASGen, moving goal squares one by one and taking the best output at each point, and adding a column of goals or not-goals to a smaller rectangle in all possible ways.

There are a few patterns here that are worth noting. A rectangle always has a puzzle with at least as many moves as a smaller rectangle, because it's always possible to fill an entire edge with already-solved immovable pieces. The 2xN positions fit a pretty clear pattern, which seems to be O(N^2) - the number of moves increases quadratically in N. I also found some patterns for 3xN and 4xN, and although they take a lot of moves, they may have unimpressive long-term growth. I think the 3xN pattern here actually grows as O(N) in the long run.

The 5xN pattern is a variant of the famous 'Fibo' pattern. The number of moves to solve it grows exponentially, with a base of the golden ratio. This pattern's existence brings up some questions: are there exponential patterns for 3xN or 4xN? Are there exponential patterns that grow faster than this? Are there patterns that grow faster than exponentially?

Here are the proved longest, or longest known, Sokoban puzzles for various rectangles, along with images:

	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
2	5	7	14	23	31	49	57	76	84	112	120	152	160?	197?	205?	252?	260?	307?	315?	373?	381?
3	14	29	49	71	101	144	167?	208?	252?	259?	314?	318?	376?	380?
4		70	91	206	234?	330?	343?	374?	484?	485?	530?	614?
5			185	305?	334?	347?	527?	861?	1381?	2247?	3609?	5830?
6				331?	485?	892?	1379?	2354?	3735?	6170?