Some thoughts on designing Sokoban levels
The rules for playing Sokoban are quite easy, as I explained in an earlier article. Designing a technically valid Sokoban level, that’s also easy. Designing a technically valid Sokoban level that has an interesting solution, that’s a bit more difficult.
From the rules for playing the game, we can extrapolate some rules for designing levels:
- There should be exactly as many goals as there are boxes, e.g., if a level has ten boxes, it should also have ten goals for the boxes, not nine, not eleven, not any other number.
- It is permissible for one or more of the boxes to already be on goals at the beginning of the level (however, it’s not a rule that the solution should require moving those boxes to other goals).
- From the starting position, it should be possible to move whichever boxes are not on goals into goals. Put another way, the level should have at least one valid solution.
- And of course there should be a player token, or “pusher,” on the board (seems obvious, but I’ve actually forgotten this one a few times).
It’s reasonable to expect a dedicated Sokoban level editor (like the one in Sokoban YASC) to enforce the one-to-one ratio of boxes-to-goals, and the presence of the player token.
However, we should not expect a Sokoban level editor subprogram to detect that a level is unsolvable. Though I do think it’s reasonable for websites that publish Sokoban levels to require the author to submit a solution before publishing.
The difficulty of Sokoban levels ranges from very easy to very hard. If a level is way too easy, the player might feel disappointed upon solving it, because they were expecting a challenge.
But if a level is way too hard, to the point that the player wonders if the level has any solution at all, they might just give up. We shouldn’t ask people to invest their time in a game that will mostly only frustrate them.
One thing that makes a Sokoban level particularly frustrating is when it seems to require you to perform an extremely long sequence of steps to solve but you really have no idea whether you’re on the right track or not.
So medium would seem to be the ideal level of difficulty. The player can feel some measure of satisfaction in having solved the puzzle, without having had to yank their hair out to do it.
Still, I think there is some value to making very easy levels and very difficult levels. So I did. I made three sets of ten levels each: extremely easy, seemingly hard (but actually medium) and what I thought would be frustratingly difficult (but honestly also medium).
Extremely easy levels
I figured I should start by making some easy levels. But extremely easy. As in the only way you could fail to solve it is if you stall. The only way to make these levels difficult is by enforcing a time limit. It would have to be a very tight limit, like maybe five or ten seconds.
Another gimmick I decided on was that there would be ten levels in the set. The first level would only have one box and one goal, the second level would have two boxes and two goals, the third level would have three boxes, and so on and so forth.
I didn’t realize it until later that the first extremely easy level I came up with is a mirror version of the Sokoban YASC dummy level that YASC makes when you have it create a new level. There is only one possible move, and that move pushes the box into its goal, thus solving the level.
In the second level, there are two possible first moves, either of which will push one of the boxes into its goal. Then, if you want, you can dawdle, by moving back and forth between the starting position and the position previously occupied by the box you just pushed into a goal.
Note however that YASC doesn’t count such simple dawdling as additional moves. When you finally push the opposite box into the other goal, YASC records the solution as three moves and two pushes.
The third and fourth levels are pretty much like that. Avoiding monotony in the design of these levels is starting to become a challenge. For the fifth level, I tried a few different things but rejected them because they introduced the possibility of obvious deadlocks.
I finally came up with something that looks different from the previous levels but is still impossible to mess up. And it introduces a way to solve inefficiently without obvious dawdling. The obvious solution is in six moves with five pushes, but it’s also possible to solve it in nine moves.
The sixth level is another one of those that you can dawdle in without Sokoban YASC counting it against you. In the seventh level, though, like in the fifth, inefficient solutions are possible.
The best solution for this one is sixteen moves and seven pushes, but an inefficient solution of 36 moves and seven pushes is also possible. The eighth, ninth and tenth levels are built along similar lines.
I think these levels could be useful for testing a new Sokoban program, or for understanding what makes a level easy. They will definitely be useful for early testing of my own Sokoban implementations.
Unlike most easy levels, there’s no flexibility for matching boxes to goals. Each box has a goal specifically for it and no other box. The flexibility to put any box in any goal also carries with it the possibility to screw up, which I did not want for this set of levels.
It occurs to me that on some really difficult levels, there is also a required box-to-goal correspondence. The difference is that the correspondence is not obvious; it’s all too easy in those really difficult levels to mess up and put a box in the wrong goal in such a way that you can’t place any more boxes on goals and therefore have to backtrack or even restart the level.
It almost goes without saying that most solutions to these extremely easy levels are resistant to optimization. Only for the tenth level of this set did I allow the Optimizer to come up with the best solution.
As I started on this, I thought designing extremely easy levels would be difficult. But, as I’ve come to find out, designing easy but not extremely easy levels is actually quite a bit more difficult.
Seemingly hard levels
I think the best Sokoban levels are those difficult enough that you can’t solve them on the first try, but easy enough that you can solve them on the second try.
The levels in this next set are actually not that hard: you can solve them on the first try if you take a moment to think about how you’re going to solve it before making the first move.
In the first level of the set, the most obvious sequence of moves at the beginning is the wrong sequence. But as you make your way to make the bad move, you might realize that you actually need to move the box in the opposite direction before you can move it into the goal.
Though I’ve surprised myself a few times, coming up with a better solution while I’m playing the levels thinking I’m just making sure the levels play as intended.
In many of these levels, I provide a long way to get at the solution. But, in all honesty, I don’t know if I would have eventually found the simpler solutions for my own levels without the YAS Optimizer.
Like a couple of hours before my originally intended publication date for this article: I played the sixth of this set and came up with a 132-move, 36-push solution. This is an improvement on my prior move-optimal solution of 140 moves.
I looked on GitHub, and sure enough, the version of the file there did not show the solution I had just come up with. Mostly, though, when I play these levels again, I come up with worse solutions.
The seventh level of this set is one of those rare instances in which I came up with a push-optimal solution and the YAS Optimizer came up with a move-optimal solution.
And the tenth level is a little odd among these in that it can be solved with eleven pushes, one for each box but one. I think my original idea for this one was that it was going to be one of the extremely easy levels.
My attempt at frustratingly difficult levels
In my opinion, the most frustratingly difficult levels are the ones in which almost all the boxes are already in goals, and it seems like the only way to get the last box into a goal is to empty out all the goals before you’re able to put all the boxes into them.
Confronted with a level like that, some players might decide that the effort to solve such a difficult level is just not worthwhile, and they should look for a different level or even a different game.
That was my goal with the Frustratingly Difficult set. But they turned out to be more medium difficulty, and one of them turned out to be ridiculously easy.
This set also consists of ten levels, with the first level having only one box and one goal, and each subsequent level adding one box and one goal.
Obviously then on the first level I couldn’t put the only box on the only goal. So instead for the first level I made a maze. The box is two spaces away from the goal. To get the box into the goal, you have to push the box the long way around, being careful not to push it into a dead end.
The best solutions I’ve got are my own move-optimal 193 moves and 79 pushes and the YAS Optimizer’s push-optimal 237 moves and 77 pushes. So the optimizer was able to avoid two pushes at the cost of 44 moves.
For the second level, I also came up with the best move-optimal solution and YASC came up with the best push-optimal solution.
For the third level, YASC found a 23-push solution that seemed perfectly obvious and simple, but would have never occurred to me on my own (best I could come up with was with 41 pushes).
Likewise on the fourth level YASC found a better solution than the one I intended, though on that one, eighteen pushes are required no matter what, so the only hope to improve a solution is to minimize the number of moves.
Another characteristic of some frustrating levels is that the player token is initially placed on a goal. So on the fifth level of this set, I placed the player token on the center goal, surrounded by four boxes already on the goals, and wall blocks.
However, the level is actually a lot easier than it looks. I put in a lot to try to suggest to the player that they should empty out the goals before they can start putting boxes into goals. Hint: it’s actually possible to solve the level by pushing only two of the five boxes, though the solution is neither move-optimal nor push-optimal (60 moves or 14 pushes, both found by YASC).
And on the sixth level, four boxes are already on the goals, but two of them are on the wrong goals. The seventh level is another one in which the player token is centered on a goal and surrounded by boxes.
However, it turns out this level is extremely easy if you don’t get distracted by the idea that you need to move every box. This level can be solved moving just two boxes.
I was going to do a similar shtick for the eighth level, but decided it would be more interesting with two boxes not already on goals. That’s another one for which I came up with the best move-optimal solution that I’m aware of, and YASC came up with a push-optimal solution.
I wish Sokoban 3.0 had a solution replay feature like Sokoban YASC; I think these two programs count moves and pushes a little differently. I was testing this eighth level on Sokoban 3.0 and came up with a solution of 71 moves and 19 pushes.
But, as far as I can tell, Sokoban 3.0 does not record solutions. So I opened the level on Sokoban YASC and tried to replicate the solution I had just come up with. It got counted as 91 moves and 20 pushes; I do believe I replayed it the same way but can’t say for sure.
It was a good enough solution that Sokoban YASC classified it as the best move-optimal solution, and demoted its Optimizer’s 119-move, 16-push solution from “Best Solution” to best push-optimal solution. But I’m left with the doubt that I did not correctly reproduce for Sokoban YASC the solution I came up with on Sokoban 3.0.
For my ninth level of this set, my first two solutions were both with 31 pushes, and YASC came up with a 31-push solution and fewer moves. Days later, I really surprised myself by managing to come up with a move-optimal solution of 116 moves and 27 pushes and a push-optimal solution of 120 moves and 23 pushes.
But then last week I managed to further improve it to 114 moves and 23 pushes. Which led me to formulate the theory that YASC’s Optimizer works best when a human has already come up with very good solutions.
At least for this particular level, my theory was borne out when the Optimizer was then able to come up with a solution of 96 moves and 19 pushes, and an alternative 114-move 23-push solution.
I also tested my theory on my tenth level. I had come up with a move-optimal solution of 142 moves and 44 pushes, and a push-optimal solution of 164 moves and 42 pushes, both beating an earlier solution by the YASC Optimizer of 234 moves and 54 pushes. Following up on my move-optimal solution, YASC came up with a 116-move, 40-push solution.
So these levels aren’t as difficult as intended. Sometimes I think they’re rather easy. Then I play them again and get confused. Especially if I play in Sokoban 3.0 rather than Sokoban YASC, since the former lacks the deadlock detection of the latter, or maybe it does have it but doesn’t give any warnings.
Next steps
I will continue creating Sokoban levels as I work on my own implementations of the game.