Development of a Sokoban level

2016-06-26

Making Sokoban puzzles are easy.
Making interesting Sokoban puzzles people want to play takes a bit more.

Developing a puzzle, hopefully interesting for other people, takes some decisions at the start. Here is what I consider.

  1. I need an idea, however faint, to the puzzle I want to make. Could be a predefined layout of the goal, could be a remake of some interesting designs by others, could be… Sometimes I will end up with something totally different from the starting idea.
  2. I want my goal area to be connected and if not with a graphically pleasing look. Never just randomly shattered goals.
  3. I usually want every block to be moved. If not you could just as well place a wall instead of the block. I am not a fanatic though. Look at these puzzles: NonMovingThe puzzles have the same solution but the one at the right has by far the nicest look. And actually is tougher, since you get some extra losing options.
  4. I don’t want a lot of unused floors. Not a fanatic either here. Specially if extra floors give you some loosing options or give the puzzle a nicer look.
  5. Should the puzzle be tough or easy? I always want my puzzles to be challenging but not necessarily very tough.

You need some tools to develop Sokoban puzzles.
Some people use a pencil and a piece of paper.
Some people just use an autogenerator.
I use the tools in YASC. You get a level designer, a solver and an optimizer. Alle of which I use a lot. Making development much easier.

But follow me through the development of “Three” below. The solutions are optimized solutions. The position of the graphic elements are described in Sokoban the same way as in Chess. From the upper left corner columns by letter, rows by number.

3-01The basic idea: The start position is a horizontally mirror of the end position.
Place the blocks and goals, surround by a wall and put a Sokoban somewhere and that’s it.

Solution: 16/7

Well, that was a little to easy.

3-02aNext step is obvious: Block the immediate paths to get to the goals.

Solution by moves: 78/29
Solution by pushes 96/21

The two blocks at the arrows don’t need to be moved at all. (Lowest two blocks if solution by pushes).
Not quite finished yet.

3-03Let us do some more blocking. Now the Sokoban has to start by pushing the block at C4 or C8 two columns to the right followed by pushing the block at D6 up/down.

Solution by moves: 114/37
Solution by pushes: 240/25

Fascinating. An explosive increasement in solution by pushes. But by moves you still don’t have to move the upper two blocks.

3-04aIf you want to make a specific block to move, then watch the solution and try to hinder the blocks in the vicinity to move. If you watch you will observe a vital part of the best solution is pushing the block at the arrow up and later back again. Let us make that impossible by placing a wall at F3. Now you need to move the block E4 to get it back.

Solution by moves: 100/37
Solution by pushes: 246/25

Still you don’t have to move the two lower blocks.

3-05Now the puzzle is far from trivial to solve and why not publish it as is?
Let’s do some “normalizing” = Removing all unnecessary walls outsize the puzzle.
Should be interesting enough to publish?

3-06Nah. I really don’t like the lonely wall in the upper left corner. Lets get rid of it.

Solution by moves: 94/37
Solution by pushes: 244/25

Didn’t change the difficulty much and those blocks at the bottom still could be just walls.

3-07aBut isn’t the puzzle a little open in the top? Lets remove some floors.

Solution by moves: 118/33
Solution by pushes: 123/27

Solution by moves are quite unchanged. But now you can’t get the Sokoban “around” the blocks which halves the moves for the optimal push solution but only increases the pushes by two.

3-08aAll the blocks move in the optimized solutions, but it is still quite easy to find a solution not involving moving the two buttom blocks. Something needs to be done at the buttom.
The usual tool: Block some movement.

Solution by moves: 116/33
Solution by pushes: 128/27

Still not moving. Not really getting anywhere.

3-09Let’s place an extra block one up, one left instead.

Solution by moves: 120/37
Solution by pushes: 226/29

Actually up to this layout the best solution found by YASO involved moving all the blocks so I thought I were close to a finished puzzle.
But now the best solution didn’t involve moving these two */@/#** blocks and it got painfully clear I still had to do something in the bottom of the puzzle.
Backtracking I discovered it up to now never was necessary to move those two blocks at the bottom to solve the puzzle.

3-10Back to the drawing board.
We certainly don’t need the floor lower right? Might create a need to move those two blocks.

Solution by moves: 135/41
Solution by pushes: 221/29

But does the lower blocks need to move? Off course not.

3-11Well, why not repeat the layout from the top. We need to move the block C8 eventually.  And now, to move it, you need to move C9. This can only be pushed to E9 and to get it away from this position we need to move both of the lower two.
That should do it!

Solution by moves: 131/39
Solution by pushes: 211/31

Finally you need to move everything.

3-12Now I just have to remove unnecessary floors and normalize the board.
Anything more to do ?
Ready for publishing ?

3-13Let’s just try an extra wall upper left…

Solution by moves: 207/43
Solution by pushes:267/35

Just a small change and a considerable increase in moves necessary to solve the puzzle.

3-14No more changes except for a final normalization.

Case completed.

You probably have noticed I use the solver and optimizer a lot. These tools considerably speed up the development time since you can test whether a design have a solution or not in no  time. And the optimization often shows a design is solvable in a much easier way than intended and you have to redesign your puzzle to make it interesting.

I am not the first to write about how to design a puzzle. Try