**ss7m+@andrew.cmu.edu (Steven M. Stadnicki)** (02/24/91)

I've read _Winning Ways_ dozens of times (one of these days I'm going to have to buy a copy for myself), and I'm working through Beasley's _The Ins and Outs of Peg Solitaire_ right now, and a question came to me: how complex is the decision problem for Generalized Peg Solitaire? That is, given an arbitrary shaped board, and arbitrary intial and final conditions, what is the complexity of an algorithm deciding whether the position is solvable? My guess is that it would be an NP-hard problem, possibly NP-complete, but I have no idea how to prove this... has anyone done research in any areas similar to this? Steven Stadnicki ss7m@andrew.cmu.edu