Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves (Q1736675)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves |
scientific article |
Statements
Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves (English)
0 references
26 March 2019
0 references
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\).
0 references
15-puzzle
0 references
8-puzzle
0 references
analysis of algorithms
0 references
average-case analysis
0 references
greedy algorithm
0 references
\((n^2-1)\)-puzzle
0 references
