📦 Sokoban Solver and Generator

🗒️ README pt-BR

▶️ Video showing the game mechanics, the generator and the solver: Sokoban Generator and Solver

This is a Sokoban puzzle generator and solver that uses BFS, A* and Dijkstra search algorithms.

Sokoban is a puzzle game in which the player pushes boxes around in a warehouse, trying to get every box to a goal.

➡️ Setup

pip install -r requirements.txt

python -m sokoban

❕Sokoban Puzzle

The puzzle states are stored in a matrix, and each element of the puzzle is represented by a single character in the matrix.

+ + + + + + +
+ * - @ - X +
+ + - @ - + +
+ X - - - $ +
+ + + + + + +

* - The player
% - The player on a goal
@ - A box
X - A goal
$ - A box on a goal
+ - A wall
- - An empty position

A box on a goal will have its color changed to green on the game window.

❕Sokoban Generator

A pseudo-random valid puzzle will be generated by using the Random button on the sidebar. Entering a valid seed number (1-99999) before using the Random button will generate a puzzle using the specified seed.

The generator will initially create a puzzle with a random board size, then the player and the boxes on goals will be randomly placed on the board. The player will only be able to pull boxes from their positions during the generation of a puzzle, breaking every wall on his way, so it is guaranteed that the puzzle will have a valid solution.

❕ Sokoban Solver

The algorithms used to implement the Sokoban puzzle solvers were Breadth-First Search(BFS) and A*.

The BFS solver uses a queue to store the next states of the puzzle it needs to visit. A visited state is stored in a hashset, and BFS won't try to visit the same state twice.

The A* algorithm is similar to the BFS algorithm, but it uses a priority queue instead of a queue, and it prioritizes moves that are more likely to solve the problem. It does so by setting costs to the puzzle state and the player's movements, punishing the player with high costs for a bad move and rewarding the player with lower costs for a good move. The state costs are defined by heuristic functions, and this solver was implemented with two different heuristics: the Manhattan Distance function and Dijkstra distance function.

All three implementations check for possible deadlocks (states that are impossible to solve) before adding the new state to the queue.

❕ Interface Buttons and Options

• Restart Reset the current level to its initial state
• Seed Specify a seed to be loaded with the Random button
• Random Generate a pseudo-random valid puzzle
• Solve BFS Solve the current puzzle using Breadth-First Search
• A* Manhattan Solve the current puzzle using A* with Manhattan Distance heuristic
• Dijkstra Solve the current puzzle using A* with Dijkstra distance heuristic
• Visualize Display the process of generating the puzzle and show the current best path for the solutions

❕ Unit Tests

All unit tests are stored in the /tests directory, separated by categories in different classes and files. Use pytest to run all unit tests at once.

More about Sokoban: Wikipedia Article