The magazine of the Melbourne PC User Group
Sokoban
Ken Holmes

Part 1: What Is It? 

It was devised in Japan in 1982 and is a series of puzzles where a sokoban (Japanese warehouse-keeper) pushes boxes through restricted spaces to put them into designated storage positions. He cannot pull and can easily put a box into an impossible situation. It is a cult game with competitions to devise, or solve, new game layouts. Many members will have seen versions of it or, perhaps, similar games using (copying?) the general idea. Early DOS versions used cursor keys and you moved the pusher one square at a time up to a box and then pushed it. It was sheer hard work and the threat of RSI loomed. Further versions progressively produced improved features such as:

  1. A click on any vacant spot caused the program to calculate whether it was a feasible destination for the pusher and, if so, the pusher would proceed to it as you reclicked or held down the button.
  2. If the pusher was adjacent to a box, a click on the box would cause the pusher to push the box one space.
  3. A click on a box would select it and then a click on any space would cause the program to calculate whether the pusher could move the box to it in a series of moves. If so, it would scurry around and do the job. This allows you to concentrate on solving the game; you still have to select feasible moves and reposition boxes to open up possible routes.
  4. Right clicking could undo previous moves. Very useful. Avoids sudden death.
  5. Ability to save game, complete or not, as a movie. If you get a better result later it can be over written.
  6. Ability to design your own puzzles.
  7. Scoring systems for multiple players. Less moves is the obvious goal. 
Researchers in artificial intelligence at several universities are working on programs to solve complete games. It is by no means a trivial exercise and demands the use of supercomputers in the same league as for chess programs.

The Latest and Greatest

If you search the Web on, say, sokoban, you will find several examples with varying degrees of sophistication but the best I have seen is the freeware SOKO15.EXE by Bjorn Kallmark, available at http://www.sourcecode.se/sokoban. It offers feature 3 with seeming infallibility and split second response, even where a box must be pushed into an alcove and out again to negotiate the way to the target. Feature 4, undo, is available for the whole game if you wish, and feature 7, scoring, is effective. Most importantly, it provides 375 hard games and 77 easy ones, which must be a large proportion of those available.

The Super VGA presentation is very attractive and midi files can supply musical background. However, it does not yet include facilities to design your own puzzles or to make movies of your solutions, as do some of the less impressive versions. The author is, after his prodigious effort, taking a break to get on with the rest of his life but indicates that these are on his "To Do" list for the future.


Figure 1

In Figure 1, we have level (puzzle) 347 partially solved. There are 18 balls (boxes) of which three have been saved on the right in the red storage area. There have been 244 moves of the pusher and 70 pushes of balls. The next move? Click on which ball at lower centre? Click on which storage position? The pusher will need to get behind the designated ball and push it up the centre then into the alcove left centre and out again. It must then go down, around and up the far left passage and across the top. It descends on the ball and pushes it through to the storage (only two of the storage spots on the right border and two in the second row are accessible). Now work out how it would move one of the balls in the storage enclosure into an actual storage spot. Note, this puzzle was originated by Thinking Rabbit.

In the Meantime

The amazing ability, to navigate moves automatically, provided an irresistible challenge to match it. Working with a DOS version of Borland Turbo C++, offering only normal VGA, does not provide as pretty a result but I was able to give the user puzzle-design capacity and the ability to record solutions as movies. Bjorn has kindly given permission for me to import the games in his data file into the program (with a click and keying in the number). We will cover that program next month.

Could I suggest that you obtain Soko15; if you enjoy puzzles you will not regret it and you may well become severely addicted. All puzzles are solvable though you may not immediately be convinced of this. If you become interested you may wish to copy the Soko15 puzzles to make movies of their solutions and also to try your hand at constructing your own unique puzzles. 

You might then read Part 2 in August PC Update.

Reprinted from the July 2001 issue of PC Update, the magazine of Melbourne PC User Group, Australia