Regarding The Brain Puzzler: If you continue the gray code pattern past the solution point, you don't return to 00000000 after the remaining 86 moves, but rather you end up with the move after 10000000, which would be 110000000 (9 bits) if you had a 9th peg. Consider the sequence for a 4-peg Brain Puzzler. Assume you start at 0000, and the goal is to reach 1111. A peg can be moved if and only if the one immediately below it (if any) is 1, and all of the pegs below that one are 0. There is a 10-move solition. Continuing the pattern, after 15 moves you reach 1000. After that the pattern breaks, because the next move would be the non-existent 5th peg: 0 0000 1 0001 2 0011 3 0010 4 0110 5 0111 6 0101 7 0100 8 1100 9 1101 10 1111 11 1110 12 1010 13 1011 14 1001 15 1000 If there were a 5th peg, the pattern would continue: 16 11000 17 11001 18 11011 19 11010 20 11110 21 11111 22 11101 23 11100 24 10100 25 10101 26 10111 27 10110 28 10010 29 10011 30 10001 31 10000 After a total of 31 moves, the low-order 4 bits would return to 0000 for the first time, but not before reaching 1111 a second time (at move 21, the 5-peg solution). A 32nd move would require 6 pegs, and would leave the low-order 4 bits 0000, and the sequence for those bits would repeat. Note that the solution lengths alternate between doubling the move count vs. doubling it and then adding one. I remember playing with The Brain Puzzler as a kid. I found it very satisfying. Once your fingers got used to the pattern, you could chug away at it really fast without any pauses. Tom James Propp writes:
Actually, now that I'm getting ready to write this up, I realize that I'm confused.
If we've got a Hamiltonian circuit on the 8-cube coming from a Gray code of length 8, and we have a path of length 170 from 00000000 to 11111111, don't we also have a path of length 256-170=86 from 11111111 back to 00000000? Wouldn't traversing this path in reverse give us a path of length 86 from 00000000 to 11111111? So isn't there a solution for The Brain (aka "The Brain Puzzle") that takes only 86 moves?
Jim Propp
On Wed, May 8, 2019 at 11:50 AM James Propp <jamespropp@gmail.com> wrote:
That's perfect!
I see that in particular the Gray-code-based puzzle "The Brain Puzzler" takes 170 moves to solve:
https://everything2.com/title/The+Brain+Puzzler
Thanks, Michael!
Jim