🎮 Sokoban Solver & Game

A modern, responsive web-based Sokoban puzzle game with an intelligent solver, level editor, and solution visualizer. Play classic push-the-box puzzles or let the AI solve them for you!

✨ Features

🎯 Game & Solver

• Intelligent AI Solver - Advanced A* algorithm with optimized performance
• Real-time Progress - Watch the solver work with live progress updates
• Solution Playback - Step through solutions move by move
• Multiple Algorithms - Choose from BFS, DFS, UCS, or A* search methods

🎨 Level Editor

• Visual Editor - Click cells to cycle through floor, wall, block, target, and player
• Responsive Grid - Automatically scales to fit your screen
• Custom Levels - Create and save your own puzzles
• Import/Export - Share levels via URL with deep-linking support

🎮 Gameplay

• Smooth Controls - Play with WASD, arrow keys, or on-screen buttons
• Voice Control - Use speech recognition for hands-free play
• Mobile Friendly - Fully responsive design works on all devices
• Auto-progression - Automatically advance to next level when solved

💾 Data Management

• Local Storage - All progress saved in your browser
• Level Sharing - Generate shareable URLs for custom levels
• Reset Option - Clear all data and start fresh
• Cached Solutions - Previously solved puzzles load instantly

🚀 Quick Start

Online (Recommended)

Simply visit the live application - no installation required!

Local Development

# Clone the repository
git clone https://github.com/dangarfield/sokoban-solver.git
cd sokoban-solver

# Serve locally (any web server works)
npx serve .
# or
python -m http.server 8000
# or
php -S localhost:8000

# Open http://localhost:8000 in your browser

🎮 How to Play

Basic Controls

• Movement: WASD keys or arrow keys
• Reset Level: Escape or Space
• Voice Commands: Say "up", "down", "left", "right", or "restart"

Level Editor

1. Click any cell to cycle through types:
2. Floor (empty space)
3. Wall (obstacle)
4. Block (pushable box)
5. Target (goal position)
6. Player (starting position)
7. Target & Block together

8. Target & Player together

9. Save your level using the save button

10. Share your creation with the export button

Using the Solver

1. Click "Solve" to start the AI solver
2. Watch progress as it explores possible moves
3. Navigate solution with Previous/Next buttons
4. Solutions are cached for instant replay

🧠 Solver Algorithm

The application uses Festival, a high-performance Sokoban solver that combines optimal search strategies with advanced pruning techniques.

Festival Algorithm Overview

Festival is a state-of-the-art solver originally developed in C++ by Yaron Shoham. This implementation is a Rust port compiled to WebAssembly for browser execution.

Key Features: - Pattern Database Heuristics - Pre-computed lookup tables for accurate distance estimates - Advanced Deadlock Detection - Identifies unsolvable positions early (freeze deadlock, bipartite matching) - Macro Moves - Optimizes sequences of moves into single operations - Transposition Tables - Avoids re-exploring identical board states - Lower Bound Pruning - Eliminates branches that cannot lead to optimal solutions

Performance Optimizations

• Rust + WebAssembly - Near-native performance in the browser (10-100x faster than JavaScript)
• Non-blocking UI - Solver runs in a Web Worker without freezing the interface
• Real-time Progress - Live updates on explored states and search progress
• Memory Efficient - Optimized state representation and hash tables
• Optimal Solutions - Finds shortest push solutions for most puzzles

🎨 Level Format

Levels use the standard XSB (Extended Sokoban) text format:

Level: My Custom Level
########
#  .   #
# $  @ #
#      #
########

Symbols (XSB Standard): - # = Wall - = Floor (empty space) - $ = Box (crate to push) - . = Goal (target position) - @ = Player starting position - * = Box on goal - + = Player on goal

🔧 Configuration

Adding Levels

Edit grids/Base-Levels.txt to include new puzzles using XSB format:

Level: Easy Puzzle
####
#.@#
#$ #
####

Level: Medium Challenge
#######
#.  @ #
# $$  #
#  .  #
#######

🤝 Contributing

This project builds upon excellent work from: - KnightofLuna/sokoban-solver - Original web interface - Festival Solver - High-performance C++ solver by Yaron Shoham

Technology Stack

• Frontend: Vanilla JavaScript, Bootstrap 5
• Solver: Rust compiled to WebAssembly
• Algorithm: Festival solver (pattern databases, advanced pruning)
• Performance: Web Workers for non-blocking UI