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/anyaschukin/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, during search)
- Time complexity (total number of states explored, during search)
- Solve time
... intermediate states ...
Find a valid sequence of moves to reach the solved state, a.k.a the "snail solution". The empty tile is always at the end of the snail.
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 @dfinnis.