Solving the N-puzzle with Iterative Deepening A* (IDA*) Algorithm

Abstract

The paper will start by introducing the idea of N-puzzle, followed by the way of solving and its rules of solvability. Most people use intuition and guessing to solve the N-puzzle which will increase the probability of getting repeated steps during the solving process. Besides that, the path that they select might be longer than the optimal path which is not efficient even if they are able to solve the N-puzzle. Therefore, by understanding different path finding techniques such as Dijkstra’s algorithm, A* algorithm, and IDA* algorithm, we chose two algorithms which are A* and IDA* to solve the N-puzzle. Two admissible heuristics such as Hamming distance and Manhattan distance are used. The estimation of Manhattan distance is more accurate to the actual distance compared to Hamming distance. The comparison of A* and IDA* algorithm is constructed by benchmarking different N-puzzle such as 8-puzzle, 15-puzzle, and 24-puzzle. Our result shows that there are times where A* solves the N-puzzle faster than IDA* but there are also situations where the opposing result is obtained. The reason of A* performing better than IDA* is due to IDA* often ended up revisiting the visited nodes and this problem would not happen in A* because A* avoids the duplicates. On the other hand, checking duplicates too often might slow down A* as well, and in our results we showed both situations and explain the path searching process in figures.