Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
type: Item
instance of: scholarly article
title: Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
zbMATH Open document ID: 1461.68090
author: Ian Parberry
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
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\).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 91A46
zbMATH DE Number: 7042263
zbMATH Keywords: 15-puzzle
zbMATH Keywords: 8-puzzle
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: average-case analysis
zbMATH Keywords: greedy algorithm
zbMATH Keywords: \((n^2-1)\)-puzzle
describes a project that uses: ZRAM
describes a project that uses: MersenneTwister
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a8030459
OpenAlex ID: W1935730781
cites work: The \((n^ 2-1)\)-puzzle and related relocation problems
cites work: A real-time algorithm for the \((n^{2}-1)\)-puzzle
cites work: The parallel search bench ZRAM and its applications
cites work: Mersenne twister
DOI: 10.3390/A8030459
description: scientific article; zbMATH DE number 7042263