Towers of Hanoi (Posted on 2003-09-07)

	Submitted by Lewis
Rating: 3.0667 (15 votes)
Solution:	(Hide)
The shortest method takes 31 steps: XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 M from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 XS from pole 1 to pole 3 L from pole 1 to pole 2 XS from pole 3 to pole 2 S from pole 3 to pole 1 XS from pole 2 to pole 1 M from pole 3 to pole 2 XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 XL from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 XS from pole 1 to pole 3 M from pole 2 to pole 1 XS from pole 3 to pole 2 S from pole 3 to pole 1 XS from pole 2 to pole 1 L from pole 2 to pole 3 XS from pole 1 to pole 3 S from pole 1 to pole 2 XS from pole 3 to pole 2 M from pole 1 to pole 3 XS from pole 2 to pole 1 S from pole 2 to pole 3 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.

	Subject	Author	Date
	Puzzle Thoughts	K Sengupta	2024-03-15 00:06:22
	No Subject	Arjun	2007-09-08 12:20:37
	re: A non-recursive solution	Xen	2004-05-25 16:17:04
	re(2): Stacks--Basic version	Charlie	2003-09-09 14:14:52
	re: Stacks--Basic version	Charlie	2003-09-09 14:07:51
	Parity	Brian Smith	2003-09-09 10:06:49
	Stacks	DJ	2003-09-08 13:28:35
	A non-recursive solution	Federico Kereki	2003-09-08 13:18:33
	C++ function	DJ	2003-09-08 12:29:22
	follow this order	Ryan	2003-09-08 02:28:36
	You blew it, Lewis !!!!!	Dan	2003-09-08 01:22:33
	re: Recursion challenge	Charlie	2003-09-07 16:12:32
	re(2): strategy	Charlie	2003-09-07 15:48:01
	re: solution in 11 moves with 5 poles	Gamer	2003-09-07 15:40:06
	solution in 19 moves	Victor Zapana	2003-09-07 15:13:01
	Recursion challenge	Gamer	2003-09-07 14:19:04
	re: strategy	Gamer	2003-09-07 14:15:48
	strategy	Charlie	2003-09-07 11:23:12
	re: Holy Hula Hoops!	Charlie	2003-09-07 11:14:04
	Steps to follow (not for the impatient)	Jun	2003-09-07 10:41:04
	Number of moves	Jill	2003-09-07 10:35:31
	Holy Hula Hoops!	Eric	2003-09-07 10:12:37