BFS search for 8-Puzzle Problem
My first take on a Planning Algorithm
As a kid, I was always fascinated by the 8-Puzzle game. The game is simple yet can be daunting. There is just one rule of the game, as you can see in the video above, you have to slide the tiles in the empty spaces to arrange them in ascending order so that the last space in a 3x3 matrix is blank.
What makes this game daunting is the very fact that 9! (9 factorial) tile combinations are possible and there are some scenarios where the puzzle also becomes unsolvable. Solving by hand does seem like an option but what if the same task was to be done by a computer?
One of the most basic approaches for solving such a problem is to generate a graph map of all possible scenarios from the given initial state and find the goal state (final state) in that map, once found you can backtrack to the initial state to find the path. This approach is called a Brute Force Search or exhaustive search and is generally slower than other search algorithms but serves as a very good learning step.
The map generated shows a hierarchy structure which helps in backtracking to find the path and also contains the…
