Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves
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\).
scientific article; zbMATH DE number 7042263