33
$\begingroup$

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?

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is an infallible algorithm: see my answer. $\endgroup$ – Jeffrey Bosboom Aug 22 '14 at 23:00
9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ You'd probably need to include some form of backtracking, otherwise the random block-pulling monkey can easily get stuck in a corner with no way out. (Of course, you could just make the player start where the monkey gets stuck, but if this happens too easily, the levels may end up being rather dull.) $\endgroup$ – Ilmari Karonen Nov 3 '15 at 14:35
  • $\begingroup$ If all targets are in a corners, the monkey cannot do anything $\endgroup$ – Cohensius Nov 22 '18 at 9:55
  • 2
    $\begingroup$ @Cohensius This is not a problem, since the Monkey plays the game "backwards" the Monkey can pull crates and not push them. So he runs around and pulls the crates out of the corners. $\endgroup$ – Falco Nov 22 '18 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.