[Haskell-cafe] Re: Pretty-printing peg solitaire boards
Bertram Felgenhauer
bertram.felgenhauer at googlemail.com
Mon Nov 26 02:13:02 EST 2007
Maur??cio wrote:
> I have to rebuild it due to a bug. However, I'm
> doing that because there's a single position which
> my brother could not solve, and he believes it to
> be impossible, so we want to check:
>
> #0#
> ###0###
> #######
> #######
> ###
> ###
I guess you meant
> #0#
> #0#
> ###0###
> #######
> #######
> ###
> ###
This indeed can not be solved. Color the Solitaire board as follows,
abc
bca
abcabca
bcabcab
bca
cab
Let A, B, and C be the number of pegs that have color a, b, and c,
respectively. Every move replaces a peg of two of the colors by a peg
of the third color. So no move changes the parities of A+B, B+C or C+A.
Now for your example, A+B, B+C and C+A are initially even. It's easy
to see that with a single peg left two of these numbers must be odd,
and therefore there is no solution.
(I think you can find this argument in "Winnning Ways for your
mathematical plays" by Berlekamp, Conway and Guy somewhere.)
HTH,
Bertram
More information about the Haskell-Cafe
mailing list