[[alternative]]An Improved Algorithm for the (n2-1)-puzzle

[[abstract]]The (n2-1)-puzzle has been studied by many researchers since Sam Loyd introduced the “14-15 puzzle” and its variants in 1870. Given an N x N chessboard with (n2-1) random-numbered tiles (leaving one blank block), the goal of the (n2-1)-puzzle is to rearrange all tiles in row-major order by sliding one tile adjacent to the blank repeatedly. In this paper, we improve the method proposed by Ian Parberry. Using divide- and-conquer and greedy techniques, we solve the (n2-1)-puzzle in at most 13/3n3-59/4n2+263/12n-17 moves. It has been known that the problem requires at least n3-O(n2) moves in the worst case, so our algorithm makes no more than 13/3 times more moves than necessary. Besides, our solution makes no more than 13/2 time more than the numbers it needs in the average case (at least 2/3n3-2/3n2 moves).