International Journal of Science, Engineering and TechnologyAuthors: Shalini K, Dr S.P. Reshma
Abstract: The reconfiguration framework provides a unified perspective on a wide range of combinatorial and graph-theoretic problems by modeling transformations between feasible solutions under defined adjacency rules. Using the classical 15-puzzle as a motivating example, the framework extends to source problems such as independent set, dominating set, graph coloring, satisfiability, and degree-sequence realizations. Central computational challenges—including reachability, shortest transformation sequences, connectivity, and diameter—are examined, many of which are PSPACE-complete in general but admit efficient algorithms for restricted graph classes. Token-based dynamics such as sliding, jumping, and addition-removal serve as fundamental adjacency models, while extensions to puzzles, coloring, and SAT reconfiguration highlight structural and complexity landscapes. This study emphasizes the deep connections between discrete mathematics and practical applications in physics, robotics, and algorithmic game theory, offering a comprehensive foundation for future research in reconfiguration problems[1,2].
DOI: http://doi.org/10.5281/zenodo.20794444
