wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> 33 Pegs
        
(Message started by: rloginunix on Jul 24^th, 2016, 6:19pm)

Title: 33 Pegs
Post by rloginunix on Jul 24^th, 2016, 6:19pm

33 Pegs or Peg-Solitaire

The board of this game, favored by Gottfried Leibniz (the co-inventor of D&I Calculus), consists of 33 cells. In a classical scenario, each cell but exactly one - in dead center - (cell 17), initially, has one peg (coin/marble/pebble/etc) in it:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_33pegs01.png

The classical objective of this game is to leave exactly one peg on the board in dead center in the smallest number of moves each of which must follow these 'rectilinear checkers'-like rules:

r1) one atomic move must be one legal jump

r2) a jump is possible iff A, B and C are three adjacent cells in a column or row with either empty C and occupied A and B or empty A and occupied B and C (depicted):

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_33pegs02.png

- in either case, only a peg in a peripheral cell, A or C, may jump and it must:
- be carried over a middle peg, in B, and
- land in an adjacent empty cell, C or A

- a peg that was jumped over, in cell B, is removed from the board

r3) diagonal jumps are not allowed

r4) a game terminates when no more legal moves are left - there does not exist a single triplet of cells with the properties described in r2

Sample: initially, possible moves are: 5 to 17, 19 to 17, 29 to 17, 15 to 17. If '29 to 17' move was made then the peg in cell 24 is removed from the board and cells 29 and 24 become empty. Further, if a peg in cell 10 is chosen as a jumping peg then it must jump over a peg in cell 17 and it must land in cell 24 - it can not land in cell 29 despite the fact that that cell is empty ...

Atomic jumps may be strung together into contiguous chains (which, imho, should not reduce the number of moves).

Post your '1 in dead center' sequence.

(full disclosure: a C programmer, I have put together (and used) a Java program that does not search for a possible solution computationally but, rather, emulates a physical game and automatically records the moves made by a human:

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/rlu_33pegs03.png

if you wish - use it, with mouse-only, keyboard-only or a combination thereof, as is, no warranties, source code available upon request. To run: java -jar pegs.jar)

Title: Re: 33 Pegs
Post by alien2 on Jul 25^th, 2016, 9:01am

If Al Bundy had 33 Pegs he would probably lose his mind.

Title: Re: 33 Pegs
Post by dudiobugtron on Jul 31^st, 2016, 6:28pm

Is the challenge to get the solution with the least number of moves? Surely all solutions will have the same number of moves, though.
Or is it just to find a solution that is easy to repeat and remember?

Title: Re: 33 Pegs
Post by rloginunix on Aug 1^st, 2016, 8:16am

Despite the (thin) veneer of silliness, this puzzle has a fair amount of computer science heft to it - no nitpicking intended but what is 'the challenge' associated with this puzzle is debatable.

'A challenge' is to find 'a solution' - a sequence of jumps which, while clearing the board, terminate with a sole peg in cell 17.

Qualification of 'a solution' can be reserved for later: a sequence's memorialization is 'easy' thanks to cells' numbering.

Title: Re: 33 Pegs
Post by towr on Aug 1^st, 2016, 10:49am

My proposed solution is to work backwards with a bitarray of size 2^33, and for an increasing number of bits mark every index that leads to a solution.

So for 1 bit, index 2^16 gets marked as True, as it's the desired end state.
Then we proceed for every number with 2 up to 31 bits set, and check if any move leads to a marked solvable state.
And lastly you trace back from 2^33-2^16 through any solvable states to 2^16 to find a solution instance.
Should be solvable with roughly a 1GB memory pool and might be reasonably fast.

And you can improve it be cutting out a bit of redundancy (lots of rotational variants)
And maybe approaching it from both end could work. (After all, you can play the game in the opposite direction with a slightly different rule.)