You are to develop a Prolog program that can solve one dimensional peg solitaire puzzles. Each puzzle is defined by a sequence of holes, some of which contain a peg. Each move involves jumping one peg over another to an empty space, removing the jumped peg. An example is shown below.

The goal is to remove all pegs except one. Your Prolog program needs to determine whether or not it is possible to solve a given puzzle, the puzzle could be of any size (the board could be of any size, containing any number of pegs in any configuration).

Your game should include the predicate solve which takes a list containing 1s and 0s representing pegs and holes respectively. The solve predicate should evalute to "Yes" if the list represents a puzzle that is solveable, "No" if it's not possible to reduce the puzzle to a single peg.

Some examples are shown below, in this case the prolog program is in the file pegs.pl:

?- ['pegs.pl'].
% pegs.pl compiled 0.00 sec, 1,900 bytes

Yes
?- solve([0,1,1]).

Yes
?- solve([1,1,1]).

No
?- solve([1,1,1,0,1,1,1]).

No
?- solve([1,0,1,1,1,1,0,1]).

No
?- solve([1,0,1,1,1,1,1,1]).

Yes

You should use SWI Prolog, which is available for Windows, Linux and Mac at www.swi-prolog.org. The web site also includes documentation (a reference manual) and links to lots of Prolog resources.

You can get an extra 10 points if your program prints out the list of moves it takes to solve the board. Something like this:

?- solve([0,1,1]).
[0, 1, 1] => [1, 0, 0]

Yes
?- solve([1,0,1,1,1,1,0,1]).

No
?- solve([1,0,1,1,1,1,1,1]).
[1, 0, 1, 1, 1, 1, 1, 1] => [1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1, 1, 1] => [1, 1, 0, 1, 0, 0, 1, 1]
[1, 1, 0, 1, 0, 0, 1, 1] => [1, 1, 0, 1, 0, 1, 0, 0]
[1, 1, 0, 1, 0, 1, 0, 0] => [0, 0, 1, 1, 0, 1, 0, 0]
[0, 0, 1, 1, 0, 1, 0, 0] => [0, 0, 0, 0, 1, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 0, 0] => [0, 0, 0, 1, 0, 0, 0, 0]

Yes

You can format the list of moves any way you want, the example above is just one way... It's fine to say something like "move peg at space 4 to space 6 removing the peg at space 5"

You can get partial credit as long as you provide a description of what the code does do and what is missing/broken.