• Guest, we are pleased to inform you that Forum Promotion has been integrated with Discord. This means no matter where you are you can always stay connected to Forum Promotion. You can connect your Discord account to Forum Promotion by going to you account connected-accounts or by Clicking here. Once your account is connected and if you are part of the FP's Discord, you will automatically be given a role "Approved Users". And when ever a thread/post is created a notication will be posted in #new-threads and #new-posts.

Tower of Hanoi puzzle: Number of moves?

Ghost

Seasoned Veteran
Jun 25, 2009
2,995
97
120
Earth
wubur.com
FP$
1,175
How many moves does it take you to solve a 3 tower / 3 disc Tower of Hanoi?
The minimum number of moves possible is 7

I made this puzzle yesterday using HTML5 & Javascript. If you want, you can see the puzzle logic in JS. I'm happy to explain any part of it.

You can complete the puzzle here:
http://wubur.com/demo/Tower_of_Hanoi/

I'm interested in knowing how many moves it takes you to complete it.

The Rules
  1. You may only ever move the top disc from a pole/tower
  2. You cannot place a wider/larger disc on top of a smaller disc
  3. You must get all 3 discs from tower 1 (on the left) to tower 3 (on the right), in the same order they are now
  4. You must click a disc with your mouse & drag it to the tower you want to place it on. It will go back to its original spot if the rules prevent you from placing it on the desired tower. (Unfortunately this will not work on phones)

Start:


Finished:


The Javascript prevents you from breaking the rules & will tell you when you have successfully completed the Tower of Hanoi.

Good luck! :)
 
  • Like
Reactions: Gabnovatron

KyngzIndeyen

New Arrival
Nov 20, 2014
5
0
11
28
FP$
13
Didn't take me long to figure out how to do it in 7 moves.

Just in case anyone's in the least bit interested, here's a proof that, for an N-disc Tower of Hanoi, the minimum number of moves to complete it is 2^N - 1. I'll be using mathematical induction to do this:

Base case (N=1): Obviously, the 1-disc Tower of Hanoi can be solved in one move: just move the lone disc from the left-hand peg to the right-hand peg. Thus, the minimum number of moves is 1 (which is equal to 2^1 - 1).

Inductive hypothesis: Assume that the statement is true for some arbitrary integer N=K. Now, we want to show that it is also true for N=K+1.

Now, in order to solve the K+1-disc Tower of Hanoi, we need to do it in three stages:
  • Move the top K discs from the left peg to the middle peg;
  • Move the bottom disc from the left peg to the right peg;
  • Move the top K discs from the middle peg to the right peg.
The first stage requires 2^K - 1 moves (by the inductive hypothesis). The second stage requires one move (obviously). The third stage requires 2^K - 1 moves (again, by the inductive hypothesis). So, the total number of stages is:

(2^K - 1) + 1 + (2^K - 1) = 2*2^K - 1 = 2^(K+1) - 1

Hence, if the statement is true for some arbitrary integer N=K, then it is also true for N=K+1. Since the statement is true for N=1, it is true for all positive integers by mathematical induction.

(In particular, in the case N=3, the minimum number of steps is 2^3 - 1 = 8 - 1 = 7)
 

Ghost

Seasoned Veteran
Jun 25, 2009
2,995
97
120
Earth
wubur.com
FP$
1,175
Didn't take me long to figure out how to do it in 7 moves.

Just in case anyone's in the least bit interested, here's a proof that, for an N-disc Tower of Hanoi, the minimum number of moves to complete it is 2^N - 1. I'll be using mathematical induction to do this:

Base case (N=1): Obviously, the 1-disc Tower of Hanoi can be solved in one move: just move the lone disc from the left-hand peg to the right-hand peg. Thus, the minimum number of moves is 1 (which is equal to 2^1 - 1).

Inductive hypothesis: Assume that the statement is true for some arbitrary integer N=K. Now, we want to show that it is also true for N=K+1.

Now, in order to solve the K+1-disc Tower of Hanoi, we need to do it in three stages:
  • Move the top K discs from the left peg to the middle peg;
  • Move the bottom disc from the left peg to the right peg;
  • Move the top K discs from the middle peg to the right peg.
The first stage requires 2^K - 1 moves (by the inductive hypothesis). The second stage requires one move (obviously). The third stage requires 2^K - 1 moves (again, by the inductive hypothesis). So, the total number of stages is:

(2^K - 1) + 1 + (2^K - 1) = 2*2^K - 1 = 2^(K+1) - 1

Hence, if the statement is true for some arbitrary integer N=K, then it is also true for N=K+1. Since the statement is true for N=1, it is true for all positive integers by mathematical induction.

(In particular, in the case N=3, the minimum number of steps is 2^3 - 1 = 8 - 1 = 7)
Yes, that's correct. the formula can be used to figure out the minimum number of moves for any tower of hanoi setup. I'm glad you posted this, as I was too lazy to add it myself.
The minimum number of moves is indeed 7 for this tower of hanoi.

Congratulations to everyone who was able to do it in the minimum number of moves :)