Solitaire Lattices

Abstract. One of the classical problems concerning the peg solitaire game is the feasibility issue. Tools used to show the infeasibility of various peg games include valid inequalities, known as pagoda-functions, and the so-called rule-of-three. Here we introduce and study another necessary condition: the solitaire lattice criterion. While the lattice criterion is shown to be equivalent to the rule-of-three for the classical English 33-board and French 37-board as well as for any m×n board, the lattice criterion is stronger than the rule-of-three for games played on more complex boards. In fact, for a wide family of boards presented in this paper, the lattice criterion exponentially outperforms the rule-of-three.