Sokoban Solver (Python)

Overview

Sokoban Solver is a Python project for building intelligent agents capable of solving Sokoban puzzles of varying difficulty. Sokoban is a classic puzzle game where a player pushes boxes onto target locations within a warehouse-like maze. This repository provides a framework and implementations for solving Sokoban automatically, including:

• A* (A-star) Search Algorithm: For optimal pathfinding and solution generation.
• State Generation & Representation: Efficient representations for complex puzzle states.
• Extensible Heuristics: Easily plug in custom heuristics for advanced research or competition.
• Batch & GUI Play: Solve puzzles either through a graphical interface or via scripts for automated testing.

The project is aimed at students, educators, AI practitioners, and puzzle enthusiasts interested in combinatorial search, AI algorithms, or game automation.

---

Features

• A* Solver: Finds the shortest solution using admissible heuristics.
• Breadth-First Search (BFS): Included for comparison and as a baseline.
• Deadlock Detection: Avoids unsolvable states to speed up search.
• State Hashing: Efficient duplicate state detection.
• Puzzle Generation: Create random or pre-defined puzzles for testing.
• Extensible Codebase: Modular structure for easy experimentation.
• Tkinter & Pygame GUIs: Visualize puzzles and solutions interactively.

---

Getting Started

Prerequisites

• Python 3.6+
• pygame and pygame_widgets (for the main GUI)
• numpy (for efficient state handling and matrix operations)

To install requirements:

pip install pygame pygame-widgets numpy

Running the Solver

1. Clone the Repository

git clone https://github.com/avro1199/Sokoban-Solver-Python
cd Sokoban-Solver-Python

2. Launch the GUI

python sokoban.py

Or, for the Tkinter-based classic GUI:

python gui_sokoban.py

3. Solve a Puzzle

• Use the menu or buttons to load a level, step through moves, or invoke the A* solver.
• The solver can handle both hand-designed and randomly generated puzzles.

4. Command-Line/Script Mode

Automated testing and batch runs are supported via test scripts and modules like sanity_check.py.

---

File Structure

• sokoban.py — Main entry point for the game and GUI.
• src/ — Core algorithms and game logic (A*, BFS, state handling, etc).
• levels/ — Example Sokoban level files in plain text.
• images/ or img/ — Sprites for GUI display.
• tests/ — Unit tests and sample scripts.
• README.md — This file.
• LICENSE — GNU General Public License (GPL v3).

---

How It Works

State Representation

The puzzle is represented as a matrix/grid. Each cell holds a symbol:

• # — wall
• @ — player
• $ — box
• . — target
• * — box on target
• + — player on target
• — empty

A* Algorithm

The solver uses A* search, where each state is a combination of player and box positions. Heuristic functions (e.g., sum of Manhattan distances from boxes to targets) guide the search efficiently.

Extensible Design

• Add new heuristics in src/astar.py.
• Plug in custom generators or deadlock detectors.
• Easily swap between BFS, DFS, A*, or Dijkstra as desired.

---

Example

Sample usage in Python:

from src.astar import solve_astar
from src.utils import load_level

matrix = load_level("levels/level1.txt")
solution, depth = solve_astar(matrix)
print("Solution:", solution)

---

License

This project is licensed under the GNU General Public License v3.0 (GPL-3.0).

---

Acknowledgements

• Inspired by classical AI textbooks and university assignments.
• Thanks to all open-source contributors and to the creators of Sokoban.

---

Contributing

Pull requests, issues, and suggestions are welcome! See the CONTRIBUTING.md for details.