Help with Peg Solitaire 15 hole triangle version

jspauli_at_gravity.phys.uwm.edu
Date: 08/22/04 

Date: 21 Aug 2004 19:42:12 -0700

I am trying to write a program in swi-prolog that solves a 15 hole
triangle (5 row max) peg solitaire (IQ) game. I have been programming
in
traditional imperative languages for quite some time, but thought
maybe prolog would lend itself to this problem best.

So, for the configuration

                      1
                     2 3
                    4 5 6
                   7 8 9 a
                  b c d e f

I believe I need to write some sort of list of legal moves,
represented as facts, not predicates. I tried writing a generalized
list of predicates such that you could try to move any given peg
sw,se,nw,ne, etc, etc. but I had no clue how to write the algorithm
that chooses the moves on various pegs (depth first search of a tree
of exactly 13 moves), which seems like a job for the prolog language
system itself anyway.

So on a second rendition I tried to use pattern matching of board
states,
so I had dozens of things like:

move([f,f,X,e,X,X,X,X,X,X,X,X,X,X,X],sw,[e,e,X,f,X,X,X,X,X,X,X,X,X,X,X])
:-
write ('Moved Peg 1 sw to hole 4').

then I had solution predicates such as:

solution( [e,e,e,e,e,e,e,e,e,e,e,e,e,e,f],[])

for each possible hole, such that the game is won
when there is only one peg left on the board.
I couldn't figure out how the recursive version of solution (the move
engine)
would work, however. This solution was based on a similar farmer,
goat, cabbage, wolf book by Adam Brooks Webber that covers several
non-imperative languages.
I thought it would be similar since essentially you need to maintain a
start
state, make one of a few basic moves, and end up at a goal state.

In C I could do this with a depth first search of a tree, and a stack
of moves,
but I thought prolog would do this for me, and find more than one
solution due
to its backtrace mechanism...so how do I teach it the rules of the
game?

Would something such as

move(1,2,4). be a better way (less verbose) of representing legal
moves, given
that most of the board never changes? What would the move engine look
like for
this? I would like to be able to feed in a board state, probably using
an
ordered list and get a result, but the initial board state could be
defined
using assert predicates as well.

I would really appreciate suggestions/example code, etc. Esp. via
email
in case I am without a news reader. jspauli(at)gravity.phys.uwm.edu

Thanks!

Relevant Pages

  • Re: Brew your own recession beer like the ancients
    ... circumference above the peg. ... If an amphora needed to be rolled on its peg, ... the peg would serve to lessen the wear on the bottom of the ... more stable in a hole in the dirt so a shallower hole for the bottom part can ...
    (sci.archaeology)
  • Re: Thread question - multi-threaded behavior
    ... > Here's a java problem I'm trying to work through. ... > one peg. ... > running game for each possible move. ... it increments a static variable and prints that out. ...
    (comp.lang.java.help)
  • Re: peg? dowel?
    ... it fits closely into its hole along all ... Pegs fit into their holes ... a "pegged joint" is one ... there is put a close-fitting peg. ...
    (alt.usage.english)
  • Thread question - multi-threaded behavior
    ... Here's a java problem I'm trying to work through. ... I wrote a program that solves a game a friend of mine calls the ... You play by jumping over a peg and removing it, ... problems from massive multitasking (althought I thought Java wouldn't ...
    (comp.lang.java.help)
  • Re: The Liar Paradox is merely an ill-formed statement
    ... :> If UTM outputs ACCEPT in response to an input, ... :> So, with this formulation, we don't have to worry about ... even if the definition of this machine were a hole ... peg should go in this hole, it would STILL be the case that THIS ...
    (sci.logic)