This used to be a famous puzzle among the high school math club circles I moved in 45 years ago. Once you know the iterative solution it becomes much easier to execute that the recursive one. On Sun, Jul 7, 2019, 4:31 PM Cris Moore <moore@santafe.edu> wrote:
The recursive solution to the Towers of Hanoi is well known. Here is a puzzle which a friend of mine and I found more challenging than we thought at first: give an _iterative_ algorithm, i.e., one which has no memory, and chooses its next move based only on the current state of the puzzle (and perhaps the knowledge of the initial and final peg for the entire stack of disks).
Hint: first come up with an iterative algorithm for the Gray code.
- Cris
p.s. The Santa Fe Institute has a copy of the French recreational mathematics magazine where Edouard Lucas proposed the Towers of Hanoi puzzle (he also, confusingly, mentions Benares). I like to point out that if a Vietnamese mathematician had invented the puzzle, it would presumably be called the Towers of Eiffel.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun