13.4. HARDPROBLEMS 237
Figure13.4:TowerofHanoipuzzlewitheightdisks.Move disk from A to B.
Move disk from C to B.
...
Thisis a difficultpuzzleformostpeopletosolve. Ofcourse,thatis notsurprising,sincemostpeopleare
nottrainedinalgorithmdesign.Thesolutionprocessis actuallyquitesimple—ifyouknow aboutrecursion.
Let’s startbyconsideringsomereallyeasycases.Supposewehave a versionofthepuzzlewithonly
onedisk.Movinga towerconsistingofa singlediskis simple—wejustremove it fromAandputit onC.
Problemsolved.OK,whatif therearetwo disks?I needtogetthelargerofthetwo disksovertopostC,but
thesmalleroneis sittingontopofit.I needtomove thesmallerdiskoutoftheway, andI candothisby
movingit topostB.Now thelargediskonA is clear;I canmove it toC andthenmove thesmallerdiskfrom
postB ontopostC.
Now let’s thinkabouta towerofsizethree.Inorderto move thelargestdiskto postC,I firsthave to move
thetwo smallerdisksoutoftheway. Thetwo smallerdisksforma towerofsizetwo.UsingtheprocessI
outlinedabove, I couldmove thistoweroftwo ontopostB,andthatwouldfreeupthelargestdisksothatI
canmove it topostC.ThenI justhave tomove thetoweroftwo disksfrompostB ontopostC.Solvingthe
threediskcaseboilsdowntothreesteps.
- Move a toweroftwo fromA toB.
- Move onediskfromA toC.
- Move a toweroftwo fromB toC.
Thefirstandthirdstepsinvolve movinga towerofsizetwo.Fortunately, wehave alreadyfiguredouthow to
dothis.It’s justlike solvingthepuzzlewithtwo disks,exceptthatwemove thetowerfromA toB usingC
asthetemporaryrestingplaceandthenfromB toC,usingA asthetemporary.
We have justdevelopedtheoutlineofa simplerecursive algorithmforthegeneralprocessofmovinga
towerofany sizefromoneposttoanother.
Algorithm: move n-disktower from source to destination via restingplace
move n-1 disk towerfrom source to resting place
move 1 disk tower fromsource to destination
move n-1 disk towerfrom resting place to destination