You might have heard of the _Tower of Hanoi_, the disk-moving puzzle with three pegs, but have you heard of _Reve’s Puzzle_? Follow Darren and Vivien as they add one more peg and solve this twist on the Tower of Hanoi through some simple intuition, coding, and math. The speed-up with the optimal Reve's solution will surprise you! Python code that simulates both puzzles is shared in GitHub (links below).
Tower of Hanoi: A Flawed Doomsday Device
The Tower of Hanoi puzzle was invented by French mathematician Édouard Lucas in 1883. It was inspired by the myth that there was a temple where God gave the priests 64 gold disks on a pole, each one a little smaller than the one beneath it, and two other empty poles. Their task was to move the 64 disks from the first pole to the third using the second one as temporary storage, with one constraint that a large disk could never be placed on top of a smaller one. When they finished their work, the world would end.
Tower of Hanoi is a flawed doomsday device, however. At the speed of one move per second, it will take about 585 billion years to complete the 64-disk move, 42 times as long as the age of our universe!
Correction 12/2/2023
At timestamp 11:43, the minimum number of moves to complete the 32-disk Hanoi should have been 4.29 billion moves instead of 429 million moves. It will take 136 years to complete 4.29 billion moves, at the speed of 1 move/sec. Please accept our apologies for the oversight.
References
- Survey Paper of Reve’s Puzzle and Variations: www.cs.wm.edu/~pkstoc/boca.pdf
- Optimal Move Counts for Reve’s Puzzle: oeis.org/A007664 You can validate some results from our Python implementation against the number sequence here.
- Google Colab: colab.research.google.com/
- GitHub code: github.com/Darren-Kao/Reves-P...
Video Chapters
00:00 Problem Statement: Tower of Hanoi and its flaw as a doomsday device.
01:02 Introduction to Tower of Hanoi, optimal solution algorithm and time complexity.
04:29 GitHub Python code for Tower of Hanoi.
06:08 Introduction to Reve’s Puzzle, optimal solution algorithm and time complexity.
08:15 GitHub Python code for Reve’s Puzzle.
09:29 Decomposing a Reve’s puzzle into a sequence of Hanoi puzzles.
11:43 Results and the Verdict: A much-improved doomsday device!
#puzzle #algorithm #python