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.

πŸ’» Source CodeΒ Β β€’Β 
Sokoban Solver: Puzzle Solving with AI
Sokoban Solver: Puzzle Solving with AI

πŸ“ 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

  1. Clone the repository:
git clone https://github.com/verus56/sokoban-solver cd sokoban-solver
  1. Install required dependencies (if necessary):
pip install -r requirements.txt

Running the App

To solve a Sokoban puzzle:

python main.py

πŸ€– How It Works

  1. Puzzle Initialization: The puzzle grid is initialized with positions of walls, targets, boxes, and the player.
  2. A Algorithm*: A* search is used to find the shortest path to move the boxes into target positions, considering obstacles.
  3. BFS Algorithm: BFS explores all possible moves systematically to find the solution, useful in scenarios where A* is not ideal.
  4. 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