Applications of abstract group theory in the solvability of solitaire board games

Abstract

Peg solitaire, which is believed to be originated in England in late 1600, is a board game played by a single player. There are various shapes of boards while the cross-shaped board is the most common and popular. The solvability of the solitaire game depends on the particular shape of the board. In literature, a mathematical analysis of the solvability published in 1842 using parity arguments can be found. In 1998, Arie Bialostocki published a paper demonstrating an elegant way to analyze the solvability of the solitaire game of the cross- shaped board. In his paper, Bialostocki used the Klein four-group and its properties to analyze the possible solutions. This is perhaps the only instance the Klein four-group, an abstract group containing four elements, has been used to analyze the solvability of a popular board game. In this research, the techniques used by Bialostocki to analyze the solvability of the solitaire game were generalized to many other shapes of boards. Furthermore, the solvability conditions on some special shapes of boards were derived. A Single-Vacancy to Single- Survivor Problem (SVSSP) is defined as the possibility of winning a solitaire game starting with a full board game with a single-hole-vacancy (initial board configuration) and winning with a board configuration in which only one peg remains (winning board configuration). The solvability of this problem, together with the solvability of the complement problem (CP), which is a specific form of SVSSP in which the last peg resides at the initially vacant hole, were investigated using the techniques proposed by Bialostocki. Furthermore, the unsolvability of some solitaire games such as French solitaire and diamond solitaire were investigated using Bialostocki’s techniques and by defining a ‘resource count’ which is also known as ‘pagoda function’. In this research, many shapes of symmetric solitaire boards containing a central hole (except the triangular boards) were taken. Furthermore, the patterns, in terms of the number of holes of the board, for the solvability of the numerous shapes of solitaire boards were identified.