DSolving: a novel and efficient intelligent algorithm for large-scale sliding puzzles

Abstract

Sliding puzzles are classic and ancient intellectual problems. Since the amount of states in a sliding puzzle equals to the factorial of the number of tiles including the blank tile, traditional algorithms are only effective for small-scale ones, e.g. 8-puzzle. This article proposes a novel and efficient algorithm called DSolving for large-scale sliding puzzles. DSolving adopts direct solving manner. It does not need to store the intermediate states. Therefore, theoretically, it can solve any scale sliding puzzle. For general number tiles except the after-mentioned ones, DSolving adopts an efficient method to quickly move them to their target locations along shortest paths. For the top-right 3 × 2 corner sub-puzzles beginning with the last two positions in each row, DSolving constructs a state transition table (STT), which can ensure those two number tiles in the top-right corner be moved and placed correctly. The last two rows of tiles are considered as several 2 × 3 sub-puzzles, and another STT is constructed to solve these 2 × 3 sub-puzzles. These two STTs reduce corresponding problems to simple table-look-up operations. Experimental results show that DSolving exhibits high time-efficiency and stability. It takes only 4–5 ms to solve a random instance of 20 × 20 sliding puzzle on a general personal computer.