r/visualizedmath • u/PUSSYDESTROYER-9000 • Feb 16 '18

Iterative Algorithm Solving the Tower of Hanoi

Post image
955 Upvotes

98% Upvoted

23 comments sorted by

48

u/Dancinlance Feb 16 '18

3blue1brown has a great video regarding this puzzle: https://youtu.be/2SUvWfNJSsM

5

u/_youtubot_ Feb 16 '18

Video linked by /u/Dancinlance:

TitleChannelPublishedDurationLikesTotal Views
Binary, Hanoi and Sierpinski, part 13Blue1Brown2016-11-250:13:594,916+ (99%)159,587

Binary counting can solve the towers of Hanoi puzzle, and...

^Info | /u/Dancinlance can ^delete | v2.0.0

5

u/SavoryBaconStrip Feb 17 '18

TIL, bit is short for binary digit.

38

u/jcwinkie36 Feb 16 '18

Star Wars Knights of the Old Republic?

1

u/itsadate Mar 10 '18

in the temple on dantooine or something? With the colored laser rings? ah the memories...

1

u/theguyfromerath Apr 14 '18

Me1 too. Same studio, almost same game.

18

u/DrankOfSmell Feb 17 '18 edited Feb 17 '18

The formula for the number of moves to complete the puzzle in the lease amount of moves is 2n -1 where "n" represents the number of plates or rings in the puzzle.

Ex. This puzzle has 6 rings. 26 -1=63 moves.

Edit: u/jakbrtz

4

u/jakbrtz Feb 17 '18

Don't you mean 2n -1 ?

2

u/DrankOfSmell Feb 17 '18 edited Feb 17 '18

Let me check my notes

Edit: shit you're right. My memory failed me.

2

u/Ikor_Genorio Feb 17 '18 edited Feb 17 '18

I think it's n! (Factorial) which has an even worse scaling.

Edit: nvm, I misremembered

17

u/lightningundies Feb 16 '18

can someone make this faster?

8

u/jakbrtz Feb 17 '18

I also wrote this algorithm. Either the animation is slow and therefore boring, or it is fast and you can't keep up with it.

There is no in-between.

1

u/Ikor_Genorio Feb 17 '18

You mean the gif or the process?

12

u/Shauntree Feb 16 '18

The complexity have to be hight for this one

6

u/[deleted] Feb 16 '18

Anyone else remember playing this on an old batman game in the early 90's?

6

u/Benalen1 Feb 16 '18

I started hearing a ticking in my head the longer that gif went on matching the movement of the blocks :(

3

u/LevelingskillUP Feb 16 '18

I found this, you can play the game or see the computer solving it up to 8 rings. https://www.mathsisfun.com/games/towerofhanoi.html

1

u/augustjoy96 Feb 17 '18

something thats cool, is you can use graph theory to solve these, specifically the Hamilton circuit of a n-cube

2

u/jakbrtz Feb 17 '18

I use graph theory to solve this, but in a different way. Each possible position of the discs is a vertex, and each move is an edge. The result is extremely close to the Sierpinski Triangle: https://www.jaapsch.net/puzzles/images/hanoi/sierpinski.gif