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 |
| _version_ | 1811192067908435968 |
|---|---|
| author | Ian Parberry |
| author_facet | Ian Parberry |
| author_sort | Ian Parberry |
| collection | DOAJ |
| description | 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\). |
| first_indexed | 2024-04-11T23:46:45Z |
| format | Article |
| id | doaj.art-7f898afea3304609b9528e62a044f285 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-11T23:46:45Z |
| publishDate | 2015-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-7f898afea3304609b9528e62a044f2852022-12-22T03:56:37ZengMDPI AGAlgorithms1999-48932015-07-018345946510.3390/a8030459a8030459Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected MovesIan Parberry0Department of Computer Science & Engineering, University of North Texas, Denton, TX 76203–5017, USAIt 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\).http://www.mdpi.com/1999-4893/8/3/45915-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle |
| spellingShingle | Ian Parberry Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves Algorithms 15-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle |
| title | Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves |
| title_full | Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves |
| title_fullStr | Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves |
| title_full_unstemmed | Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves |
| title_short | Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves |
| title_sort | solving the n2 1 puzzle with 8 3 n3 expected moves |
| topic | 15-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle |
| url | http://www.mdpi.com/1999-4893/8/3/459 |
| work_keys_str_mv | AT ianparberry solvingthen21puzzlewith83n3expectedmoves |