The goal of this project is to solve the N-puzzle ("taquin" in French) game using the A* search algorithm or one of its variants.
∆ The project and the README are still WIP
- Manage various puzzle sizes (3, 4, 5, 17, etc...). The higher the program can go without dying a horrible, horrible death, the better
- The cost associated with each transition is always 1
- The user must be able to choose between at LEAST 3 (relevant) heuristic functions
- The Manhattan-distance heuristic is mandatory
- At the end of the search, the program has to provide the following values :
- Complexity in time (total number of states ever selected in the "opened" set)
- Complexity in size (Maximum number of states ever represented in memory at the same time during the search)
- Number of moves required to transition from the initial state to the final state
- The ordered sequence of states that make up the solution
- If the puzzle is unsolvable, the user must be informed and the program must exit properly
go run ./src -f [FILE]go run ./src <<< "$(python res_npuzzle-gen.py -s 3)"Puzzle file format
// Puzzle size, must be >= 3
3
// Followed by puzzle definition
1 2 3
0 8 7
6 5 4
▫️ A*
The A* algorithm is an algorithm for finding a path in a graph between an initial node and an end node. It uses a heuristic evaluation on each node to estimate the best path through it, and then visits the nodes in order of this heuristic evaluation, ignoring already visited nodes
▫️ IDA*
The IDA* algorithm is basically the same than A*, except it concentrate on exploring the most promising node without ignoring already visited one
▫️ Breadth-first search
▫️ Hamming Distance
The Hamming distance is the total number of misplaced tiles
▫️ Manhattan Distance
The distance between two points measured along axes at right angles
▫️ Linear Conflict
If two tiles are in the same row/column, and their goal positions are in the same row/colum, a linear conflict happens. This heuristic is always combined with Manhattan Distance
▫️ Gaschnig