Complete Search of Sliding Tile Puzzles on a Personal Computer [Extended Abstract] - Tarakanov, Oleg (Proceedings of the International Symposium on Combinatorial Search, 2023)
The 4x4 and 8x2 Sliding Tile Puzzles have more than ten trillion solvable states, making complete brute force search very challenging: best existing solutions take weeks to run or require expensive hardware. We propose and implement a set of optimizations of the frontier search algorithm, that are efficient on a modern personal computer. We run a number of complete searches, each taking about 3 days on our hardware, for both puzzles in single-tile and multi-tile metrics, verifying previously known results about the radiuses of the puzzles. We also discover that the diameter of the 4x4 Puzzle is 80 single-tile moves, and the radius of the 8x2 Puzzle is 57 multi-tile moves.