Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves

DOI10.3390/a8030459zbMath1461.68090OpenAlexW1935730781MaRDI QIDQ1736675

Ian Parberry

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a8030459

zbMATH Keywords

greedy algorithmanalysis of algorithmsaverage-case analysis15-puzzle\((n^2-1)\)-puzzle8-puzzle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial games (91A46)

Related Items

Introduction to reconfiguration

Uses Software

• ZRAM
• MersenneTwister

Cites Work

• The \((n^ 2-1)\)-puzzle and related relocation problems
• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• The parallel search bench ZRAM and its applications
• Mersenne twister