Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves
It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{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\).
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-07-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/8/3/459 |
| Summary: | It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{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\). |
|---|---|
| ISSN: | 1999-4893 |