A Python project for solving N-puzzle problems using classical AI search algorithms with GUI.
- 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
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
pip install pygame
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 |
Launch the GUI:
python puzzle_gui.py
Ensure at least one solution exists in data/output/
before running.
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]
}
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
}
- Create a new file in
algorithms/
, e.g.greedy.py
. - Implement a
solve(initial_state, goal_state, size, heuristic=None)
method. - Add it to
ALGORITHMS
inmain.py
:
from algorithms import greedy
ALGORITHMS = {
...,
"greedy": greedy.solve
}
- Run it using:
python main.py --input data/input/your_file.json --algorithm greedy --heuristic manhattan
from utils.generator import generate_random_puzzle
state = generate_random_puzzle(size=3, shuffle_moves=100)
MIT License. Built for educational and experimentation purposes with clean modular design.