8-PuzzleProblem

It is a program to solve an 8-puzzle problem This project is about 8-puzzle problem which is a 3x3 buttons (tiles) based puzzle in which input is given disorderly (jumbled) and a shortest path has to be found which is followed by the empty button (tile) to convert the input state with jumbled digits into orderly required final state. A* search is used for the solution of this problem. A* is combination of Dijkstra and BFS and is very efficient to solve this problem as it estimates least number of moves required to get to the final state. A heuristic function is used with the A* search, which finds the value (moves) from start (root) to the current node which is usually referred as g(n) and value (moves) require to get from current to final state which is usually referred as h(n). Both are then added to get the whole distance from start to end state which is usually referred as f(n). A* is used to minimize this value (moves). Time complexity of the A* search depends upon the heuristic function used as it determines the moves that are going to be used to get to the final state. This method is based on estimations and gives optimal solution and if solution is not possible it gives out exception. An input is given to the program with the help of a text file in which numbers from 1 to 8 are given disorderly and exactly one space is also given so an empty button which is going to move for the working of the program can be created but it is also made sure that the format is same as we are going to display on the output i.e., 3x3. As the working is happening in the list, so the space can either move 1 step forward or backward or 3 steps forward or backward in the list and in GUI it appears as left or right and up or down respectively.