Finding a shortest solution for the N x N extension of the 15- Puzzle is intractable

The 8-puzzle and the 15-puzzle have been used for many years as a domain for testing heuristic search techniques. From experience it is known that these puzzles are difficult and therefore useful for testing search techniques. In this paper we give strong evidence that these puzzles are indeed good test problems. We extend the 8-puzzle and the 15-puzzle to a nxn board and show that finding a shortest solution for the extended puzzle is NP-hard and thus computationally infeasible. We also present an approximation algorithm for transforming boards that is guaranteed to use no more than c L (SP) moves, where L (SP) is the length of the shortest solution and c is a constant which is independent of the given boards and their size n.