Notes on solving and playing peg solitaire on a computer - Mathematics > CombinatoricsReport as inadecuate

Notes on solving and playing peg solitaire on a computer - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: We consider the one-person game of peg solitaire played on a computer. Twopopular board shapes are the 33-hole cross-shaped board, and the 15-holetriangle board-we use them as examples throughout. The basic game begins froma full board with one peg missing and the goal is to finish at a board positionwith one peg. First, we discuss ways to solve the basic game on a computer.Then we consider the problem of quickly distinguishing board positions wherethe goal can still be reached -winning- board positions from those where itcannot. This enables a computer to alert the player if a jump underconsideration leads to a dead end. On the 15-hole triangle board, it ispossible to identify all winning board positions from any single vacancystart by storing a key set of 437 board positions. For the -central game- onthe 33-hole cross-shaped board, we can identify all winning board positions bystoring 839,536 board positions. By viewing a successful game as a traversal ofa directed graph of winning board positions, we apply a simple algorithm tocount the number of ways to traverse this graph, and calculate that the totalnumber of solutions to the central game is 40,861,647,040,079,968. Our analysiscan also determine how quickly we can reach a -dead board position-, where aone peg finish is no longer possible.

Author: George I. Bell



Related documents