Skip to content

DangDecTen/ai-lab-slidingtilepuzzle

Repository files navigation

Sliding Tile Puzzle Solver

A Python project for solving N-puzzle problems using classical AI search algorithms with GUI.

🚀 Features

Core Algorithms

  • Breadth-First Search (BFS) - Optimal solution, guaranteed shortest path
  • Depth-First Search (DFS) - Memory efficient, may find longer solutions
  • A Search* - Optimal with Manhattan distance heuristic

📁 Project Structure

AI-Fundamentals/
├── main.py                    # Run solvers and generate output
├── puzzle_gui.py       # Visualize puzzles and solutions
├── report.py                  # Summarize output results
├── algorithms/                # Core logic of the project
├── data/
│   ├── input/                 # JSON definitions of initial state
│   └── output/                # JSON solution results
├── utils/                     # Helper functions
├── final_report.md            # Techinical report
└── README.md

📦 Prerequisites

pip install pygame

⚙️ How to Run

Command Line Interface

Run a single puzzle:

python main.py --input data/input/easy_8_puzzle.json --algorithm a_star --heuristic manhattan

Run all puzzles with BFS:

python main.py --all --algorithm bfs

Command Line Options:

Flag Description Options
--input Path to input file Any .json file in data/input/
--all Run on all input files -
--algorithm Search algorithm bfs, dfs, ids, ucs, bi_bfs, a_star
--heuristic Heuristic function manhattan, none

GUI

Launch the GUI:

python puzzle_gui.py

Ensure at least one solution exists in data/output/ before running.

🧮 Input Format (JSON)

Place in data/input/ folder:

{
  "name": "Simple 3x3 Puzzle",
  "size": 3,
  "initial_state": [1, 2, 3, 4, 5, 6, 0, 7, 8],
  "goal_state": [1, 2, 3, 4, 5, 6, 7, 8, 0]
}

📤 Output Format (JSON)

Stored in data/output/ with matching filenames:

{
  "puzzle_name": "Simple 3x3 Puzzle",
  "size": 3,
  "initial_state": [...],
  "goal_state": [...],
  "algorithm": "a_star",
  "heuristic": "manhattan",
  "status": "Path found",
  "solution_path": ["R", "D", ...],
  "solution_length": 12,
  "time_taken": 0.035,
  "space_used": 1341,
  "nodes_expanded": 589
}

➕ Adding a New Algorithm

  1. Create a new file in algorithms/, e.g. greedy.py.
  2. Implement a solve(initial_state, goal_state, size, heuristic=None) method.
  3. Add it to ALGORITHMS in main.py:
from algorithms import greedy
ALGORITHMS = {
  ...,
  "greedy": greedy.solve
}
  1. Run it using:
python main.py --input data/input/your_file.json --algorithm greedy --heuristic manhattan

🧪 Generating Random Puzzles

from utils.generator import generate_random_puzzle
state = generate_random_puzzle(size=3, shuffle_moves=100)

📬 License & Credits

MIT License. Built for educational and experimentation purposes with clean modular design.

About

AI Lab - Searching, solving Sliding Tile puzzle

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Contributors 2

  •  
  •