Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 248-252.
Abstract
The 8-puzzle is the largest puzzle of its type that can be completely solved. It is simple, and yet obeys a combinatorially large problem space of 9!/2 states. The N x N extension of the 8-puzzle is NP-hard. In the first part of this paper, we present complete statistical data based on an exhaustive evaluation of all possible tile configurations. Our results include data on the expected solution lengths, the 'easiest' and 'worst' configurations, and the density and distribution of solution nodes in the search tree. In our second set of experiments, we used the 8-puzzle as a workbench model to evaluate the benefit of node ordering schemes in IterativeDeepening A* (IDA*) . One highlight of our results is that almost all IDA* implementations perform worse than would be possible with a simple random ordering of the operators.
@inproceedings{ijcai1993p35,
title = {Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA},
author = {Reinefeld, Alexander},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {248--252},
year = {1993},
note = {Constraint Satisfaction Problems},
url = {https://ijcai.org/proceedings/1993/35},
}
TY - CPAPER TI - Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA AU - Reinefeld, Alexander T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 248 EP - 252 UR - https://ijcai.org/proceedings/1993/35 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
