Skip to content

A BFS and A* implementation to the classic 8-puzzle problem

Notifications You must be signed in to change notification settings

C-Collamar/8-Puzzle-Solver

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

8-Puzzle-Solver

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)

Test Cases

Goal board configuration:

1 2 3
8 0 4
7 6 5

Initial board configurations:

Easy
1 3 4
8 6 2
7 0 5
Medium
2 8 1
0 4 3
7 6 5
Hard
2 8 1
4 6 3
7 5 0
Worst
5 6 7
4 0 8
3 2 1

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.

Compilation

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

Releases

No releases published

Packages

No packages published

Languages