How can I procedurally generate Sokoban puzzles?

Question

How can Sokoban puzzles be procedurally generated with a computer program, guaranteeing at least one solution?

A simple algorithm might be:

{n} times
    place a "target" square and a box on the square
end
until {puzzle is done (?)}
    move a character to a location next to the box, and "pull" it towards the character
end

Here are my two main questions about this:

1. How do you tell when the puzzle is "done" enough? (line 4)

2. How would you move the character next to a box so that it could be pulled?

   I was thinking about some kind of flood-fill to see if the character can reach a box, but how do I go to a random location from which I can pull a box?

Answer 1

There is, indeed, a way! No way has yet been found (at least that I've found) to generate them infallibly, though.

In a paper by Y. Murase, H. Matsubara, and Y. Higara, called "Automatic Making of Sokoban Puzzles", they explain exactly how one makes unique puzzles. While their algorithm isn't perfect (about half of the puzzles they generated aren't solvable), it offers a significant statistical advantage over other possible methods.

In essence, they rely on three basic templates which are applied over a basic template which statistically are likely to generate solvable situations. Then, they mark specific spaces as invalid for both goals and boxes.

Goals are generated first, as boxes' positions are restricted by the goals. Invalid positions for goals can be categorized by checking each direction; if there is no valid way to push a box into the goal from any direction, that position cannot be a goal.

Then, crates are marked. The majority of invalid crate positions are those in corners (positions bounded by two walls) and those against walls with no goal access. These invalid positions are re-evaluated after placing each crate to insure that, for instance, two crates aren't placed adjacently against a wall.

Then they literally run a solving algorithm on it and see if it works.

You can see a demonstration of this algorithm, called Autosokoban.

Answer 2

Joshua Taylor and Ian Parberry, "Procedural Generation of Sokoban Levels", Proceedings of the 6th International North American Conference on Intelligent Games and Simulation (GAMEON-NA), pp. 5-12, EUROSIS, 2011. The abstract is:

We describe an algorithm for the procedural generation of levels for the popular Japanese puzzle game Sokoban. The algorithm takes a few parameters and builds a random instance of the puzzle that is guaranteed to be solvable. Although our algorithm and its implementation runs in exponential time, we present experimental evidence that it is sufficiently fast for offine use on a current generation PC when used to generate levels of size and complexity similar to those human-designed levels currently available online.

Note that in contrast to Emrakul's answer, the puzzles produced by this algorithm are guaranteed to be solvable.

The paper, a presentation video, and five level sets are available at the paper web page. Unfortunately, the implementation does not seem to be available.

Answer 3

Couldn't you just use this easy approach:

Simply start with a solved Level and let a random generator play the level backwards!

So the Figure can move in all directions and optionally pull crates while moving - just let a random monkey play the level for some time and if it looks pretty use it!