A real-time algorithm for the \((n^{2}-1)\)-puzzle

DOI10.1016/0020-0190(95)00134-XzbMath0875.68539OpenAlexW1989991251MaRDI QIDQ1350227

Ian Parberry

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00134-x

zbMATH Keywords

Greedy algorithmManhattan distanceAnalysis of algorithmsLower boundDivide and conquer\((n^{2}-1)\)-puzzle15-puzzleReal-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

A simple proof that the \((n^{2} - 1)\)-puzzle is hard ⋮ SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS ⋮ Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces ⋮ Puzzle and dragons is hard ⋮ Multi-color pebble motion on graphs ⋮ Motion planning in Cartesian product graphs ⋮ Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves

Cites Work

• Unnamed Item
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Depth-first iterative-deepening: An optimal admissible tree search
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A Scheme for Fast Parallel Communication

This page was built for publication: A real-time algorithm for the \((n^{2}-1)\)-puzzle