GitHub Repository: 15-Puzzle-Problem-Solver-Mirror

This repository provides a highly optimized toolkit for analyzing and solving the classical N-Puzzle (specifically focusing on 8-puzzle and 15-puzzle variants). It features a robust Python testing framework backed by various search algorithms ranging from basic uninformed graph traversals (BFS, DFS) to highly advanced heuristic-driven algorithms (A*, IDA*).

• Search Algorithms: Uninformed (Breadth-First Search, Depth-First Search) and Heuristically-Informed (A*, IDA*).
• Heuristics Evaluation: Manhattan Distance, Linear Conflict, and Additive Pattern Databases (6-6-3 PDB).
• Interactive Visualization Workspace: Step-by-step terminal CLI animations and dedicated Tkinter GUI Popups to debug and analyze solution execution states explicitly.
• Robust Auto-Benchmarking: Hardcoded test-case modules containing exactly reproducible 8-puzzle and 15-puzzle states sorted by difficulty.
• C++ Equivalents: Pure, raw speed backend engines written in C++ handling identical graph algorithms for production loads.

The Python workspace gives you two primary ways to watch the algorithms unfold physically over the parsed states. Append these flags natively to solver loops to see how nodes shift!

1. CLI Terminal Animation (--visualize) Outputs a time-stepped console draw natively tracking the moving 0 piece dynamically:

python solve.py solve --size 3 --heuristic manhattan --visualize

2. Tkinter Native Popup GUI (--popup) Generates an OS-native Read-Only window featuring large, scrollable grids of every single movement mapped side-by-side with overall mathematical data:

python solve.py solve --size 3 --heuristic manhattan --popup

To evaluate efficiency, avoid passing random unverified arguments that might physically break. The suite ships with 12 mathematical test limits (2 Easy, 2 Medium, 2 Hard layouts for sizes 3x3 and 4x4).

Run a specific solver directly against a defined difficulty tier and observe the output constraints:

# Solve an easy 8-puzzle perfectly returning stats via BFS
python solve.py run-case 8_easy_1 --algorithm bfs 

# Map an intricate Hard 15-Puzzle using optimized IDA* inside a GUI popup
python solve.py run-case 15_hard_1 --algorithm ida --heuristic linear_conflict --popup

Want empirical, side-by-side data of all features handling all tiers? Utilize test-all. This routine loops all algorithms natively directly handling garbage collection up to a heavily throttled dynamic 4GB RAM check, gracefully omitting algorithms mathematically unviable for specific puzzle depths generating a final logs/test-results.txt data sheet.

python solve.py test-all

pip install termcolor psutil
python solve.py solve --heuristic manhattan

Help and usage:

python solve.py --help
python solve.py solve --help
python solve.py run-case --help

Interpreter selection:

python solve.py --interpreter python solve --heuristic manhattan
python solve.py --interpreter pypy solve --heuristic manhattan

1. Build the C++ binary:

   make -C cpp build

2. Run A* (15-puzzle, Manhattan):

   ./cpp/build/solver --algorithm astar --heuristic manhattan --size 4

3. Run IDA* (15-puzzle, Linear Conflict):

   ./cpp/build/solver --algorithm ida --heuristic linear_conflict --size 4

solve.py
python/
    cases.py        # Difficulty dictionary & configurations
    heuristics.py   # Math operations isolating cost functions
    search.py       # Core Node traversal models (BFS, DFS, A*, IDA*)
    visualizer.py   # UI handlers and Terminal matrix painters
docs/
logs/
cpp/
legacy/

• solve.py: Central CLI router and SubParser architecture dispatch.
• python/: Core library logic bridging state validation with mathematical searches.
• docs/: Full running guide and command list.
• logs/: Outputs of testing reports (test-results.txt) alongside timestamped diagnostics.
• cpp/: C++ solver implementation and Makefile.
• legacy/: Archived prior scripts and experiments.

Provide a custom start state:

python solve.py solve --state "1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 15"

As discussed in the Comparative Analysis of Algorithms, each search algorithm holds distinct theoretical time and space complexities. Our benchmarking suite natively verified these traits empirically across several standard 8-puzzle and 15-puzzle configurations:

• Theoretical Metrics: Time O(b^d), Space O(b^d)
• Observation: True. BFS reliably solved all easy layouts correctly but strictly hit out-of-memory maximum bounds on deeper 15-puzzles. Because it sequentially enqueues every node level-by-level, it rapidly exhausted gigabytes of memory space. This empirical data completely validates that its O(b^d) space complexity is the primary prohibitive bottleneck before time complexities even matter.

• Theoretical Metrics: Time O(b^m), Space O(bm)
• Observation: True. DFS was incredibly memory efficient, relying purely on linear system stacks, and uniformly avoided raising memory limit flags. However, because it blindly searches fixed branch depths without heuristics or optimal path weighting, it regularly triggered massive node/Time limits, executing functionally forever on non-trivial depths. It thoroughly mapped the exponential O(b^m) trap.

• Theoretical Metrics: Time O(b^d) (worst-case), Space O(b^d)
• Observation: True. Utilizing heuristics such as Manhattan Distance or Linear Conflict vastly restricted the effective branching factor, allowing 15-hard cases to complete gracefully. Nonetheless, since A* still actively maintains exhaustive dictionaries across its Open/Closed sets, it repeatedly demonstrated much higher Peak Memory usages than its counterparts on 15-puzzles, validating its problematic spatial constraints at scale.

• Theoretical Metrics: Time O(b^d) (worst-case), Space O(bd)
• Observation: True. The empirical data strongly proved IDA* effectively merges the strengths of DFS and A*. The recursive, linear stack approach successfully restrained maximum spatial footprint constraints, requiring visibly fewer megabytes than A* on identically hard 15-puzzles. Although it conceptually required re-evaluating early nodes during subsequent bounds, the overall timeline differences were highly nominal compared to the raw memory scaling advantages it produced.