Longest Rectangular Sokoban Puzzles

In early 2016 I wrote a program to determine the maximal, or longest possible, Sokoban puzzle inside a rectangular grid of a particular size. Longest means that the puzzle takes more player moves to solve than any other puzzle in same same room. For this search, I only considered grids with no internal walls, because allowing internal walls would vastly increase the search space. The longest searches already took some hundreds of hours on my machine.

The algorithm used is pretty simple. For a given set of goal squares, we can do a breadth-first search backwards through the possible positions of the puzzle to find out how long a puzzle with that goal can take to solve. Then we just need to try that for every possible set of goal squares, up to rotation.

You can download these puzzles in playable format in this .sok file.

2x3: 5 moves

2x4: 7 moves

2x5: 14 moves

2x6: 23 moves

2x7: 31 moves

2x8: 49 moves

2x9: 57 moves

2x10: 76 moves

2x11: 84 moves

2x12: 112 moves

3x3: 14 moves

3x4: 29 moves

3x5: 49 moves

3x6: 71 moves

3x7: 101 moves

3x8: 144 moves

4x4: 70 moves

4x5: 91 moves

4x6: 206 moves

5x5: 185 moves