[Haskell-cafe] Re: Pretty-printing peg solitaire boards

[Bertram Felgenhauer]

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