A Memory-Efficient Method for Fast Computation of Short 15-Puzzle Solutions

Author

Parberry, Ian

Author_Institution

Dept. of Comput. Sci. & Eng., Univ. of North Texas, Denton, TX, USA

Volume

7

Issue

2

fYear

2015

fDate

Jun-15

Firstpage

200

Lastpage

203

Abstract

While the 15-puzzle has a long and interesting history dating back to the 1870s, it still continues to appear as apps on mobile devices and as minigames inside larger video games. We demonstrate a method for solving the 15-puzzle using only 4.7 MB of tables that on a million random instances was able to find solutions of 65.21 moves on average and 95 moves in the worst case in under a tenth of a millisecond per solution on current desktop computing hardware. These numbers compare favorably to the worst case upper bound of 80 moves and to the greedy algorithm published in 1995, which required 118 moves on average and 195 moves in the worst case.

Keywords

computer games; directed graphs; greedy algorithms; mobile computing; 15-puzzle solution computation; desktop computing hardware; directed graph; greedy algorithm; memory-efficient method; minigame; mobile device application; video game; Computer science; Educational institutions; Games; Greedy algorithms; History; Mobile handsets; Upper bound; 15-puzzle; 8-puzzle; breadth-first search; directed graph; divide and conquer; greedy algorithm;

fLanguage

English

Journal_Title

Computational Intelligence and AI in Games, IEEE Transactions on

Publisher

ieee

ISSN

1943-068X

Type

jour

DOI

10.1109/TCIAIG.2014.2352255

Filename

6883190