Xref: utzoo comp.theory:1573 rec.puzzles:8163 sci.math:15346
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!tut.cis.ohio-state.edu!sei!fs7.ece.cmu.edu!o.gp.cs.cmu.edu!andrew.cmu.edu!ss7m+
From: ss7m+@andrew.cmu.edu (Steven M. Stadnicki)
Newsgroups: comp.theory,rec.puzzles,sci.math
Subject: A question on Peg Solitaire
Message-ID: <IblivQO00W02AAfm4z@andrew.cmu.edu>
Date: 23 Feb 91 22:38:20 GMT
Organization: Carnegie Mellon, Pittsburgh, PA
Lines: 11

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


Brought to you by Super Global Mega Corp .com