Next Article in Journal
Conditional Random Fields for Pattern Recognition Applied to Structured Data
Previous Article in Journal
A Benchmarking Algorithm to Determine Minimum Aggregation Delay for Data Gathering Trees and an Analysis of the Diameter-Aggregation Delay Tradeoff
Article

Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves

Department of Computer Science & Engineering, University of North Texas, Denton, TX 76203–5017, USA
Academic Editor: Dimitris Fotakis
Algorithms 2015, 8(3), 459-465; https://0-doi-org.brum.beds.ac.uk/10.3390/a8030459
Received: 13 January 2015 / Revised: 28 May 2015 / Accepted: 30 June 2015 / Published: 10 July 2015
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\). View Full-Text
Keywords: 15-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle 15-puzzle, 8-puzzle, analysis of algorithms, average case analysis, greedy algorithm, (n2 — 1)-puzzle
Show Figures

Figure 1

MDPI and ACS Style

Parberry, I. Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves. Algorithms 2015, 8, 459-465. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030459

AMA Style

Parberry I. Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves. Algorithms. 2015; 8(3):459-465. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030459

Chicago/Turabian Style

Parberry, Ian. 2015. "Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves" Algorithms 8, no. 3: 459-465. https://0-doi-org.brum.beds.ac.uk/10.3390/a8030459

Find Other Styles

Article Access Map by Country/Region

1
Only visits after 24 November 2015 are recorded.
Search more from Scilit
 
Search
Back to TopTop