The Sokoban puzzle file format is designed with user-friendliness in mind. Unlike stricter formats like HTML or XML, it allows puzzles to be written in a way that's easy for people to share and understand. This simplicity comes at a cost, though. While the files are plain text, the logic behind reading them can get tricky for the programmer if not handled correctly.

This guide will demonstrate how to create a program that effectively parses these files. To complement the guide, a fully functional and efficient reference implementation of both a puzzle file reader and writer, written in Common Lisp, is available here. The Common Lisp code can easily be converted to other programming languages, and this process can even be partially automated.

Main Procedure

Key Observation:

One crucial concept to remember is that the program will encounter notes until it stumbles upon a puzzle board, a snapshot (an unsolved state of the puzzle), or a solution (a snapshot representing a completed puzzle). This observation forms the core of our program's structure, as reflected in the following pseudocode:

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     ... (more to come)

Prioritizing Notes:

At first glance, focusing on notes might seem strange since puzzle boards are the heart of the file. However, this approach has a significant advantage. Not only does the file begin with notes, but each puzzle and snapshot can have their own set of notes as well. This means that whenever we encounter a puzzle board or a snapshot, we need to grab any associated notes before moving on.

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     if found-puzzle-board? then
       puzzle := makePuzzle(puzzle-board)
       file.puzzles += puzzle
       puzzle.notes := readNotes()
       ... (more to come)
     else
       (found an orphaned snapshot)
       puzzle := makePuzzle(no board)
       file.puzzles += puzzle
       puzzle.snapshots += snapshot
       snapshot.notes := readNotes()

"Orphaned" Snapshots:

The reason we handle "orphaned snapshots" is because it's sometimes useful to load snapshots and solutions separately for further processing. A common scenario would be loading a file containing solutions (perhaps from the clipboard) to pair them with existing puzzles.

Recurring Pattern:

It's worth noting the repeated use of the "readNotes()" function right before the "while" loop restarts. We'll see this pattern again as we complete the main function by adding the logic to load snapshots associated with a specific puzzle.

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     if found-puzzle-board? then
       puzzle := makePuzzle(puzzle-board, optional-title)
       file.puzzles += puzzle
       puzzle.notes := readNotes()
       while found-snapshot?
         puzzle.snapshots += snapshot
         snapshot.title := optional-title
         snapshot.notes := readNotes()
     else
       (found an orphaned snapshot)
       puzzle := makePuzzle(no board)
       file.puzzles += puzzle
       puzzle.snapshots += snapshot
       snapshot.title := optional-title
       snapshot.notes := readNotes()
   post-processing, e.g., make titles unique and resistant to misinterpretation

Wrapping Up:

With these additions, our main function is complete! It's both straightforward and robust. We've also introduced the concept of optional titles for puzzles and snapshots. These titles are essentially header lines from the text file, and the "readNotes()" function is responsible for differentiating them from regular notes belonging to the preceding element.

As you can see, the "readNotes()" function carries a significant responsibility. However, this modular approach keeps the code well-organized and easy to manage.

Notes Text Lines

Now, let's take a closer look at the "readNotes()" function.

 function readNotes()
   ... (initialize return values)
   collect notes text lines until encountering:
     1. a puzzle board
     2. a snapshot
     3. the end of the file
 
   ... (more to come)

As you can see, the function accumulates text lines until it encounters one of three conditions: a puzzle board, a snapshot, or the end of the file.

Title Line Detection:

The slightly tricky part for "readNotes()" is identifying a potential title line preceding the next puzzle board or snapshot. Here's the key: we discard trailing blank lines, but at first, we need to keep initial blank lines. This distinction plays a role in determining whether a line is interpreted as a title or simply part of the notes.

Imagine these two scenarios:

• Scenario 1 (No Title Line):

 I am a notes text line
 I am a notes text line too

• Scenario 2 (With Title Line):

 I am a notes text line
 [blank line]
 I am the title of the next puzzle or snapshot, if any

In the second scenario, the blank line separates the notes from the title line.

Complete Implementation:

The complete implementation of "readNotes()" is shown below. The description includes all the necessary details, allowing for a straightforward translation into your preferred programming language.

 function readNotes()
   initialize return values:
     notes, puzzle-board, snapshot, run-length-encoded-snapshot?, and optional-title
 
   collect notes text lines until encountering:
     1. a puzzle board
     2. a snapshot
     3. the end of the file
   
   trim notes text lines by removing:
     - leading ">" characters followed by a space (email-style quoting)
     - trailing spaces, tabs, and other control characters
 
   discard trailing blank lines (empty lines at the end)
 
   if a puzzle board or snapshot is found:
     if there are notes lines:
       and (only one line exists in the notes
           or the second-to-last line in the notes is blank)
       then
         optional-title := the last line in notes
         discard the last line in notes
         discard trailing blank lines
   
   discard leading blank lines (empty lines at the beginning)

Board Text Lines

Several key points need to be considered when finding puzzle boards:

1. Run-length encoding: A single line can represent multiple board rows.
2. Validation criteria: To distinguish actual puzzle boards from notes that resemble them, the program checks for specific characteristics:

• Structure: The first non-empty column in each row must contain a wall or a box on a goal. This ensures a minimum level of structure, making puzzle boards easier to locate, especially in large files.
• Minimum size: The board must have at least three rows and three columns.
• Empty rows: Empty rows are used for decoration and should only appear within the board, not at the beginning or end.

Here's the process the program follows:

• Tentative collection: When encountering a line that might contain puzzle rows, the program initially collects that line along with all subsequent lines that also seem like puzzle rows.
• Validation: The program then analyzes the collected lines to determine if they actually form a valid puzzle board. If not, or if the "tail" ends with an empty row (which is invalid), the program puts as many of the collected lines back on the queue as necessary, so they will be treated as notes.

It's important to note that this validation focuses solely on the structure of the board. Whether the puzzle is well-formed (e.g., has a player, matching boxes and goals) is only checked when a user attempts to solve it.

Function Implementation:

The "boardLines?()" function, despite its name, actually returns the identified puzzle rows rather than a simple true/false value. Here's the pseudocode:

 function boardLines?()
   if the current text line contains board rows and
      the first of these rows isn't empty then
     collect text lines until encountering:
       1. a text line that doesn't contain board rows
       2. the end of the file
 
     while the last found board row is empty
       discard the board rows found in the last collected text line
       put the last collected text line back on the queue (treat it as a notes text line)
   
     if the collected board rows live up to the minimum size criteria then
       return the collected board rows, left-justified
     else
       put all collected text lines back on the queue (treat them as notes)

Snapshot Moves Text Lines

There's a key distinction between identifying puzzle board rows and snapshot moves:

• Puzzle board rows: Run-length decoding is essential to accurately determine the content of individual rows due to the potential for compressed data within a single line.
• Snapshot moves: Finding snapshot moves is simpler and doesn't require run-length decoding initially. However, when we perform run-length decoding at a later stage, it's important to note that it can span multiple lines. This is in contrast to board text lines, which are always decoded one line at a time. This flexibility allows for cleaner snapshot storage with a straight right margin in the text file.

Function Implementation:

The "snapshotLines?()" function, similar to "boardLines?()", returns the actual snapshot lines rather than a simple true/false value. Here's the pseudocode:

 function snapshotLines?()
   collect text lines with moves until encountering:
     1. a line that doesn't contain moves
     2. the end of the file

We're nearing the completion of these functions! We've defined the "plural" functions ("boardLines?()" and "snapshotLines?()") that handle collections of lines. Now, let's explore their corresponding "singular" counterparts, which examine a single line at a time.

Board Text Line

The "boardLine?()" function has two key distinctions:

1. Arguments: Unlike prior functions, it can accept an argument beyond just the current text line. This allows us to call the function recursively.
2. Return Value: Upon successful decoding, it returns a list containing multiple board rows, not just a single row.

Function Implementation:

Here's the pseudocode for "boardLine?()":

 function boardLine?( text )
   trim leading ">" characters (email-style quoting)
   if the text contains only legal board characters then
     if the text is run-length encoded then
       decode the text
       trim one trailing "|" and then split on "|"
       for each text section:
         call boardLine?( text-section )
       if all text sections pass the test then
         return the decoded text sections as board rows
     else
       (the text isn't run-length encoded)
       return a list with the trimmed text as one board row

Explanation:

The function first checks if the line contains only valid board characters. If so, it then determines if the data is run-length encoded. If it is, the function decodes it, splits it into sections (representing individual board rows), and recursively calls itself on each section for further validation. Finally, if all sections pass the test, the decoded text sections are returned as a list of board rows.

Snapshot Moves Text Line

The "snapshotLine?()" function should not perform run-length decoding. Instead, it has another speciality: it returns two values:

1. Snapshot moves: These moves might be run-length encoded.
2. A "run-length encoded?" flag: This indicates whether the returned moves are indeed run-length encoded.

If a snapshot contains one or more run-length encoded lines, the "snapshotLines?()" function (which calls "snapshotLine?()") can then optionally perform a decoding of the entire snapshot.

Function Implementation:

Here's the pseudocode for "snapshotLine?()":

 function snapshotLine?( text )
   trim leading ">" characters (email-style quoting)
   if the text contains only legal snapshot characters and
      the text contains at least one move (a direction character) then
     return two values:
       1. the trimmed text as snapshot moves
       2. run-length encoded moves?

Explanation:

The function verifies that the line represents a valid sequence of snapshot moves. If the line is valid, the function returns two values:

1. Snapshot moves: This is the trimmed text representing the actual moves within the snapshot.
2. A "run-length encoded?" flag: This value indicates whether the returned moves are run-length encoded.

The flag value can be used later by "snapshotLines?()" to determine if any decoding is necessary. In other words, "snapshotLines?()" can use this flag to decide whether to decode the entire snapshot, in case some of the lines within the snapshot contain run-length encoded moves.

Utility Functions

Here's a final noteworthy utility function:

make-interpretation-resistant-title( title ): This function addresses a potential issue where a title line preceding a puzzle or snapshot could be mistakenly interpreted as part of a puzzle or snapshot itself. For example, titles like "Dull" or "Rud" might cause confusion.

The function ensures clarity by enclosing such titles in quotation marks. Here's the pseudocode:

 function make-interpretation-resistant-title( title )
   if boardLine?( title ) or snapshotLine?( title ) then
     return the title enclosed by quotation marks
   else
     return the title

Conclusion

With this, we've reached the end of our guide! The functions for run-length decoding and its counterpart for run-length encoding are implemented in the accompanying Common Lisp program and won't be covered here.

If you would like to support other cases, such as when much or all of the meta-data appears before the puzzle, then you likely will need to implement a more complex heuristic for determining which non-puzzle data belongs to each puzzle. SokoSave Mobile takes this approach, trying very hard to intuit which information belongs with which puzzle, since many older collections are formatted in ways not compatible with the .sok format. To do this, SokoSave Mobile implements heuristics based directly on the SokoSplit utility (with a few small bug fixes): http://www.high-speed-software.com/sokosave/sokosavedesktop/sokosplit/

Here is a brief description of the heuristic. For each puzzle, perform the following steps in order:

1. If there is a blank line immediately before the puzzle, assign it to the puzzle.

2. Assign all following unassigned non-blank lines to the puzzle.

3. Assign all preceding unassigned non-blank lines to the puzzle. These lines precede the blank line (if present) assigned to the puzzle in step 1.

4. Assign all following unassigned lines (blank or not) to the puzzle.

5. Optional: Clean up by trimming leading and trailing blank lines from the collected meta-data. (Internal blank lines are retained.)

This heuristic works correctly with all of the old puzzle collections I have sitting around which were downloaded years ago, as well as with modern collections available for download. The heuristic also is a superset of the YASC .sok parsing, so it works properly with those collections, as well.