Proceedings:
Proceedings of the AAAI Conference on Artificial Intelligence, 5
Volume
Issue:
Science
Track:
Search
Downloads:
Abstract:
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 .
AAAI
Science