236 CHAPTER13. ALGORITHMANALYSISANDDESIGN
0
5
10
15
20
25
30
35
0 500 1000 1500 2000 2500 3000
Seconds
List Size
’selSort’
’mergeSort’
Figure13.3:Experimentalcomparisonofselectionsortandmergesort.13.4.1 TowersofHanoi
Oneveryelegantapplicationofrecursive problemsolvingis thesolutiontoa mathematicalpuzzleusually
calledtheTowerofHanoiorTowerofBrahma. ThispuzzleisgenerallyattributedtotheFrenchmathe-
maticianEdouardLucas,whopublishedanarticleaboutit in1883.Thelegendsorroundingthepuzzlegoes
somethinglike this.
Somewhereina remoteregionoftheworldis a monasteryofa verydevoutreligiousorder. Themonks
have beenchargedwitha sacredtaskthatkeepstimefortheuniverse.Atthebeginningofallthings,the
monksweregivena tablethatsupportsthreeverticalposts.Ononeofthepostswasa stackof 64 concentric
goldendisks. Thedisksareofvaryingradiiandstackedintheshapeofa beautifulpyramid.Themonks
werechargedwiththetaskofmovingthedisksfromthefirstposttothethirdpost.Whenthemonkshave
completedtheirtask,allthingswillcrumbletodustandtheuniversewillend.
Ofcourse,if that’s allthereweretotheproblem,theuniversewouldhave endedlongago.To maintain
divineorder, themonksmustabidebycertainrules.
- Onlyonediskmaybemovedat a time.
- A diskmaynotbe“setaside.” It mayonlybestackedononeofthethreeposts.
- A largerdiskmayneverbeplacedontopofa smallerone.
Versionsofthispuzzlewerequitepopularat onetime,andyoucanstillfindvariationsonthisthemein
toy andpuzzlestores.Figure13.4depictsa smallversioncontainingonlyeightdisks.Thetaskis tomove
thetowerfromthefirstposttothethirdpostusingthecenterpostassortofa temporaryrestingplaceduring
theprocess.Ofcourse,youhave tofollow thethreesacredrulesgivenabove.
We wanttodevelopanalgorithmforthispuzzle.Youcanthinkofouralgorithmeitherasa setofsteps
thatthemonksneedtocarryout,orasa programthatgeneratesa setofinstructions.Forexample,if welabel
thethreepostsA,B andC.Theinstructionsmightstartoutlike this:
Move disk from A to C.