Solving the (n^2-1)-puzzle with 83n^3 expected moves

DOI10.3390/A8030459MaRDI QIDQ1736675zbMATH OpenOpenAlexFDO

Authors Ian Parberry

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

15-puzzle8-puzzle\((n^2-1)\)-puzzleanalysis of algorithmsaverage-case analysisgreedy algorithm

Mathematics Subject Classification ID

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

Review text

Summary: It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\frac{8}{3} n^3 +O(n^2)\) expected moves. This analysis is verified experimentally on 10,000 random instances each of the \((n^2-1)\)-puzzle for \(4 \leq n \leq 200\).

Recommendations

• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• The \((n^ 2-1)\)-puzzle and related relocation problems
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• scientific article; zbMATH DE number 1529463
• Analysis of the picture cube puzzle

Cites work

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

Cited in

(5)

• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• Introduction to reconfiguration
• Additive approximation algorithms for sliding puzzle
• On the diameters of friends-and-strangers graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems

Describes a project that uses

Uses Software

• ZRAM
• MersenneTwister

This page was built for publication: Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736675)