Those of you who have downloaded SOKO15.EXE from http://www.sourcecode.se/sokoban should by now be well and truly hooked and would like to record as movies your solutions of some of the puzzles. Also you may be bursting with ideas to construct your own cunning games. If so, you may download Sokoken6.exe. It is a self-extractor yielding Sokoban6.exe and supplementary files which operate in DOS. Of course, you may put a shortcut (to sokoban6.exe) on your desktop. Download and read Readthis.txt for more details.

Features

The program can import the games directly from Soko15, by courtesy of its author, Bjorn Kalmark of Sweden; his games data file is included among the supplementary files. After you have played each game, the solution may be recorded as a movie. This may be played at various speeds so that you may study it and then have another go to reduce the number of moves or pushes.

Figure 2 shows the design phase with an original game. The icons at top right may be selected and dropped onto the arena to lay out a fresh game. A click on "Save to file" will let you put it into your own data file; Then it may be played and made into a movie. If it is too easy or impossible, you may click on "Getgame" and retrieve it for modification before again saving to file. If you wish to import a Soko15 game, just click on "import file", type in the number and save to file. However, you will be unable to modify these games, out of respect for their originators, and you should read the Soko15 Help screens to appreciate who these benefactors are.

The Logic of the Moves

The computer must do an exhaustive search of all possible paths until it stumbles on the required destination for the pusher or the box.

First consider pusher moves. From its current position, it can go N, S, E or W provided the space is free. If we use this sequence, it will move north if that space is free; if it isn't it will next check whether the S space is free. Assuming it is, it will move to it and then start again by checking the N space from the new position; thus we have a recursive process where a single piece of code will call itself, with different parameters (of location in this case), as many times as required until the destination is reached. Of course, we don't want the pusher to retrace its route so each space visited is marked (in an array) so that it can't be visited twice. Thus, in the example above, the second move could not go north back to the original location and would next check S. If the first move, to the south, ultimately led to a dead-end, it would back out of all nested recursions and try moving to the east as a first move. The same procedure occurs at every position through the nested recursions until the target is achieved; then it backs out, ignoring any as yet untried branches, and the program displays the moves along the successful path.

Using a single sequence of directions may take us by a long route when a shorter one is possible. There are 24 (4X3X2X1) permutations of the sequence; using 4 or 8 of these still missed the shortest route occasionally so I have adopted using all 24. All would be equally effective on average so there seems to be no basis for selecting a limited number. This means that it can take more time but we want to find the shortest path. In some games, on a long circuitous route, one sequence is favourable in one section but it isn't in another and might miss a shortcut there; and sometimes every sequence can slip up somewhere. The missed short cut may be obvious to you, but isn't to the computer. However, you may undo the move and force the shortcut by moving the pusher in two or more separate moves.

With each sequence, it is possible for the route to have a loop section where it returns adjacent to a previously visited space. Obviously it could simply jump across, so we use a procedure which processes the history and revises it to remove useless loops of this type. This is done with all 24 sequences and, only then, is the shortest route selected.

Next we consider box moves. To move it to its destination requires a series of single space box pushes and we again use the 24 direction sequences for the box's path. For every push, the target space must be free but so must be the space on the other side of the box, and the pusher must be able to get to it to do the job. Again, we must mark each space visited by the box to avoid an endless loop. But - in some games it is necessary to push the box into an alcove then get behind it and push it out again to make it possible to reach the box's final target; this involves visiting some squares twice. Of course, the player can use two separate moves to achieve this, one into the alcove and one out. But Soko15 does it in one move and we wish to do the same. So, if a search, limiting to one visit, fails, we repeat allowing two visits to any space to see if such a backtrack offers a solution; this will find useful backtracks but may also find superfluous ones. So we need a procedure which examines each backtrack to see if, at a twice-visited space, the pusher could have repositioned itself to proceed without entering the dead end; the move history is revised to skip any pointless detours. All of these operations must be performed in each of the 24 direction sequences for the box and, of course, each intermediate move of the pusher also checks its 24 sequences. A prodigious amount of activity mops up the processor's megahertz and it can take a second or two to decide whether the requested total move is possible. Hence we put a "Working" sign on screen during the calculation to reassure the player that the mouse click was recognised. The delay is only obvious when the double search is conducted, ie. when an alcove visit is necessary for success or the chosen move is in actually impossible. You may choose to get a quicker result by using two moves. Also, if the program can't find an obvious shortcut, you may force it as with the pusher.

I am impressed by Soko15 which carries out all moves instantaneously whether or not an alcove detour is necessary; it occasionally misses the very shortest route but only by a few spaces. Perhaps it uses less than 24 direction sequences and uses some smarter concept or technique in the coding. When Soko15 is further developed to include movies and puzzle design, my attempt will become superfluous. However, it provided a subject for a programming exercise and it is refreshing to discover a game in the hands of enthusiasts who, whilst in friendly rivalry, are ultimately motivated towards providing more enjoyment for all.

If members wish to originate fresh games, or see a movie of a solution of a Soko15 game, I can act as a clearing house for these. You need only send your games6.txt and the appropriate movie??.dat files to myself or any other person. The recipient can create a second folder with another copy of Sokoban6, removing games6.txt and the movie??.dat files and substituting with yours. Incidentally, if no games6.txt file is present, the program will create it when you save game number 1; this may be an imported Soko15 game or one you have just designed. You may thus create a shorter file, with one or a few games, to exchange.

There are many of the Soko15 games which seem impossible to me and I am confident there will be many similarly placed. 

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

[About Melbourne PC User Group]