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