Thameur Portfolio
Sokoban Solver π§©
June 15, 2022 (2y ago)
𧩠A Sokoban puzzle solver based on the A* and Breadth-First Search (BFS) algorithms designed to solve Sokoban puzzles efficiently.
π Abstract
The Sokoban Solver is an AI-based solution to solving the Sokoban puzzle using the A* and Breadth-First Search (BFS) algorithms. The goal of the puzzle is to move boxes to target positions within a maze while avoiding obstacles. This solver efficiently finds the optimal path for solving the puzzle by leveraging search algorithms to explore all possible moves and find the shortest solution.
π Features
- Sokoban Puzzle Solver: Solves Sokoban puzzles using AI search algorithms.
- A and BFS Algorithms*: Uses A* and BFS for optimal and breadth-first search approaches.
- Deadlock Detection: Detects deadlocks to avoid unsolvable scenarios.
- Easy Setup: Run the Python script to solve Sokoban puzzles with minimal configuration.
- Visual Representation: Provides a visual representation of the puzzle solving process.
π Getting Started
Prerequisites
Before you can run this project, ensure the following packages are installed:
- Python 3.x
Installation
- Clone the repository:
git clone https://github.com/verus56/sokoban-solver cd sokoban-solver
- Install required dependencies (if necessary):
pip install -r requirements.txt
Running the App
To solve a Sokoban puzzle:
python main.py
π€ How It Works
- Puzzle Initialization: The puzzle grid is initialized with positions of walls, targets, boxes, and the player.
- A Algorithm*: A* search is used to find the shortest path to move the boxes into target positions, considering obstacles.
- BFS Algorithm: BFS explores all possible moves systematically to find the solution, useful in scenarios where A* is not ideal.
- Deadlock Detection: The system identifies deadlocks to avoid futile exploration of unsolvable puzzles.
π Technical Stack
- AI Engine: A* and BFS Algorithms
- Puzzle Solving: Sokoban Puzzle Logic
- Search Algorithms: A*, BFS
- Language: Python
π οΈ Deployment
This system can be run locally on any machine with Python installed to solve Sokoban puzzles of various complexity levels.
π License
Released under the GPL-3.0 License.
π² Contact
Made with β€οΈ by Hamzaoui Thameur
- GitHub: Hamzaoui Thameur
- Email: thameurhameaoui9@gmail.com