A C-implementation solving the 8-puzzle problem using the uninformed search strategy BFS (Breadth-First Search) and heusitic search strategy A*. The goal is to empirically compare both strategies' space and time performance.
For each strategy, the program collects and outputs the following information:
- sequence of moves corresponding to the solution (e.g. up, down, left, right)
- total number of nodes expanded
- total number of nodes generated
- length of the solution path (number of moves)
Goal board configuration:
| 1 | 2 | 3 |
| 8 | 0 | 4 |
| 7 | 6 | 5 |
Initial board configurations:
Easy
|
Medium
|
Hard
|
Worst
|
Notes:
- While A* performs well even on the worst case, the program crashes before the BFS function completes due to its memory-hogging nature. Tested as a 32-bit executable running on a 64-bit Windows® 7 OS with Intel® Core™ i5 and 8 GB RAM.
- While there are 9! total number of configurations possible to input, only half of them are solvable. Read more about the solvability of certain configurations of the n-puzzle in this Wikipedia article or in this MathWorld explanation.
On Windows, compile and run using the following commands
gcc main.c -o Solver.exe
Solver.exeOn Linux, compile and run using the following commands
gcc main.c -o Solver
./Solver