In this post I will talk about the Towers Of Hanoi puzzle and create a few neat in-game visualizations for various puzzle sizes using ScriptCraft.
Towers Of Hanoi
The Towers Of Hanoi is a math puzzle that involves usually three poles and n disks. The puzzle starts with all the disks stacked on the left-most pole with the largest disk on the bottom and the smallest on top. For example, here is the initial configuration for a 3 disk puzzle….in the snow:
The object of the puzzle is to move all the disks from the left-most pole to the right-most while following these three rules:
- You can only move one disk at a time.
- You can only move the very top disk from a pole.
- You can only stack a smaller disk onto a bigger one.
Sketch It Out By Hand
Now that you have the initial configuration and the rules, grab a piece of scratch paper and see if you can sketch all the moves needed to complete a three disk puzzle. With three disks it will not take you long to draw them all out. If you get stuck check out the Towers Of Hanoi Wikipedia page for help.
Tracking & Visualizing Moves
Now that you are probably tired of drawing out moves manually, lets devise a recursive algorithm to solve this puzzle for an any number of disks. In fact, the Towers Of Hanoi is one of those fun and almost magical problems that if you characterize it the right way you can almost word for word translate it into a programming language. To solve a puzzle with n disks and three poles we have to:
- Move all the disks but the bottom disk (n – 1 disks) from the left pole to the middle pole.
- Move the bottom disk to the right-most pole.
- Move all the disks from the middle pole (n – 1 disks) to the right-most pole.
Running the above with ScriptCraft will cause the moves to be printed out. If you want to see how I rendered the move visualizations with colored wool checkout my Towers Of Hanoi Gist which you can drop into your ScriptCraft js-plugins directory and start creating move visualizations.
Comparing Puzzles Of Different Disk Size
Placing together visualizations from different disk-sized puzzles yields the most interesting results. Here is a picture showing Towers Of Hanoi moves starting on the left with 3 disks and ending with the moves required to solve an 8 disk puzzle on the right:
As you can see the number of moves required to solve the puzzle for every additional disk grows by leaps and bounds! Specifically for n disks the fewest moves required to solve a puzzle is moves.
- So if you have a puzzle with 10 discs it would take moves.
- A puzzle with 30 disks would take moves!
Is there a topic you would like to see covered here? I want to hear your input. Send me an email with any suggestions for future posts. If you liked this post, then you might also like Visualizing Sorting Algorithms In Minecraft.