Notes on solving and playing peg solitaire on a computer - Mathematics > CombinatoricsReportar como inadecuado

Notes on solving and playing peg solitaire on a computer - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: George I. Bell


Documentos relacionados