This site requires JavaScript, please enable it in your browser!
Greenfoot back

Report as inappropriate.

shrucis1
shrucis1 presents ...

2013/12/9

Tower of Hanoi

Tower of Hanoi:
The Tower of Hanoi, also known as the Tower of Brahma or Lucas' Tower, is a mathematical game or puzzle. It consists of three rods, and several disks of different sizes that slide on and off of the rods. You begin the puzzle with all the disks stacked in ascending order with largest on the bottom, on one of the rods, forming a conical shape. The goal of the puzzle is to move the entire stack of disks to another rod, following a few simple rules:
1. Only one disk can be moved at a time.
2. In every move, you may only take the top disk from a stack.
3. A larger disk cannot be placed on top of a smaller disk.
(http://en.wikipedia.org/wiki/Tower_of_Hanoi)


Using these rules makes for a simple yet interesting puzzle. Supposedly, the origin of the puzzle comes from a legend about Hindu priests. So the story goes, there was once an Indian temple which contained a large room with three large posts. On these posts were 64 giant, golden disks. According to the legend, they believed that when the last move of the puzzle was completed, the world would end. However, to complete this would require over 18 quintillion steps, a step consisting of moving the top ring from one post to another.

Instructions:
Type a number in the text field and press start to begin with that many rings on the far left 'rod'. I have chosen not to depict the rods, although there are only three possible locations for every 'ring', giving the appearance of invisible rods. Each ring is a random color every time. Hope you enjoy it! By the way, as danpost pointed out in the comments, the formula giving the minimum number of moves to complete the puzzle is ((2^n)-1), where n is the number of rings.

Credit to bourne for his GUI Components, the button and the textfield

Side Note:
I solved the tower of hanoi puzzle using recursion, where you reference a method from inside the method, although there are other ways to do it iteratively. I chose not to do this, as the recursive solution presented itself to me more clearly and before the iterative one did. If you would like to learn more about recursion and its applications, I highly recommend it, as it is a very useful skill to have.

4312 views / 853 in the last 7 days

3 votes | 0 in the last 7 days

Tags: simulation with-source puzzle math

open in greenfoot
Your browser is ignoring the <APPLET> tag.
HTML5 version not available | Scenario not running?
A new version of this scenario was uploaded on Mon Dec 09 15:17:41 UTC 2013 Fixed a bug that Super_Hippo pointed out. Still somewhat glitchy after 11 rings. Occasionally a ring will move to a tower and overlap over another ring without moving to the top. This can only happen with larger numbers of rings, I believe it only occurs after 11 rings, although I am not sure. This overlap affects the aesthetic of the model, but note, it does not affect the solution.
Super_HippoSuper_Hippo

2013/12/9

Like a half million, I guess. Well, I took the highest number possible and thought, it would be a much faster. :)
shrucis1shrucis1

2013/12/9

It'd take 524,287 steps. I haven't modified it so it goes faster the more rings you use. If you download it, you can use Greenfoot's speed control, but when you put that at the maximum, it's much more likely to make errors, and still takes a LONG time to do 19.
JetLennitJetLennit

2013/12/9

@Kartoffolot here is a link to one that goes to 8 http://www.greenfoot.org/scenarios/4715
Super_HippoSuper_Hippo

2013/12/9

Amazing, on full speed, it is exactly what I expected here on the site. Good, that the speed graph is not linear. Although I can only see the first five digits of the number. Some errors occurred, which only affected, as you said, the aesthetic. Good work :) By the way, the speed setting should not affect the amount of errors. It could lag, but for me, it does not lag at all. It is just very fast and even this half million does not take that long.
KartoffelbrotKartoffelbrot

2013/12/9

@ JetlLennit: Thanks @ shrucis1: You don't need them to be dragable. Just make three buttons. First click for selecting, second click for placing.
danpostdanpost

2013/12/9

I did want to show the algorithm I used to effectively solve the puzzle; however, I did not want to upload the scenario and take anything (view/votes) from yours. I will supply a link to the new discussion thread with the code once it is started.
danpostdanpost

2013/12/9

I posted my world class code at the following link: http://www.greenfoot.org/topics/5099
KartoffelbrotKartoffelbrot

2013/12/10

Wow, very fair danpost!
A new version of this scenario was uploaded on Sun Dec 22 19:23:18 UTC 2013 Now shows the rings

See all comments

Want to leave a comment? You must first log in.

Who likes this?

nachocab JetLennit Kartoffelbrot