Tower of Hanoi puzzle: Number of moves?

Discussion in 'Intellectual Talk' started by Ghost, Mar 13, 2019.

  1. Ghost

    Ghost Seasoned Veteran

    2,962
    27
    115
    +63
    0
    -0
    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:
    [​IMG]

    Finished:
    [​IMG]


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

    Good luck! :)
     
    • Like Like x 1
  2. Empire

    Empire Valued Contributor Valued Contributor

    20,547
    1,541
    320
    +2,216
    124
    -0
    I think I leave it to I have time.. I reply in 6 years later :p
     
  3. Lämmchen

    Lämmchen Up-and-Coming Sensation

    261
    62
    35
    +84
    0
    -0
    Nice puzzle. I did it in 7 moves.
     
  4. Bluezone777

    Bluezone777 Dinner Team Leader

    868
    191
    140
    +379
    4
    -0
    I finished the puzzle in 7 moves as well.
     
  5. KyngzIndeyen

    KyngzIndeyen New Arrival

    5
    0
    11
    +0
    0
    -0
    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)
     
  6. Empire

    Empire Valued Contributor Valued Contributor

    20,547
    1,541
    320
    +2,216
    124
    -0
    You lost me already
     
  7. Gabnovatron

    Gabnovatron New Arrival

    7
    2
    3
    +2
    0
    -0
    I finished in 7.
     
  8. Ghost

    Ghost Seasoned Veteran

    2,962
    27
    115
    +63
    0
    -0
    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 :)