Puzzle format

From Sokoban Wiki

(Difference between revisions)
Jump to: navigation, search
m (Circular levels)
m (Sok format description)
 
(33 intermediate revisions not shown)
Line 1: Line 1:
-
= Level =
+
= Puzzle =
-
The most commonly used format for representing a level of Sokoban is:
+
The most commonly used format for representing a Sokoban puzzle is:
{| class="soko-table feature-list"
{| class="soko-table feature-list"
-
!Level element         || Character || ASCII Code
+
!Puzzle element         || Character || ASCII Code
|-
|-
|Wall                  || #        || 0x23
|Wall                  || #        || 0x23
Line 21: Line 21:
|}
|}
-
The simplest solvable level looks like this:
+
The simplest solvable puzzle looks like this:
<pre>#####
<pre>#####
Line 28: Line 28:
</pre>
</pre>
-
It's important that the whole level is surrounded by walls (<code>#</code>).
+
It's important that the whole puzzle is surrounded by walls (<code>#</code>).
-
This means assumed all boxes are removed from the board the player musn't be able to get to the border of the level. Hence a level like this can't be loaded by most of the Sokoban programs:
+
This means - assumed all boxes are removed from the board - the player musn't be able to get to the border of the puzzle. Hence a puzzle like this can't be loaded by most of the Sokoban programs:
[[Image:example non closed level.png]]
[[Image:example non closed level.png]]
-
The player can reach the right border of the level, since the level is not "closed".
+
The player can reach the right border of the puzzle, since the puzzle is not "closed".
 +
 
 +
 
 +
== Formats not all programs support ==
During the years some Sokoban programs have added support for Sokoban formats that aren't supported by many old programs.
During the years some Sokoban programs have added support for Sokoban formats that aren't supported by many old programs.
-
== Circular levels ==
+
=== Circular puzzles ===
-
Circular levels are levels that start in the end position.  
+
Circular puzzles are puzzles that start in the end position.  
-
Example:  
+
 
-
2x2 Cyclic by DrFogh
+
Example puzzle:
[[Image:example circular level.png]]
[[Image:example circular level.png]]
-
Due to design issues it's also allowed to have boxes in a level which can never be reached by the player. In these cases the boxes MUST be located on a goal. Example level:
+
The Sokoban implementing this puzzle type must ensure that at least one push must be made to report "solved" for such puzzles.
 +
 
 +
Note:<br>
 +
When implementing a solver it's important to implement a special logic for such puzzles.
 +
 
 +
Usually a solver avoids duplicate states (= all boxes at the same positions and the player has the same reachable positions).
 +
 
 +
However, in circular puzzles it is important that the initial state must be reacheable again.
 +
 
 +
=== Puzzles with decorative outside elements ===
 +
 
 +
Some puzzles have walls, boxes and goals outside the player reachable area to create a better look.
 +
 
 +
An example level is "Sasquatch 01 / Level 41":
 +
 
 +
[[Image:level with outside elements.png]]
 +
 
 +
The boxes on the left side can't be reached by the player.  
 +
The whole left area is just there to for a decorative purpose.
 +
 
 +
Some programs support loading and playing these puzzles.
 +
 
 +
In case the outside elements are not all boxes on goals it's unclear what to do.
 +
Some programs refuse to load such puzzles since the number of goals and boxes does not match.
 +
However, other programs just consider and count the '''reachable''' boxes and goals and ignore the other boxes/goals.
 +
 
 +
=== Interior empty rows ===
 +
 
 +
Some puzzles look better having interior empty rows.
 +
 
 +
An example is the puzzle "Steaming Hot" by David Buchweitz.
 +
 
 +
[[Image:example interior empty rows.png]]
 +
 
 +
Note:
 +
Since in the sok format an empty line is used to separate puzzle, solutions, snapshots, ... such interior empty rows can't be written as an empty line.
 +
 
 +
Hence, the rule for is: "An empty interior row is written with at least one "-" or "_".
 +
 
 +
The puzzle "Steaming Hot" can therefore be stored in a txt file like this:
 +
 
<pre>
<pre>
-
*###* <- two boxes on goal that can never be reached by the player
+
 
-
#@$.#
+
  #     #
-
*###* <- two boxes on goal that can never be reached by the player
+
#
 +
  # #  #
 +
  # #  #
 +
  #  #  #
 +
#  #  #
 +
  # #  #
 +
-
 +
##########
 +
#........####
 +
# $$$$$$$#  #
 +
#.$......#
 +
# $$$$$$ # #
 +
#......$+#
 +
#$$$$$$$ #  #
 +
#        ####
 +
##########
</pre>
</pre>
-
If these extra boxes are not located on a goal the level is invalid. Example invalid level:
+
 
-
<pre>
+
 
-
########
+
=== Not closed puzzles ===
-
#@$.#$.#
+
 
-
########
+
Some websites and programs also allow puzzles that aren't surrounded by walls.
-
</pre>
+
The player can move to the border of such puzzles but not further.  
-
It depends on the program the level is loaded with how this situation is handled:
+
 
-
* some programs refuse to load such a level
+
In extreme cases, such a puzzle doesn't have any walls at all.
-
* some programs load this level but it's not possible to solve it
+
 
-
* some programs can load this level as "normal" level for playing
+
An example is the puzzle "No walls" created by Rincewind:
 +
 
 +
[[Image:example interior no walls level.png]]
 +
 
 +
This puzzle type is just supported by very few Sokoban implementations and not the standard!
 +
There are just a few puzzles of this type.
= Solution =
= Solution =
-
A solution of a level is represented by the moves of the player. The player can move up, down, left or right. Hence, the letters for these directions are: u, d, l, r. &rArr; [[Solution format]]
+
A solution to a puzzle is represented by the player's moves. The player can move up, down, left or right. Therefore, the letters for these directions are: u, d, l, r.
-
A possible solution string may look like this:  
+
A possible solution string might look like this:  
<code>DDrdrruLruLLDllU</code>
<code>DDrdrruLruLLDllU</code>
-
The capitals in this solution show that a box is pushed as the player moves. Usually this information is stored in a solution, too, although the solution is still correct if all letters are lowercase. <br>
+
 
-
Note: Although it's common to use the letters ('''n''')orth, ('''s''')outh, ('''e''')ast and ('''w''')est in other games the letters u, d, l and r have been become a standard for Sokoban directions. The letters n and s are instead used for the additional directions in the Sokoban variations Hexoban and Trioban, and n, s, e, and w are needed for additional Octoban directions.
+
The uppercase letters in this solution indicate that a box is being pushed as the player moves.
 +
Usually, this information is also stored in a solution, although the solution is still correct if all letters are lowercase.
 +
 
 +
Note: Although it's common to use the letters ('''n''')orth, ('''s''')outh, ('''e''')ast and ('''w''')est in other games, the letters u, d, l, and r have become the standard for Sokoban directions. The letters n and s are used instead for the additional directions in the Sokoban variations Hexoban and Trioban, and n, s, e and w are used for the additional directions in Octoban.
 +
 
 +
 
 +
Some programs allow playing a puzzle in reverse mode.
 +
The puzzle is displayed having all boxes at goals and the player can pull the boxes.
 +
This way it's sometimes easier to determine the push sequence needed to solve a puzzle at the end when forward playing (-> pushing the boxes).
 +
 
 +
Reverse solutions and snapshots must start with: []
 +
Hence, a valid reverse solution for this puzzle:
 +
 
 +
[[Image: example reverse solution.png]]
 +
 
 +
would be: []urLdrLdrLdrL
 +
 
 +
Note that in a reverse solution the pulls must be written with capital letters.
 +
 
 +
Since the player may be in different areas at the end of the puzzle the start position in reverse mode is not known when reverse mode is used.<br>
 +
It's therefore possible for the player to "jump" to the start position before the first pull is made.
 +
 
 +
For instance in this example puzzle:
 +
 
 +
[[Image: example jump moves.png]]
 +
 
 +
the player starts at a goal.<br>
 +
Since reverse mode starts with all boxes on a goal the player would start "above" a box.<br>
 +
Hence, the player must "jump" to any valid start position (= a square without a wall and box).
 +
 
 +
The jump moves must be written inside the brackets.
 +
A valid reverse solution for that puzzle with initial jump moves is:
 +
[dr]RulUrddllldLuuurLdrLdrrrDluLL
= Snapshot =
= Snapshot =
-
It's also possible to save moves of the player even if they don't constitute a solution for the level. In this case these moves are called "snapshot". The only differences between a solution and a snapshot is the fact that the moves of a snapshot don't result in a solved state of the level.
+
It's also possible to save moves of the player even if they don't constitute a solution for the puzzle.<br>
 +
In this case these moves are called "snapshot". <br>
 +
The only differences between a solution and a snapshot is the fact that the moves of a snapshot don't result in a solved state of the puzzle.
 +
 
 +
= Puzzle collection =
 +
Many authors publish several puzzles as a collection of puzzles.
 +
 
 +
Such a collection is named, for instance "Sokoban Perfect".
 +
 
 +
Usually all puzzles contained in this collection are then referred to as "the Sokoban Perfect puzzles".<br>
 +
 
 +
A specific puzzle of this puzzle collection is specified by adding the number of the puzzle in that collection after the collection name.
 +
 
 +
For instance to refer to the 10th puzzle of the collection "Sokoban Perfect" one can write: "Sokoban Perfect #10" or simply "Sokoban Perfect 10".<br>
 +
In the case the puzzles don't have own titles they are just numbered (1, 2, 3, ...)
 +
However, some authors also named their puzzles.
 +
 
 +
= Puzzle file format =
 +
There exist various file formats for storing the data of a puzzle / puzzle collection.
 +
The most common file extensions are: ''.sok'', ''.xsb'' and ''.txt'' <br>
-
= Level collection =
+
Every file format stores the data in a different way.  
-
Many authors publish several levels as a collection of levels. This collection is named, for instance "Sokoban Perfect". Usually all levels contained in this collection are then referred to as "the Sokoban Perfect levels".<br>
+
Some store all data in just one file and others store different data in different files (for instance the solutions may be saved in extra files for every puzzle). <br><br>
-
A specific level of this level collection is specified by adding the number of the level in that collection after the collection name. For instance to refer to the 10th level of the collection "Sokoban Perfect" one can write: "Sokoban Perfect #10" or simply "Sokoban Perfect 10".<br>
+
-
In the case the levels don't have own titles they are just numbered (1, 2, 3, ...) However, some authors also named their levels.
+
-
= Level file format =
+
The widely used .sok-format is described [[sok format|here]], including a detailed description of how to implement a program that can read the format.
-
There exist various file formats for storing the data of a level / level collection. The most common file extensions are: ''.sok'', ''.xsb'' and ''.txt'' <br>
+
-
Every file format stores the data in a different way. Some store all data in just one file and others store different data in different files (for instance the solutions may be saved in extra files for every level). <br>
+
-
The often used .sok-format is described here: [[sok format]]
+
= Run length encoding =
= Run length encoding =
The XSB format with RLE (run-length-encoding), is more compact and efficient in mobile devices (as Palm, PocketPC, Smart Phones), besides being smaller to send for SMS.
The XSB format with RLE (run-length-encoding), is more compact and efficient in mobile devices (as Palm, PocketPC, Smart Phones), besides being smaller to send for SMS.
-
It can be used for both: levels and solutions.
+
It can be used for both: puzzles and solutions.
In this format digits show how many elements of the same type are following.
In this format digits show how many elements of the same type are following.
  #### becomes 4#
  #### becomes 4#
-
This level ("Claire", by Lee J Haywood):
+
This puzzle ("Claire", by Lee J Haywood):
  #######
  #######
Line 105: Line 214:
  7#|#.@-#-#|#$*-$-#|#3-$-#|#-..--#|#--*--#|7#
  7#|#.@-#-#|#$*-$-#|#3-$-#|#-..--#|#--*--#|7#
-
The rows of the level are separated by "|"s.
+
The rows of the puzzle are separated by "|"s.
There has been a discussion in the [http://games.groups.yahoo.com/group/sokoban/ Yahoo Group] about what character should represent an empty square in May 2006. Finally the hyphen has been elected to be the standard character for an empty square. Nevertheless, programs are encouraged to support both, hyphens and underscores.
There has been a discussion in the [http://games.groups.yahoo.com/group/sokoban/ Yahoo Group] about what character should represent an empty square in May 2006. Finally the hyphen has been elected to be the standard character for an empty square. Nevertheless, programs are encouraged to support both, hyphens and underscores.
-
If only two level elements are grouped together they may be run length encoded, but needn't to.
+
If only two puzzle elements are grouped together they may be run length encoded, but needn't to.
Example:
Example:
  $$ may keep $$ or be encoded as 2$
  $$ may keep $$ or be encoded as 2$
Line 116: Line 225:
In the RLE format empty squares at the end of a row should be omitted.<br>
In the RLE format empty squares at the end of a row should be omitted.<br>
-
For example, this level:<br>
+
For example, this puzzle:<br>
  ###<span style="color:#FF3030;">'''__'''</span>  <- two empty squares / spaces at the end of the row
  ###<span style="color:#FF3030;">'''__'''</span>  <- two empty squares / spaces at the end of the row
Line 127: Line 236:
  <span style="color:#FF3030;">'''3#'''</span>|#.3#|#*$-#|#--@#|5#
  <span style="color:#FF3030;">'''3#'''</span>|#.3#|#*$-#|#--@#|5#
-
= Exchange of Sokoban levels in Emails =
+
= Exchange of Sokoban puzzles in e-mails =
-
Many e-mail servers strip empty spaces and multiple spaces, too. To ensure the levels can be imported to the email recipients properly here are some suggestions:
+
Many e-mail servers strip empty spaces and multiple spaces, too.  
 +
To ensure the puzzles can be imported to the email recipients properly here are some suggestions:<br>
Replace all spaces by hyphens "-" (preferred) or underscores "_".
Replace all spaces by hyphens "-" (preferred) or underscores "_".
-
(Recipients of your mail will have to transpose them back to spaces in order to import the levels into their Sokoban programs, although, some Sokoban programs will perform this transposition automatically.)
+
 
 +
(Recipients of your mail will have to transpose them back to spaces in order to import the puzzles into their Sokoban programs, although, some Sokoban programs will perform this transposition automatically.)
 +
 
 +
 
 +
= Sok format description =
 +
 
 +
There is a dedicated page explaining the widely used [[sok format|Sok-format]] and its implementation in computer programs.

Current revision as of 09:19, 23 June 2024

Contents

Puzzle

The most commonly used format for representing a Sokoban puzzle is:

Puzzle element Character ASCII Code
Wall # 0x23
Player @ 0x40
Player on goal square + 0x2b
Box $ 0x24
Box on goal square * 0x2a
Goal square . 0x2e
Floor (Space) 0x20

The simplest solvable puzzle looks like this:

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

It's important that the whole puzzle is surrounded by walls (#).

This means - assumed all boxes are removed from the board - the player musn't be able to get to the border of the puzzle. Hence a puzzle like this can't be loaded by most of the Sokoban programs:

Image:example non closed level.png

The player can reach the right border of the puzzle, since the puzzle is not "closed".


Formats not all programs support

During the years some Sokoban programs have added support for Sokoban formats that aren't supported by many old programs.

Circular puzzles

Circular puzzles are puzzles that start in the end position.

Example puzzle:

Image:example circular level.png

The Sokoban implementing this puzzle type must ensure that at least one push must be made to report "solved" for such puzzles.

Note:
When implementing a solver it's important to implement a special logic for such puzzles.

Usually a solver avoids duplicate states (= all boxes at the same positions and the player has the same reachable positions).

However, in circular puzzles it is important that the initial state must be reacheable again.

Puzzles with decorative outside elements

Some puzzles have walls, boxes and goals outside the player reachable area to create a better look.

An example level is "Sasquatch 01 / Level 41":

Image:level with outside elements.png

The boxes on the left side can't be reached by the player. The whole left area is just there to for a decorative purpose.

Some programs support loading and playing these puzzles.

In case the outside elements are not all boxes on goals it's unclear what to do. Some programs refuse to load such puzzles since the number of goals and boxes does not match. However, other programs just consider and count the reachable boxes and goals and ignore the other boxes/goals.

Interior empty rows

Some puzzles look better having interior empty rows.

An example is the puzzle "Steaming Hot" by David Buchweitz.

Image:example interior empty rows.png

Note: Since in the sok format an empty line is used to separate puzzle, solutions, snapshots, ... such interior empty rows can't be written as an empty line.

Hence, the rule for is: "An empty interior row is written with at least one "-" or "_".

The puzzle "Steaming Hot" can therefore be stored in a txt file like this:


  #      #
 #   #  #
  # #  #
   # #  #
  #   #  #
 #   #  #
  # #  #
-
##########
#........####
# $$$$$$$#  #
#.$......#  #
# $$$$$$ #  #
#......$+#  #
#$$$$$$$ #  #
#        ####
##########


Not closed puzzles

Some websites and programs also allow puzzles that aren't surrounded by walls. The player can move to the border of such puzzles but not further.

In extreme cases, such a puzzle doesn't have any walls at all.

An example is the puzzle "No walls" created by Rincewind:

Image:example interior no walls level.png

This puzzle type is just supported by very few Sokoban implementations and not the standard! There are just a few puzzles of this type.

Solution

A solution to a puzzle is represented by the player's moves. The player can move up, down, left or right. Therefore, the letters for these directions are: u, d, l, r.

A possible solution string might look like this: DDrdrruLruLLDllU


The uppercase letters in this solution indicate that a box is being pushed as the player moves. Usually, this information is also stored in a solution, although the solution is still correct if all letters are lowercase.

Note: Although it's common to use the letters (n)orth, (s)outh, (e)ast and (w)est in other games, the letters u, d, l, and r have become the standard for Sokoban directions. The letters n and s are used instead for the additional directions in the Sokoban variations Hexoban and Trioban, and n, s, e and w are used for the additional directions in Octoban.


Some programs allow playing a puzzle in reverse mode. The puzzle is displayed having all boxes at goals and the player can pull the boxes. This way it's sometimes easier to determine the push sequence needed to solve a puzzle at the end when forward playing (-> pushing the boxes).

Reverse solutions and snapshots must start with: [] Hence, a valid reverse solution for this puzzle:

Image: example reverse solution.png

would be: []urLdrLdrLdrL

Note that in a reverse solution the pulls must be written with capital letters.

Since the player may be in different areas at the end of the puzzle the start position in reverse mode is not known when reverse mode is used.
It's therefore possible for the player to "jump" to the start position before the first pull is made.

For instance in this example puzzle:

Image: example jump moves.png

the player starts at a goal.
Since reverse mode starts with all boxes on a goal the player would start "above" a box.
Hence, the player must "jump" to any valid start position (= a square without a wall and box).

The jump moves must be written inside the brackets. A valid reverse solution for that puzzle with initial jump moves is: [dr]RulUrddllldLuuurLdrLdrrrDluLL

Snapshot

It's also possible to save moves of the player even if they don't constitute a solution for the puzzle.
In this case these moves are called "snapshot".
The only differences between a solution and a snapshot is the fact that the moves of a snapshot don't result in a solved state of the puzzle.

Puzzle collection

Many authors publish several puzzles as a collection of puzzles.

Such a collection is named, for instance "Sokoban Perfect".

Usually all puzzles contained in this collection are then referred to as "the Sokoban Perfect puzzles".

A specific puzzle of this puzzle collection is specified by adding the number of the puzzle in that collection after the collection name.

For instance to refer to the 10th puzzle of the collection "Sokoban Perfect" one can write: "Sokoban Perfect #10" or simply "Sokoban Perfect 10".
In the case the puzzles don't have own titles they are just numbered (1, 2, 3, ...) However, some authors also named their puzzles.

Puzzle file format

There exist various file formats for storing the data of a puzzle / puzzle collection. The most common file extensions are: .sok, .xsb and .txt

Every file format stores the data in a different way. Some store all data in just one file and others store different data in different files (for instance the solutions may be saved in extra files for every puzzle).

The widely used .sok-format is described here, including a detailed description of how to implement a program that can read the format.

Run length encoding

The XSB format with RLE (run-length-encoding), is more compact and efficient in mobile devices (as Palm, PocketPC, Smart Phones), besides being smaller to send for SMS. It can be used for both: puzzles and solutions.

In this format digits show how many elements of the same type are following.

#### becomes 4#

This puzzle ("Claire", by Lee J Haywood):

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

runlength encoded looks like this:

7#|#.@-#-#|#$*-$-#|#3-$-#|#-..--#|#--*--#|7#

The rows of the puzzle are separated by "|"s. There has been a discussion in the Yahoo Group about what character should represent an empty square in May 2006. Finally the hyphen has been elected to be the standard character for an empty square. Nevertheless, programs are encouraged to support both, hyphens and underscores.

If only two puzzle elements are grouped together they may be run length encoded, but needn't to. Example:

$$ may keep $$ or be encoded as 2$

It's recommended to write run-length encoded boards in a single line because currently some programs may not be able to handle RLE-boards spanning multiple lines. Most of the editor programs (for instance "notepad" in Windows) have a automatic wrapping of lines so there is no need for manually creating new lines. However, when a RLE board spans multiple lines, the trailing "|" on each line may be omitted.

In the RLE format empty squares at the end of a row should be omitted.
For example, this puzzle:

###__  <- two empty squares / spaces at the end of the row
#.###
#*$ #
# @ #
#####

Should be RLE this way:

3#|#.3#|#*$-#|#--@#|5#

Exchange of Sokoban puzzles in e-mails

Many e-mail servers strip empty spaces and multiple spaces, too.

To ensure the puzzles can be imported to the email recipients properly here are some suggestions:
Replace all spaces by hyphens "-" (preferred) or underscores "_".

(Recipients of your mail will have to transpose them back to spaces in order to import the puzzles into their Sokoban programs, although, some Sokoban programs will perform this transposition automatically.)


Sok format description

There is a dedicated page explaining the widely used Sok-format and its implementation in computer programs.

Personal tools