wu :: forums
« wu :: forums - 33 Pegs »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 2:40am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   easy
(Moderators: Grimbal, ThudnBlunder, Eigenray, towr, william wu, SMQ, Icarus)
   33 Pegs
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: 33 Pegs  (Read 6550 times)
rloginunix
Uberpuzzler
*****





   


Posts: 1026
33 Pegs   pegs.jar.pdf
« on: Jul 24th, 2016, 6:19pm »
Quote Quote Modify Modify

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:
 

 
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):
 

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

 
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)
IP Logged
alien2
Uberpuzzler
*****






   


Gender: male
Posts: 6981
Re: 33 Pegs  
« Reply #1 on: Jul 25th, 2016, 9:01am »
Quote Quote Modify Modify

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


dudiobugtron
Uberpuzzler
*****





   


Posts: 735
Re: 33 Pegs  
« Reply #2 on: Jul 31st, 2016, 6:28pm »
Quote Quote Modify Modify

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?
IP Logged
rloginunix
Uberpuzzler
*****





   


Posts: 1026
Re: 33 Pegs  
« Reply #3 on: Aug 1st, 2016, 8:16am »
Quote Quote Modify Modify

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: 33 Pegs  
« Reply #4 on: Aug 1st, 2016, 10:49am »
Quote Quote Modify Modify

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.)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board