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