All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Towers of Hanoi (Posted on 2003-09-07) Difficulty: 3 of 5
You have three small poles and five hoops - XS, S, M, L, XL (as in extra small, small, medium, large and extra large). They are placed on pole 1 in order, with largest at the bottom.

You can move one hoop at a time, and the hoops you are not moving have to be on a pole. You also cannot place a hoop on top of a smaller one. How can you move the hoops so that they are in the same order as they are now, but on pole 3?

  Submitted by Lewis    
Rating: 3.0667 (15 votes)
Solution: (Hide)
The shortest method takes 31 steps:
  1. XS from pole 1 to pole 3
  2. S from pole 1 to pole 2
  3. XS from pole 3 to pole 2
  4. M from pole 1 to pole 3
  5. XS from pole 2 to pole 1
  6. S from pole 2 to pole 3
  7. XS from pole 1 to pole 3
  8. L from pole 1 to pole 2
  9. XS from pole 3 to pole 2
  10. S from pole 3 to pole 1
  11. XS from pole 2 to pole 1
  12. M from pole 3 to pole 2
  13. XS from pole 1 to pole 3
  14. S from pole 1 to pole 2
  15. XS from pole 3 to pole 2
  16. XL from pole 1 to pole 3
  17. XS from pole 2 to pole 1
  18. S from pole 2 to pole 3
  19. XS from pole 1 to pole 3
  20. M from pole 2 to pole 1
  21. XS from pole 3 to pole 2
  22. S from pole 3 to pole 1
  23. XS from pole 2 to pole 1
  24. L from pole 2 to pole 3
  25. XS from pole 1 to pole 3
  26. S from pole 1 to pole 2
  27. XS from pole 3 to pole 2
  28. M from pole 1 to pole 3
  29. XS from pole 2 to pole 1
  30. S from pole 2 to pole 3
  31. XS from pole 1 to pole 3
First, to find the shortest method, pretend there is only one hoop. Obviously, you only have to move it to the third pole, and you're done.

Then, the case with two hoops. You have to move the top hoop to the 'extra' pole (2), then move the bottom hoop to the third pole, and then put the smaller hoop back on top of it.

For three hoops, you have to move the top two hoops to the extra pole (the same way you would put two hoops onto the third pole), then put the third one where you want it, and put the two hoops back on top of it (again, the same way as moving just two hoops).

Thus, it can be reasoned that the least number of steps it takes to move n hoops will twice the number of steps it took to move n-1 hoops, plus the one step to move the largest hoop to the third pool. (Sn = 2Sn-1 + 1).

The least number of moves it will take to move 5 hoops, then, is:
2(2(2(2(1)+1)+1)+1)+1=31

Several methods were offered in the comments to solve this.
Charlie posted a BASIC program here that uses recursion to solve the problem.
DJ posted a C++ program here with a similar recursion, that also shows the state of the poles after each move.
Frederico Kereki posted a simple, non-recursive method here that also yields the simplest solution.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
No SubjectArjun2007-09-08 12:20:37
Some Thoughtsre: A non-recursive solutionXen2004-05-25 16:17:04
re(2): Stacks--Basic versionCharlie2003-09-09 14:14:52
re: Stacks--Basic versionCharlie2003-09-09 14:07:51
ParityBrian Smith2003-09-09 10:06:49
SolutionStacksDJ2003-09-08 13:28:35
SolutionA non-recursive solutionFederico Kereki2003-09-08 13:18:33
Some ThoughtsC++ functionDJ2003-09-08 12:29:22
follow this orderRyan2003-09-08 02:28:36
You blew it, Lewis !!!!!Dan2003-09-08 01:22:33
re: Recursion challengeCharlie2003-09-07 16:12:32
re(2): strategyCharlie2003-09-07 15:48:01
re: solution in 11 moves with 5 polesGamer2003-09-07 15:40:06
solution in 19 movesVictor Zapana2003-09-07 15:13:01
QuestionRecursion challengeGamer2003-09-07 14:19:04
re: strategyGamer2003-09-07 14:15:48
strategyCharlie2003-09-07 11:23:12
re: Holy Hula Hoops!Charlie2003-09-07 11:14:04
Steps to follow (not for the impatient)Jun2003-09-07 10:41:04
Number of movesJill2003-09-07 10:35:31
Holy Hula Hoops!Eric2003-09-07 10:12:37
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information