One-Dimensional Peg Solitaire

. We solve the problem of one-dimensional peg solitaire. In particular, we show that the set of congurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for playing the game. 1 Introduction Peg solitaire is a game for one player. Each move consists of hopping a peg over another one, which is removed. The goal is to reduce the board to a single peg. The best-known forms of the game take place on cross-shaped or triangular boards, and it has been marketed as \Puzzle Pegs" and \Hi-Q." Discussions and various solutions can be found in [1-5]. In [6], Guy proposes one-dimensional peg solitaire as an open problem in the eld of combinatorial games. Here we show that the set of solvable congurations forms a regular language, i.e. it can be recognized by a nite-state automaton. In fact, this was already shown in 1991 by Plambeck ([7], Introduction and Ch.5) and appeared as an exercise in a 1974 book of Manna [8]. More generally,..