A scale-down solution of N2–1 puzzle

Real-time decision making algorithms like ‘real-time search’ have become of great importance in several fields like robotics. ‘N²–1 puzzle’ is widely employed as a benchmark problem for these algorithms. However, the problem of finding an optimal solution for ‘N²–1 puzzle’ is NP-complete. It is hard to evaluate the optimality of the experimental results for large size problems with N=5(24-puzzle) or greater by the comparison with the optimal solution. Therefore, in this paper, we propose a new method (SD solution) for solving the ‘N²–1 puzzle’ by scaling down the size of the problem one by one. The proposed method does not employ any search tree. Thus it can find a nearly optimal solution even for large problems and requires less memory and computation time. The outcomes of the proposed method can be hopefully employed for evaluating a performance of many other algorithms.