Author |
Topic: 33 Pegs (Read 6550 times) |
|
rloginunix
Uberpuzzler
Posts: 1026
|
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:
Posts: 6981
|
|
Re: 33 Pegs
« Reply #1 on: Jul 25th, 2016, 9:01am » |
Quote 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 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 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:
Posts: 13730
|
|
Re: 33 Pegs
« Reply #4 on: Aug 1st, 2016, 10:49am » |
Quote 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
|
|
|
|