Technical Report: DCC-98-10
Depth-first search solves Peg Solitaire
Armando B. Matos
DCC & LIACC
Universidade do Porto
Rua do Campo Alegre 823
4150 Porto, Portugal
December 1998
Abstract
We invite the reader to test his skillness in
previewing the behaviour of a simple, depth-first search algorithm
that solves (or tries to solve) the Peg-solitaire game; the test is
based on a few questions about the search tree involving aspects
such as the number of nodes explored by the algorithm, the influence
of the ordering of the peg moves on the efficiency of the
computation and the ``average branching factor'' of internal nodes.
We refrain from presenting at this moment the
conclusions of this paper, so that the reader can fully enjoy the
experiment that will be described in this report.
Keywords:
Depth-first search; games; complexity
