Terms
field - the level, whole playing area of the current game.
position - a phase, set-up in the field.
final position - a position in which no turn is possible - either the goal or a deadlock.
box - same as crate.
Theory
Just a little bit of logic - it seems obvious but we'll use it in the implementation part.
So - about every game of Sokoban, we can say that it is one of these:
- solvable, unsolved - in the process of solving
- solvable, solved - the goal
- unsolvable, unsolved - if our implementation yields no results, and there are no more possible moves / combinations of moves
Now - a Sokoban game consists of turns that are:
- moves - the character can move in an area defined by walls and/or boxes, this area is smaller or equal (if not counting the walls, and there are no boxes) to the whole playing area - however, moving the character around the field makes no difference except score, which is irrelevant for the actual solution - let's ignore it for now
- pushes - pushing the boxes is much more important, and can potentially lead to our goal - solving the field - by pushing the boxes at their respective goals
A box can be:
- in-goal - most likely this box does not need to be moved, and some rules can prohibit a box from moving when at a goal position (very unusual)
- pushable - in 1 to 4 directions
- unpushable, not at goal
- blocked by 2 walls - the current position is unsolvable no matter what
- other - we will get to this box later - for now a crate stands in our way
Process
This is the step-by-step process we will use in solving (definitions underneath):
- populate possibleTurnsn with every directly accessible push (pushable or in-goal) in the current position, with player at the current place
- take the first item in possibleTurnsn, remove it and execute it
- see if the current position:
- is final - goal - solved, do not do anything
- is final - deadlock - this turn led to a deadlock, don't populate it anymore, go back to 2. step, n stays the same
- is not final - increment n and populate possibleTurnsn with possible turns in this position
Definitions:
possibleTurnsx - a two dimensional array, or an array of arrays - the x defines the "depth" of the turns
n - in the beginning is zero, will be incremented in the execution of the algorithm above
Tips
Finally - the process above will leave you with a combination of turns that will leave to a solved position. Last thing to do is to use an algorithm like A* to determine the shortest route between these turns / pushes, to maximize the speed and score, minimize number of in-game turns.