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:

Initial board configurations:

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.exe

On Linux, compile and run using the following commands

gcc main.c -o Solver
./Solver