Level Identity

Here is a description of algorithms that calculates an identity for a given Sokoban level. There are two types of identities. The Unique-Id and the Exact-Id. Both are based only on the playable part of the level. Try the LEVEL IDENTITY CALCULATOR on your own level.

• Unique-Id is independent of rotations and mirroring and of the initial position of the man. Unique-Id can be used to determine if two levels are duplicates or not.
• Exact-Id is based on the exact layout of the playable part of the level. Exact-Id can be used to match a solution with a level.

1  Fill the playable area of the level. Start at the "man" position and recursively fill neighbouring squares until you hit a wall. The result is shown in red here.

2  Fill with walls. Change every square that is not marked, to wall. This eliminates everything outside the playable area.

3  Reduce walls. Make the four outer walls exactly one unit thick at its thinnest.                                                              

4  Now the level is ready for the Unique-Id calculation.                                                                               

5  Encode the level, using the usual characters ( $@#.+*). Each line must be terminated with newline (hex 0A).

#	Wall	$	Package
space	Floor	.	Goal
*	Package on Goal	@	Sokoban
+	Sokoban on Goal

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

6  Calculate an MD5 message digest of the string from step 5. The calculated sum is 32 characters long, but only the first 16 are used. MD5 is available in most programming and scripting languages.The specification can be found here RFC 1321. The result in this example is: 4C58C6973860C790.

7  To calculate the Unique-Id, put the man in every possible position that can be reached from the initial position without pushing any balls. This is done since this move is a trivial variation of the original level.

8  Rotate and mirror the level in all possible combinations and repeat steps 5 and 6. This produces eight different MD5 sums. Final step is to select the numerically smallest of the eight sums. In this case the level identity is: 1674E2D1AC70B61C.

Try the LEVEL IDENTITY CALCULATOR.

Note that there is a (very) slight risk that two totally different levels will produce the same identity.

49E47127B88A5490
B26AE7764B4984C1
1BC4A18F1B91726C
B1BEE44D8D44F8DC
1674E2D1AC70B61C
9745BF55B27DC965
28573C1F952FD18A
60598C834B8313D0