Approximately Optimal Search on a Sliding Puzzle

Authors: Merleau NSC, O'Malley M, Roldán Á, Mukherjee S

Published in: arXiv 2024 (2024)

Citations: 3

Abstract:
The sliding puzzle — rearranging tiles on a grid to reach a goal configuration — becomes intractable in higher dimensions for exact solvers. This paper studies approximate solutions on d-dimensional sliding puzzles, proving that a greedy strategy achieves solutions within a constant factor of optimal for any fixed dimension. The analysis draws on connections to sorting networks and combinatorial geometry, providing both theoretical guarantees and practical algorithms that scale far beyond exact methods.