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.