TOPICS
Search

Peg Solitaire


A game played on a board of a given shape consisting of a number of holes of which all but one are initially filled with pegs. The goal is to remove all pegs but one by jumping pegs from one side of an occupied peg hole to an empty space, removing the peg which was jumped over.

PegSolitaire

One of the most common configurations is a cross-shaped board with 33 holes. All holes but the middle one are initially filled with pegs. Strategies and symmetries are discussed by Gosper et al. (1972). Berlekamp et al. (1982) give a complete solution of the puzzle.

PegSolitaireTriangle

There is also triangular variant with 15 holes (where 15 is the 5th triangular number T_n) and 14 pegs (Beeler 1972). Numbering hole 1 at the apex of the triangle and thereafter from left to right on the next lower row, etc., the following table gives possible ending holes for a single peg removed (Beeler 1972). Because of symmetry, only the first five pegs need be considered. Also because of symmetry, removing peg 2 is equivalent to removing peg 3 and flipping the board horizontally. Bell (2008) surveys this problem, which dates back to Smith (1891). Bell gives necessary and sufficient conditions for this problem to be solvable and a simple solution algorithm.

removepossible ending pegs
11, 7=10, 13
22, 6, 11, 14
43=12, 4, 9, 15
513

Kraitchik (1942) considered a board with one additional hole placed at the vertices of the central right angles.


See also

Checkers, Conway's Soldiers

Explore with Wolfram|Alpha

References

Beasley, J. D. The Ins and Outs of Peg Solitaire. Oxford, England: Oxford University Press, 1992.Beeler, M. Item 76 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 29, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/games.html#item76.Bell, G. I. "Solving Triangular Peg Solitaire." J. Integer Seq. 11, Article 08.4.8, 1-21, 2008.Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Ch. 23 in Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982.Chang, E.; Phillips, S. J.; and Ullman, J. D. "A Programming and Problem Solving Seminar." Stanford University Technical Report CS-TR-91-1350, February 1991. http://elib.stanford.edu.de Vreught, H. "Hi-q." http://rec-puzzles.org/new/sol.pl/competition/games/hi-q.Gardner, M. "Peg Solitaire." Ch. 11 in The Unexpected Hanging and Other Mathematical Diversions. New York: Simon and Schuster, pp. 122-135 and 250-251, 1969.Gosper, R. W.; Brown, S.; and Rayfield, M. Item 75 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 28-29, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/games.html#item75.Guy, R. K. "Unsolved Problems in Combinatorial Games." In Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July, 1994 (Ed. R. J. Nowakowski.) Cambridge, England: Cambridge University Press, 1998.Hopcroft, J. E. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation, 2nd ed. Reading, MA: Addison-Wesley, 2000.Kraitchik, M. "Peg Solitaire." §12.19 in Mathematical Recreations. New York: W. W. Norton, pp. 297-298, 1942.Manna, Z. Mathematical Theory of Computation. New York: McGraw-Hill, 1974.Moore, C. and Eppstein, D. "One-Dimensional Peg Solitaire, and Duotaire." Working Paper 00-09-050. Sante Fe Institute. http://www.santafe.edu/sfi/publications/Working-Papers/00-09-050.ps.gz."Peg.solitaire." http://rec-puzzles.org/new/sol.pl/competition/games/peg.solitaire.Ravikumar, B. "Peg-Solitaire, String Rewriting Systems and Finite Automata." Proc. 8th Int. Symp. Algorithms and Computation. New York: Springer-Verlag, pp. 233-242, 1997.Smith, H. "Puzzle." US Patent #462, 170, 1891.Uehara, R. and Iwata, S. "Generalized Hi-Q is NP-Complete." Trans IEICE E73, 270-273, 1990.

Referenced on Wolfram|Alpha

Peg Solitaire

Cite this as:

Weisstein, Eric W. "Peg Solitaire." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PegSolitaire.html

Subject classifications