Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable
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.
Cite
Text
Ratner and Warmuth. "Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable." AAAI Conference on Artificial Intelligence, 1986.Markdown
[Ratner and Warmuth. "Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable." AAAI Conference on Artificial Intelligence, 1986.](https://mlanthology.org/aaai/1986/ratner1986aaai-finding/)BibTeX
@inproceedings{ratner1986aaai-finding,
title = {{Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable}},
author = {Ratner, Daniel and Warmuth, Manfred K.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1986},
pages = {168-172},
url = {https://mlanthology.org/aaai/1986/ratner1986aaai-finding/}
}