Algorithmic Approaches to MOLS Sliding Puzzle (2024)

Undergraduates: Maxim Chadaev, Daniel Henderson

Faculty Advisor: Ivan Cherednik
Department: Mathematics

---

Exploring the MOLS sliding puzzle, a novel variant of the traditional 15-puzzle, presents unique_x000D_
challenges for AI algorithms. We present two solutions: a brute-force Breadth-First Search (BFS)_x000D_
algorithm that ensures the shortest path at the cost of extensive runtime and a Best-First Search_x000D_
(BeFS) algorithm that more efficiently finds a valid solution of reasonable length. Additionally,_x000D_
we introduce a formula that predicts the average shortest path, providing a theoretical benchmark_x000D_
for future algorithm development. This puzzle is particularly promising for training AI models,_x000D_
advancing applications in machine learning and strategic game analysis