A sliding puzzle solver using the A* search algorithm with several heuristics.
The goal is to solve quickly, with a target of under 10 seconds for puzzle size 3. At worst, this project solves size 3 in a few milliseconds, & size 4 in under a second.
See the subject for more details.
Final Score 114/100
First you need to have your golang workspace set up on your machine.
Then clone this repo into your go-workspace/src/ folder.
git clone https://github.com/dfinnis/N-Puzzle.git; cd N-Puzzle
Download dependencies.
go get -d ./...; pip install -r requirements.txt
To run.
go run main.go
Alternatively, build & run the binary.
go build; ./N-Puzzle
N-Puzzle first generates a random puzzle. If the puzzle is solvable N-Puzzle prints the solution from inital state to solved. N-Puzzle then prints:
- Number of moves required
- Size complexity (maximum number of states stored simultaneously in memory)
- Time complexity (total number of states explored)
- Solve time
... intermediate states ...
Find a valid sequence of moves to reach the solved state, a.k.a the "snail solution".
Set puzzle size, default 3.
go run main.go -s 4
Set heuristic to guide the A* search. Default manhattan. Options:
- manhattan
- hamming
- euclidean
- nilsson
- outRowCol
go run main.go -h nilsson
The boards/ folder contains 169 unit tests, solvable and unsolvable, depth 3 to 9. boards/ also contains generator.py, a random boards generator.
test.sh runs static unit tests from the boards/ folder, & random tests using generator.py.
./test.sh
For each size, test.sh then plots solve time, size & time complexity, & moves by heuristic. For size 3:
These plots show for size 3 the manhattan heuristic performs best, solving fastest while still providing a low number of moves.
The nilsson heuristic is almost as quick as manhattan, but usually takes more moves. Heuristics outRowCol, hamming, & euclidean take progressively more time to solve compared to manhattan for no improvement in number of moves.
For size 4 only manhattan & nilsson heuristics return a solution in under a minute, the other heuristics are omitted:
These plots show for size 4 the nilsson heuristic performs best, solving in under a second. This is reflected by a smaller size & time complexity than manhattan, the trade off being a greater number of moves.
I wrote this project in a team with the awesome @anyaschukin.