From: cet1@cus.cam.ac.uk (Chris Thompson)
Newsgroups: sci.math
Subject: Re: Peg Solitaire - help!
Date: 13 Nov 1997 16:42:23 GMT

In article <64euke$n3f@singer.cent.gla.ac.uk>,
Alastair Norrie  <9341861n@student.gla.ac.uk> wrote:
>I was wondering if anyone could help me regarding the possible number of 
>permutations to peg solitaire there are?

English or Continental board?

If by "permutations" you mean "positions", there is an obvious space of
2^33 [English] or 2^37 [Continental] positions (not all of which can 
actually be reached from others, e.g. the all-full and all-empty
ones), as each hole can be either full or empty.

Apart from the rotational and reflective symmetries (take out a factor
of about 2^3), there is also the division of the positions into 16=2^4
equivalence classes by the "rule of three" (see [WW]). Positions in
different equivalence classes cannot be reached from each other.

>I am working on a genetic algorithm to try and 'create' a solution for a 
>university project, and I wanted to try and estimate the size of the 
>search space.  (This will in effect justify an evolutionary route rather 
>than an exhaustive search.)  Unfortunately, my mathematics isn't that 
>strong, and I can't seem to get my head round the problem.

I would recommend the chapter on Peg Solitaire in the 2nd volume of

 [WW] "Winning Ways", Berlekamp, Conway & Guy

were it not for the fact that (a) it does need a modicum of mathematical
ability to follow, & (b) once you have seen how much structure the game has, 
you may become disenchanted with the idea of attacking it with a sledgehammer.

>Oh, and by the way, it's not just solutions that I need to count, it is 
>ALL attempts that end in failure as well as success.

Here you seem to be wanting to count *games* (i.e. move sequences), not 
*positions*. [I hope we aren't going to have a repeat of those awful posts
>from  Herr Plutonium in which he was unable to distinguish the two concepts
for Chess...]

Chris Thompson
Email: cet1@cam.ac.uk

==============================================================================
From: David Stretch <dds@leicester.ac.uk>
Newsgroups: sci.math
Subject: Re: RE- Chris - Solitaire Help
Date: 21 Nov 1997 16:33:27 -0000

In article <19971121115801.GAA00663@ladder01.news.aol.com>,
QSCGZ <qscgz@aol.com> wrote:
>>If you know how many 'games' there are, I would be bery grateful
>>if you could drop me a note.......
>
>
> ( peg-solitaire , 32 pegs )
>
>
>my estimate :  2^60

I cannot comment on whether this number is correct or not. However, I
know a source which might either contain an answer, or give references
to where such an answer can be found, or something else of
relevance. (I can't re-read it, and the index doesn't list an entry
which refers to the number of games.) 

It is:

Beasley, J.D. (1992). _The ins and outs of peg solitaire._ from the
"recreations in mathematics" series (ed. David Singmaster). Oxford,
OUP Paperbacks. ISBN: 0-19-286145-X. It cost me \pounds 7.99.

pp.xii+275

There are 15 chapters, split into sections. The content is formal
where necessary, and goes into some depth, referring to Conway's work,
as well as other developments. The book discusses variant boards,
variant rules, and different kinds of problems set on the same size
and shape boards. I found it gave me an interesting insight into the
underlying logic and mathematics of this game. In short, given that
the original enquirer was asking because of his desire to write a simulation of
some aspect of Solitaire play, I suspect this may be quite a fruitfuil
book for him to look at.

I hope this helps.

-- 
David D Stretch: Greenwood Institute of Child Health, Univ. of Leicester, UK.
Lecturer in Mathematical Psychology.                Phone:+44 (0)116-254-6100  
dds@leicester.ac.uk  http://www.leicester.ac.uk/CWIS/AD/GWINST/greenwood.html