Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 15, 2012

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
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:
Rubik's Cube
Sam Loyd Puzzle Solvability

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

3 comments:

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

    ..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

    ReplyDelete
  2. Just 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
  3. @Pritish, Thanks for the correct solution.
    @Crazy Dino, Your solution is not correct.

    ReplyDelete