HOW TO
- "source start.sh"
- python srcs/npuzzle.py [puzzle_file]
The goal of this project is to solve the N-puzzle game using the A* search algorithm or one of its variants.
X represents the empty cell
start position
5 | 2 | 9 |
---|---|---|
3 | X | 1 |
8 | 7 | 4 |
final wanted position
1 | 2 | 3 |
---|---|---|
8 | X | 4 |
7 | 6 | 5 |
You start with a square board made up of N*N cells. One of these cells will be empty, the others will contain numbers, starting from 1, that will be unique in this instance of the puzzle.
Your search algorithm will have to find a valid sequence of moves in order to reach the final state, a.k.a the "snail solution", which depends on the size of the puzzle.
notes
Greedy A* is described here https://en.wikipedia.org/wiki/A*_search_algorithm#Relations_to_other_algorithms