Sliding Graph Puzzles: Permutation Groups, Wilson’s Theorem, and New Algorithms
Chun Chi Wong, Linxuan Li, Ruohan Chen · Applied and Computational Engineering · 2025
The 15-puzzle is a classic sliding puzzle consisting of a 4x4 grid with 15 numbered square tiles and one empty space. In 1974, Wilson generalized the 15-puzzle to find the group of permutations on graphs. In this work, we provide a variation of a proof of Wilson’s theorem, propose a result for 1-connected and disconnected graphs, find a new manual algorithm for solving sliding graph puzzles, and extend existing computer algorithms on the 15-puzzle to solve any sliding graph puzzle.