Solving classical problem the 8 puzzle problem using A* algorithm. Developed initially for 8-puzzle problem and then modified to work with n-puzzle problem. The heuristic used in this case is number of misplaced tiles. This heuristic does not over estimates and hence it is admissible. The A* search algorithm is optimal and always finds a path with the minimum cost.
The program stores the states in a data structure
state_node{
state - the state of the puzzle
id - an unique number given to this state
h - the heuristic
g - actual cost from the starting point to this node
f - f = g+h(as in A*algorithm)
}
n Puzzle problem have many states which are unsolvable. Such states cannot be solved by legal moves of the puzzle. The program identifies such by generating all the possible unsolvable states in n puzzle problem board then comparing every state generated by the solver to this list.
The program also checks for validity of the puzzle given to solve by verifying it as a n x n matrix. The goal state is not hard coded in the program. The program generates the goal state for any n puzzle depending on the value of n.
[1]> (load "/npuzzle.lisp")
[2]> (solve-npuzzle '#(0 1 3 4 2 5 7 8 6))
Output comes here
Name: Rohit Sinha
Email id: sinha049@umn.edu