Thursday, May 29, 2014

The Original Sokoban Puzzle Mystery -- SOLVED!

The Original Sokoban Puzzle Mystery -- SOLVED!

Credits
Hiroyuki Imabayashi, Thinking Rabbit and Falcon Co. Ltd. - for the original Sokoban game

Andrew Myers - for XSokoban, without which the mystery of the original puzzles would not exist

Joris Wit - for Sokoban++, without which I would not have been able to pursue puzzles larger than 50x50 cells (it was the first I found that could support those size puzzles)

Brian Damgaard - for Sokoban YASC, and for his indispensible help and advice on the puzzle files

Rekrul, didi_lxt, merman and the Commodore 64 (C64) Forum for their great help with the C64 variant of the game

Carlos Montiers for his very important and great help with the Japanese versions and the early MS-DOS variants

The Virtual Apple ][ Online Emulator for allowing me to be able to compare the Apple ][ variant of the game

Other links:
Sokoban History
Sokoban: The beautiful world of remodels
                 UPDATE

New information has come to
light. I am now able to add
more information concerning
both the original Japanese
versions of the game, as well
as about the variants produced
by Spectrum Holobyte. I will
be updating this site to
incorporate what I have now
learned.
Puzzle 42 of the Commodore 64
variant is unsolvable! This has
apparently been the case since
its release. I am seeking to
find out if Spectrum Holobyte
ever issued a fix for this.
If you know something, email me.

"What mystery", you ask? The mystery of the Sokoban level file named "Original.txt" (hereafter called 'the Original'), and whether or not the puzzles it contains are the "original" fifty puzzles. The Original contains no other information than the following file notes and ninety puzzles, each followed by a level number:

; Original & Extra

; Copyright: Thinking Rabbit
; E-Mail: 
; Web Site: 
;
; The 50 original levels from Sokoban
  plus the 40 from Extra.
The Original has also been known, for over ten years, to be the puzzles from the XSokoban variant of the game. For the purists among the Sokoban crowd, these puzzles are not the originals, because five of the puzzles differ from the official release of the game licensed by ASCII Corp. and developed by Spectrum Holobyte, a division of Sphere Inc. The variant accepted as the "official original" has long been held to be the MS-DOS variant, but there were three other variants that were just as official, and were released in the same time period. Two of them were also by Spectrum Holobyte. They are the Commodore 64 variant, and the Apple ][ variant. The third variant was sub-licensed from ASCII and Sphere by Tandy Corp. for their TRS-80 Color Computer series, and was developed by Spectral Associates.

The XSokoban Trail

I decided to explore this myself. I located the XSokoban site through Google and visited the site. On the site is a link to a manual page for XSokoban. Following that link, I found this under the Authors label:

Authors

Unknown Hacker - Original curses(3) implementation.
Joseph L. Traub - X windows interface.
Kevin Solie - simultaneously developed X
  implementation (merged in). 
Mark Linderman, Christos Zoulas - Mouse code (added
  to Solie's version). 
Andrew Myers(http://www.cs.cornell.edu/andru) -
  Improved mouse UI, score ranking, color and WWW
  support.

Code has also been donated by many xsokoban users.
  Thanks for all your contributions and suggestions!

I followed the link: "The source code for various versions published by me and by comp.sources.x." (turned out to be titled 'Downloading XSokoban'), and downloaded the 3.3c implementation. Once it was extracted to my hard-drive, I opened the README file and found, at the beginning:

XSokoban 3.3c
-------------

This distribution contains all the files to compile
and run the game, the original 50 sokoban screen files,
40 additional screen files gleaned from various public
domain versions of sokoban, and a manual page that
explains how the game works.

From this I was able to determine that the XSokoban variant does contain ninety levels, and that the forty "extras" were gleaned from other variants of the game.

I also sent an email to Andrew Myers using the address listed on the XSokoban main page. Since the site had not been updated since 2006 (the page information for the main page shows a last modified date of January 27, 2006), I could only hope that this was still a valid email address, and that Mr. Myers was still at Cornell University. It turns out that he is still located at Cornell, and he did answer my email. I have not received permission to quote his email directly, but I can say that he indicated that he himself modified some of the extras to try to increase their solution difficulty. He did not say which puzzles he modified. He also indicated that he did not know of the existence of the file named Original.txt, and that he could not say whether the original fifty were actual originals or not, only that he did not modify them.

I compared the first fifty of the XSokoban puzzles to the first fifty puzzles in the Original. They were the same puzzles. The difference is that the Original is all fifty puzzles in fifty "levels" of one puzzle each in a single file, and the XSokoban puzzles are contained in fifty separate files, each named screen.x (where x is a number from 1 to 50). Puzzle file screen.1 contains:

    #####
    #   #
    #$  #
  ###  $##
  #  $ $ #
### # ## #   ######
#   # ## #####  ..#
# $  $          ..#
##### ### #@##  ..#
    #     #########
    #######

I did not compare the forty extras (screen.51 through screen.90) to the forty puzzles in the Original. Since the first fifty were the same, I think it safe to assume the last forty are also the same. I leave it to someone else to make those comparisons.

I thank Prof. Myers for his time, his email, and the information he provided. While it does not bring a definitive answer to where the original fifty came from, it does close the case on whether or not the Original is taken from XSokoban, and the answer is YES, the Original.txt file is taken directly from the XSokoban screen files.

On the Comparison Trail

While I had learned some of the answers I was looking for, I had yet to learn how these puzzles compared to the original official variants. Comparison to the MS-DOS variant had been documented already, but I wanted to be thorough, so I compared the Original to all three of the Spectrum Holobyte variants and the Spectral Associates variant.

I am a Color Computer enthusiast with a leaning towards the NitrOS-9 RTOS and a love for the Basic09 programming language. In addition, I am also a video game player, and have played many games on the CoCo. I was first introduced to Sokoban on my CoCo3 when I inherited a copy of the ROM cart from a friend who was getting more into PCs and farther away from the CoCo. It was that variant that I played first, and I was able to locate and download a digital copy of the ROM cart. My first comparison was between the CoCo variant and the XSokoban variant.

I have also played the MS-DOS variant in the past. First it was on my friend's PC, a 386. In 1999-2000 I owned a Pentium-II PC, and I ran Windows 2000 Professional on it (I was a student at DeVry then, and received a copy of that OS as part of my required materials). On that computer I was able to play the game in a 16-bit protected window. It was easy to locate another copy of that variant, which I downloaded and installed in DOSBox. This was the second variant I compared to the XSokoban variant, and I also compared it to the CoCo variant.

While I knew that the Apple ][ and Commodore 64 variants existed, I had never owned a copy of either (or the machines to play them on). I found the Virtual Apple ][ Online Emulator by Googling Apple 2 emulators, and was pleasantly surprised to find a copy of that variant available for play through the online emulator. This is how I compared the Apple ][ variant to to all three of the variants I had already compared.

The Commodore 64 variant proved to be more elusive. There was one link that claimed to be a online emulator for the Commodore 64, but it was actually for the Apple ][. I found the Commodore 64 (C64) Forum, and asked for assistance in locating an online emulator that would allow me to compare the C64 variant to the others. I received great assistance from the users known as Rekrul, didi_lxt and merman. With their help I was introduced to the awesome C64 emulator named VICE (Versatile Commodore 8-bit Emulator). With it, and their help in locating a copy of the C64 variant of the game, I was set. I compared the C64 variant to all of the others.

The following table details the results of my comparisons:
puzzle 10  X=M=A=6<>C (1 wall block differs)
The XSokoban variant is the same as all Spectrum Holobyte variants. The Spectral Associates variant is different.
puzzles 11,12,20,25,37,47,50  X<>M=C=A=6
All Spectrum Holobyte variants and the Spectral Associates variant are the same. The XSokoban variant is different.
11 X<>M=C=A=6 (different start position)
12 X<>M=C=A=6 (1 wall block differs)
20 X<>M=C=A=6 (2 targets and 2 boxes differ)
25 X<>M=C=A=6 (2 wall blocks differ)
37 X<>M=C=A=6 (1 wall block differs)
47 X<>M=C=A=6 (different start position)
50 X<>M=C=A=6 (3 boxes in the upper-right, 1 wall block in the lower-right differ)
puzzle 23 X=M=C=A<>6 (different start position)
All variants are the same, except the Commodore 64 variant has a different start position.
puzzle 24 X=M=A=6<>C (different start position)
All variants are the same, except the Color Computer variant has a different start position.
puzzle 27 X=M=C=6<>A (different start position)
All variants are the same, except the Apple 2 variant has a different start position.
puzzle 42 X<>M<>6<>A=C (2 boxes in the lower-left differ in location)
This is the most interesting of the puzzles. The Spectral Associates variant is the same as the Spectrum Holobyte Apple ][ variant. The XSokoban and the Spectrum Holobyte variants for MS-DOS and the Commodore 64 are different from each other and from the Spectrum Holobyte Apple ][/Spectral Associates variants.
puzzles 1-9,13-19,21-22,26,28-36,38-41,43-46, 48-49  X=M=C=A=6
All variants are the same.
comparison data
X = XSokoban variant
C = Color Computer variant(Spectral Associates)
M = MSDOS variant(Spectrum Holobyte)
A = Apple ][ variant(Spectrum Holobyte)
6 = Commodore 64 variant(Spectrum Holobyte)
Bleeding Corner Puzzles (fixed in the Tribute files)
08Row 10, Col 01:
Commodore 64 and XSokoban variants have corner wall block missing in all other variants
10Row 16, Col 19:
Color Computer variant missing corner wall block that occurs in all other variants
36Row 13, Col 16:
All variants missing corner wall block
44Row 15, Col 19:
Color Computer variant missing corner wall block that occurs in all other variants

This data shows that while the XSokoban variant contains seven puzzles that differ from all official variants, there are a total of twelve puzzles that differ between variants, with one being unique to the Spectral Associates variant, one to the Spectrum Holobyte Commodore 64 variant, one to the Spectrum Holobyte Apple 2 variant, and the twelfth is divided up between the XSokoban variant, the Spectrum Holobyte MS-DOS variant, the Commodore 64 variant, and the Spectrum Holobyte Apple ][ and the Spectral Associates variants, which are the only two the same. This is clear evidence that modifying levels between variants was common, even among the many official variants that Thinking Rabbit/Falcon Co. Ltd. have licensed (http://www.sokoban.jp/ and click the fourth link down on the left for a incomplete list of licensed variants).

This ends the XSokoban Trail. I have drawn the following conclusions concerning the original Sokoban puzzles, as they are referred to by the Sokoban enthusiasts.

1. With all the variants that have been licensed by Thinking Rabbit, none of them contains the exact same fifty puzzles that were included in the Japanese release of the fifty level Sokoban game released in 1982. While they may all be derived from those fifty levels, each variant introduced its own variations of those fifty puzzles.

2. While the common conception is that the MS-DOS variant contains the "official originals", the fact is that the other two variants produced by the same company have alternate variations for at least one puzzle each. This proves that even the so-called original is not the original.

3. While these variants may not contain the exact same puzzles as the Japanese variant, they are still official releases, and as such may be considered as original for the purposes of connection back to Thinking Rabbit.

The Second Part of the Mystery

No, the mystery is not quite solved. There is still an original puzzle set that has not been compared, or even entered into the discussion. The Japanese fifty puzzle set is not within my reach to be able to compare to the puzzles listed above. I have emailed Thinking Rabbit/Falcon Co. Ltd. using a form on the official Sokoban site. I have not received any response from them as yet, but am still holding out hope that they will answer and bring more light to this subject.

In addition to the fifty, there is another, older original set. These puzzles are not the same as the fifty, but are (for the most part) included in the fifty. This set is the original twenty puzzles created by Hiroyuki Imabayashi in 1980 when he invented the Sokoban game. That version of the game was different from the version released in 1982. The puzzles were in a different order, some were larger than the 19x16 screen display required by the later version, and this version contained what were called "false walls". You had to find and use these "hidden passages" to solve the puzzle.

These puzzles are the true originals, and until they can be compared to any other incarnation of Sokoban, we will not solve the final mystery of the original puzzles. All that is documented about this version says that some puzzles were removed and some were modified to fit the new size format, and all of them were re-arranged as the replacements and new puzzles were added to the fifty puzzle version.

Comparing the Puzzles that Differed

I have included screen shots of the twelve puzzles that differed between the variants compared, and put them into a table so you can compare them side-by-side. The Variants Compared link contains this table.

The Variants Compared


Sokobans Compared

Of the 50 puzzles, 38 of them are identical in each variant compared. The remaining 12 puzzles have differences that seem trivial, but will actually determine the difficulty level for solving that puzzle. Using the table below, you can compare the different variants and see what the differences between them are.

Clicking an image will bring up a slide-show viewer and you can go through all of them sequentially.


Puzzle XSokoban MS-DOS Apple ][ Commodore 64 Tandy Color Computer
10
11
12
20
23
24
25
27
37
42
47
50