KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#developer-tools #typescript #codex #ai-agents #claude-code #dsh #dsh-plugin #cli #macos #ai-agent #deepseek-harness #open-source

sokoban-solver-generator

★ 22 Open GitHub ↗

Sokoban puzzle generator and solver with BFS, A* and Dijkstra

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# 📦 Sokoban Solver and Generator

🗒️ [README pt-BR](https://github.com/xbandrade/sokoban-solver-generator/blob/main/README-pt-BR.md)

▶️ Video showing the game mechanics, the generator and the solver: [Sokoban Generator and Solver](https://www.youtube.com/watch?v=l0BHKkoViII)

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](https://en.wikipedia.org/wiki/Sokoban)

sokoban-solver-generator

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README