Tower of Hanoi

Author

Eric W. Weisstein
January 31, 2006

This notebook downloaded from http://mathworld.wolfram.com/notebooks/RecreationalMath/TowerofHanoi.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/TowerofHanoi.html.

©2006 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

Code borrowed and adapted from
Jaime Rangel-Mondragón
"Generalized Hanoi Tower"
http://library.wolfram.com/infocenter/MathSource/4861/

Code

h3[1]:={1}
h3[n_]:=h3[n]=Join[h3[n-1],{n},h3[n-1]]

hanoi3[1,i_,j_]:={{i,j}}
hanoi3[n_,i_,j_]:=Join[hanoi3[n-1,i,6-i-j],{{i,j}},hanoi3[n-1,6-i-j,j]]

disp[t_,{i_,j_}]:=Module[{q=t,d},
d=First[(Subscript[q, [[i]]])];
(Subscript[q, [[i]]])=Rest[(Subscript[q, [[i]]])];
(Subscript[q, [[j]]])=Prepend[(Subscript[q, [[j]]]),d];
q]

towers[n_]:=FoldList[disp,{Range[n],{},{}},hanoi3[n,1,3]]

h[n_,li_]:=Module[{y=-0.5},
{
{RGBColor[1,0,0],Rectangle[{-0.2,0},{0.2,n/2+0.5}]},Map[(y=y+0.5;Rectangle[{-#,y},{#,y+0.5}])&,Reverse[li]],
{SandyBrown,Rectangle[{-n-.5,-.5},{n+.5,0}]}
}
]

shift[g_,x_]:=g/.Rectangle[r__]:>Rectangle@@Transpose[Transpose[{r}]+{x,0}]

Towers[{a_,b_,c_}]:=Module[{n=Length[Flatten[{a,b,c}]]},Graphics[{h[n,a],
shift[h[n,b],2n],
shift[h[n,c],4n]},AspectRatio->Automatic,PlotRange->{{-n-.5,5n+1},{-1, n}}]
]

List of Disk Numbers to be Moved at Each Step

Using h3

h3/@Range[4]//ColumnForm

By Hand

s[1]:={1}
s[n_]:=s[n]=Flatten[{s[n-1],n,s[n-1]}]

s/@Range[4]//ColumnForm

Same as binary carry sequence plus 1

h3[5]

Table[IntegerExponent[n,2],{n,31}]+1

Steps for n Disks

On Three Rods

RSolve[{h[n]==2h[n-1]+1,h[1]==1},h[n],n]

On Four Rods

s[1]:=1
s[n_]:=s[n]=s[n-1]+2^Floor[(Sqrt[8n-7]-1)/2]

s/@Range[50]

x=Floor[(Sqrt[8n-7]-1)/2];

Table[1+(n-x(x-1)/2-1)2^x,{n,50}]

Figure

Show[GraphicsArray[Transpose[Partition[movie=Towers/@towers[4],8]]],
ImageSize->500]

Animation

<<Utilities`GIF`;

Export[gifs<>"hanoi.gif",movie,ConversionOptions->{"AnimationDisplayTime"->1}]//Timing