### European Peg Solitaire Solvability

**Source:**Wikipedia article on Peg Solitaire

**Problem:**

The European version of the popular game "Brainvita" (or "Peg Solitaire") looks as follows:

Y Y O O O Y Y

Y O O O O O Y

O O O O O O O

O O O T O O O

O O O O O O O

O O O O O O O

Y O O O O O Y

Y Y O O O Y Y

Prove that the initial configuration as shown in the representation is not solvable.

**Background:**

The game fills the entire board with pegs except for the central hole. The objective is, making valid moves, to empty the entire board except for a solitary peg. A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg.

**Similar Problems:**

Sam Loyd Puzzle Solvability

Solution posted by Pritish Kamath (CSE IITB 2012 Alumnus, Assistant Researcher MSR Bangalore) in comments!

**Update:**Solution posted by Pritish Kamath (CSE IITB 2012 Alumnus, Assistant Researcher MSR Bangalore) in comments!

If you cover your board with three colours in the following manner :

ReplyDelete..abc..

.abcab.

abcabca

bcabcab

cabcabc

.bcabc.

..abc..

Let A, B and C be the number of pebbles on colours 'a', 'b' and 'c' respectively. The relative parity of A, B and C remains conserved after every move. And initially, A = B = C = 12. Hence it is unsolvable.

PS : By relative parity, I mean [A (xor) B] and [B (xor) C] are conserved.

Basically, if initially, A:odd B:odd C:even, then after any number of moves, it'll either be A:odd B:odd C:even or A:even B:even C:odd

What is logic behind conservation of relative parity?

DeleteJust colour it like a chess board. Then we will have 16 pegs in black and 20 pegs in white (or vice versa). A valid move always gets a peg into the same colour and a peg is removed from the same colour. So, definitely one peg from each of the colour will remain no matter what.

ReplyDelete@Pritish, Thanks for the correct solution.

ReplyDelete@Crazy Dino, Your solution is not correct.