Solvability of Peg Solitaire on a Complete Bipartite Graph

Peg Solitaire is a well-known classical puzzle for a single player that has been extensively studied in recreational mathematics and combinatorial game theory. In this paper, we extend the study of Peg Solitaire from a spatial perspective to a graph-theoretic perspective by considering a complete bipartite graph Km,n. In this context, we propose some algorithmic approaches to solve the solvability problem using backtracking and BFS techniques. From the experimental analysis of small sizes of graphs, it is evident that the solvability of Peg Solitaire is mainly influenced by parity and partition constraints. A comparative analysis of this new perspective of Peg Solitaire is carried out by considering a standard Peg Solitaire board. In this context, a strong link between Peg Solitaire and graph theory is established to analyze the solvability problem from a generalized perspective.