This is a 8-Puzzle Solver using A* search algorithm. here, i've used Manhattan Distance and Hamming Function as Heuristic (h-score) and Level of Node in a tree as (g-score).
Click a box which can be moved i.e (box having free space in neighbour) to make a move. Press SPACE key to shuffle the board. Press ENTER key, sit back and watch the algorithm solving the puzzle.
- Goal: Goal State is initially given.
- State: Instance of Puzzle.
- Actions: Move the blank tile in left, up, down and right positions
- Performance: Number of total moves in the solution
A* is an informed search algorithm used in path findings and graph traversals. It is a combination of uniform cost search and best first search, which avoids expanding expensive paths. A* star uses admissible heuristics which is optimal as it never over-estimates the path to goal. The evaluation function A* star uses for calculating distance is
- f(n) = g(n) + h(n)
- g(n) = cost so far to reach n
- h(n) = estimated cost from n to goal
- f(n) = estimated total cost of path through n to goal
The heuristic function is a way to inform the search regarding the direction to a goal. It provides an information to estimate which neighboring node will lead to the goal. The two heuristic functions that we considered for solving 8-puzzle problem are