1/15/2016
AlgorithmsandDataStructuresI
Module9:Recursion,PartII
Supplementalmaterial
TheTowerofHanoi
IntheTowerofHanoipuzzle:
Therearethreestacks(towers),numbered0,1,2.
ThereareNdisksnumbered0,...,N1.
=>0isthesmallest.
Initially,thedisksareplacedintower0,intheorderlargesttosmallest.
=>Smallestontop.
Goal:tomovethediskstotower1usingonlylegalmoves.
What'salegalmove?
Youcanmoveonlyadiskatthetopofatower.
Youcanmoveonlyonediskatatime.
Youcannotplaceadiskontopofasmallerone.
Wewillsolvetheproblemusing(ofcourse)recursion:
Therearethreekeystepsintherecursion:
Step1:movedisks0,...,N2fromtower0totower2
[Link]
1/20
1/15/2016
AlgorithmsandDataStructuresI
=>Subproblemofsmallersize.
Step2:movediskN1fromtower0totower1.
Step3:movedisks0,...,N2fromtower2totower1.
=>Subproblemofsmallersize.
Inpseudocode(withoutbasecase):
AlgorithmtowerOfHanoi(n,i,j)
Input:Disksnumbered0,...,naretobemovedfromtoweritotowerj
1.//...basecase...
//Firstfindthethirdtower,otherthaniandj:
2.k=otherTower(i,j)
//Step1:movedisks0,..,n1fromitok
[Link](n1,i,k)
//Step2:movedisk#nfromitoj
[Link](n,i,j)
//Step3:movedisks0,...,n1fromktoj
[Link](n1,k,j)
Thebasecase:moveasingledisk
[Link]
2/20
1/15/2016
AlgorithmsandDataStructuresI
Here'stheprogram:(sourcefile)
publicclassTowerOfHanoi{
publicstaticvoidmain(String[]argv)
{
//A3diskpuzzle:
[Link]("3Disksolution:");
solveHanoi(2,0,1);
//A4diskpuzzle:
[Link]("4Disksolution:");
solveHanoi(3,0,1);
}
staticvoidsolveHanoi(intn,inti,intj)
{
//Bottomout.
if(n==0){
//Thesmallestdisk.
move(0,i,j);
return;
intk=other(i,j);
solveHanoi(n1,i,k);//Step1.
move(n,i,j);//Step2.
solveHanoi(n1,k,j);//Step3.
staticvoidmove(intn,inti,intj)
{
//Fornow,we'llmerelyprintoutthemove.
[Link]("=>Movedisk#"+n+"fromtower"+i+"totower"+j);
}
staticintother(inti,intj)
{
//Giventwotowers,returnthethird.
if((i==0)&&(j==1)){
return2;
}
elseif((i==1)&&(j==0)){
return2;
}
elseif((i==1)&&(j==2)){
return0;
}
elseif((i==2)&&(j==1)){
return0;
}
elseif((i==0)&&(j==2)){
return1;
}
elseif((i==2)&&(j==0)){
return1;
}
//Weshouldn'treachhere.
return1;
}
}
Note:
Theaboveprogrammerelyprintsoutthemovesneeded
=>Wedon'tactuallymaintainthestateofeachtower.
[Link]
3/20
1/15/2016
AlgorithmsandDataStructuresI
Next,supposewewanttomaintainthestateofeachtower:
Theidealdatastructureisastack.
We'lluseonestackforeachtower.
Here'stheprogram:(sourcefile)
[Link].*;
publicclassTowerOfHanoi2{
//towers[0],towers[1]andtowers[2]arethethreestacks.
staticStack<Integer>[]towers;
publicstaticvoidmain(String[]argv)
{
//A3diskpuzzle:
[Link]("3Disksolution:");
solveHanoi(2,0,1);
//A4diskpuzzle:
[Link]("4Disksolution:");
solveHanoi(3,0,1);
}
staticvoidsolveHanoi(intn,inti,intj)
{
//Createthethreestacks.
towers=newStack[3];
for(intk=0;k<3;k++){
towers[k]=newStack<Integer>();
}
//Putdisks0,...,nonstack0.
for(intk=n;k>=0;k){
towers[0].add(k);
}
//Printtheinitialstack.
printTowers();
//[Link]:thisisthemethodbelow.
solveHanoiRecursive(n,i,j);
}
staticvoidsolveHanoiRecursive(intn,inti,intj)
{
//Bottomout.
if(n==0){
move(0,i,j);
return;
intk=other(i,j);
solveHanoiRecursive(n1,i,k);//Step1.
move(n,i,j);//Step2.
solveHanoiRecursive(n1,k,j);//Step3.
}
staticvoidmove(intn,inti,intj)
{
//Pulloutthetopdiskonstacki.
inttopVal=towers[i].pop();
//Putitonstackj.
towers[j].push(topVal);
//Printstatus.
[Link]("Towersaftermoving"+n+"fromtower"+i+"totower"+j);
printTowers();
}
[Link]
4/20
1/15/2016
AlgorithmsandDataStructuresI
staticintother(inti,intj)
{
//...
}
staticvoidprintTowers()
{
for(inti=0;i<[Link];i++){
[Link]("Tower"+i+":");
if(!towers[i].isEmpty()){
for(IntegerI:towers[i]){
[Link](""+I);
[Link]();
}
}
}
Note:
Sinceweneededtocreatethestacksaheadoftime,wemovedtherecursivepartofthecodeintoanewrecursive
methodsolveHanoiRecursive().
Toremoveadiskfromthetopofatower,wepop()fromthattower(stack):
//Pulloutthetopdiskonstacki.
inttopVal=towers[i].pop();
Toplaceadiskontopofatower,wepush()it:
//Putitonstackj.
towers[j].push(topVal);
NoticehowprintTowers()usesthe"collection"versionoftheforloop:
if(!towers[i].isEmpty()){
//Newtypeofforloop:
for(IntegerI:towers[i]){
[Link](""+I);
Astrangecompilationmessage:
Incompilingtheaboveprogram(withaJava1.5compiler),wegetawarning(notanerror):
Note:[Link].
Note:RecompilewithXlint:uncheckedfordetails.
Thisallowsyoutocontinuewithexecution.
Youcan,asitsuggests,recompilewiththeXlint:uncheckedoption:
javacXlint:[Link]
Whatyouseeasaresult:
[Link][Link]warning:[unchecked]uncheckedconversion
found:[Link][]
required:[Link][]
towers=newStack[3];
^
Thecompilerdidnotlikethestatement:
[Link]
5/20
1/15/2016
AlgorithmsandDataStructuresI
towers=newStack[3];
So,shouldthisinsteadhavebeen
towers=newStack<Integer>[3];
asonemightintuitivelyexpect?
Unfortunately,thatresultsinacompilationerror.
ThereasonisquiteesotericandhastodowiththegorydetailsofgenerictypesarehandledinJava.
Essentially,itboilsdowntothis:adeclarationlike
towers=newStack<Integer>[3];
isunsafebecauseonecanassignnonIntegerstackstotowers,whichiswhythecompilerdoesn'tallowit.
Thus,weareleftwithusingtheslightlylessunsafe
towers=newStack[3];
whichthecompilerallowsbutwarnsagainst.
GenerictypesinJavaconstitutealargeandsomewhatadvancedtopic,toocomplicatedforthiscourse.
Anapplication:diskbackupschedules
Supposewehavefourdisks(A,B,CandD)onwhichwewishtoperformbackupseachday.
=>Thisisadifferentmeaningofdisk(harddrive,removablemedia)
Eachdayweneedtochooseadiskonwhichtobackup
=>Thebackupschedule.
Oneoptionistogoroundrobin
Day0usediskA
Day1usediskB
Day2usediskC
Day3usediskD
Day4usediskA
Day5usediskB
...
(andsoon)
Withthissystem,wecanonlygobackatmostfourdays.
Wearenotabletoretrievethestateofthesystemfrom,say,6daysago.
Anotherapproach:staggerthedisks:
Day0usediskA
Day1usediskB
Day2usediskA
Day3usediskC
Day4usediskA
Day5usediskB
Day6usediskA
Day7usediskD
Day8usediskA
...
(andsoon)
Withthisapproach,we'dhaveadistributionlike
DiskA1or2daysbefore
DiskBatmost4daysbefore
DiskCatmost8daysbefore
DiskDatmost16daysbefore
[Link]
6/20
1/15/2016
AlgorithmsandDataStructuresI
Thisdistributionallowsadeeperreachintothepast.
ThesequenceaboveisexactlytheTowerofHanoimovesequencefordisksnumberedA,B,CandD.
Recursion:areview
First,let'sreviewasimpleexamplefromModule4:
Recalltherecursivecomputationofpower:
//Computeab
staticintpower(inta,intb)
{
//Bottomout:
if(b==0){
return1;
}
//Recursion:
return(a*power(a,b1));
}
What'simportant:
Wemusttestforthebottomoutcasebeforerecursing.
Thebottomoutcaseteststhevalue(orvalues)oftheparameter(orparameters)thatchangesinthe
recursion.
=>Thesearetheparametersthatcontroltherecursion.
Therecursivecallsmustchange(usuallydecrease)theparametersthatcontroltherecursion.
=>Above,thereisonlyonerecursivecall,butTowerofHanoihastwo.
Howrecursionworks:
Eachmethodcallcreatesanactivationrecordonthesystemstack.
Theactivationrecordconsistsofspaceallocatedfortheparticularparametersandlocalvariablesforthat
methodcall.
Thus,arecursivecallresultsinanewactivationrecordforeachsuchrecursivecall.
=>Thisiswhyeachexecutionofthemethodretainsitsownparametersandlocalvariables.
Theactivationrecordalsoknowsthatwhenexecutionofamethodcallcompletes,executionreturnstothe
callingmethodjustafterthecalledmethodwascalled.
Forrecursionit'snodifferentexceptthatit'sthesamecodeinvolvedinallmethodcalls.
Thebestwaytounderstandrecursioninitiallyistodrawthestackpictureandworkthroughanexample.
Let'snowreviewanotherexamplefromModule4:
Thisisthepermutationseatingexamplewhereweprintthearrangement:
//Theparameterstothismethodare:
//numSpacestotalnumberofremainingseatsavailable
//numRemainingtotalnumberofpeoplelefttoseat
//seatsanarraywhereseats[i]==0ifseatisavailable
//personwhichpersonweneedtoseat
staticvoidprintPermutations(intnumSpaces,intnumRemaining,int[]seats,intperson)
{
//Bottomoutcase.
if(numRemaining==0){
//Print.
[Link]([Link](seats));
return;
}
[Link]
7/20
1/15/2016
AlgorithmsandDataStructuresI
//Otherwise,nonbasecase:lookforanemptyspotfor"person"
for(inti=0;i<[Link];i++){
if(seats[i]==0){
//Emptyspot.
seats[i]=person;
//Recursivelyassignremaining,startingwithperson+1
printPermutations(numSpaces1,numRemaining1,seats,person+1);
//Important:weneedtoundotheseatingforothertrials.
seats[i]=0;
}//endfor
}
What'ssimilaraboutthisrecursivemethod:
Theparameterthatcontrolsrecursionis:numSpaces
=>Thisiswhatwecheckinthebottomoutcase.
Otherparameterspassalonginformation:personandseats.
What'sdifferent(fromthepower()example):
Whenwefillintheseatsarray,weundothisassignmentaftertherecursivecall:
//Makesomechangetoaparameter:
seats[i]=person;
//Recurse:
printPermutations(numSpaces1,numRemaining1,seats,person+1);
//Undothechange(restoretheoriginal)forfuturerecursions:
seats[i]=0;
Twotypesofrecursion:
Recursionwhereyoudon'tundochanges.
=>Sometimesthisiscalledtailrecursion.
Recursionwhereyouneedtoundochangessothatyoucanproperlyexploreallpossibilities
=>Sometimesthisiscalledrecursionwithbacktracking.
Manyexamplesoftailrecursioncaneasilybewrittennonrecursively(usingiteration)
=>Formanyoftheseexamples(power,factorial,fibonacci),it'sbettertouseiteration.
However,whenthere'sbacktracking,itcanbeverydifficulttoavoidrecursion.
Mazeconstructionandtraversal:a(long)exampleofrecursionwithbacktracking
Wewillnowexamineamazeapplicationindetailtoillustraterecursionwithbacktracking:
First,wewilluserecursiontocreateamazelikethis:
[Link]
8/20
1/15/2016
AlgorithmsandDataStructuresI
Then,wewilluserecursiontosolvesuchamaze(byfindingapathfromagivenstartcell(e.g.,thetopleft)toa
givenendcell(e.g.,thebottomright):
WewillputawholebunchofusefulcodeinaclasscalledMazeandinsteadfocusonusingthatclassthroughits
methods.
[Link]
9/20
1/15/2016
AlgorithmsandDataStructuresI
We'llusethiscellnumberingconvention:
Rowsstartnumberingat0,andincreasedownwards.
Columnsstartat0andincreaserightwards.
Thus,thetopleftcellis(0,0).Theonetoitsrightis(0,1)andtheonedirectlybelowis(1,0).
Tostartwith,let'sexaminethemethodsintheclassMaze:
Theconstructor:wecreateaninstancebyspecifyingthenumberofrowsandcolumns:
Mazemaze=newMaze(5,5);
Ourexampleswillusesquaremazes.
display():callthismethodtodisplaythemaze:
Mazemaze=newMaze(5,5);
//BringuptheGUI:
[Link]();
breakWall():
Initially,[Link],wewill"breakwalls"
betweenneighboringcells.
Forexample,wecanbreakthewallbetweencells(3,4)and(2,4)asfollows:
Mazemaze=newMaze(5,5);
//NotetheuseoftheCoordclass:
Coordc1=newCoord(3,4);
Coordc2=newCoord(2,4);
[Link](c1,c2);
[Link]();
Or,alternatively,withshortercode:
Mazemaze=newMaze(5,5);
//Createaninstancedirectlyinthemethodargumentlist:
[Link](newCoord(3,4),newCoord(2,4));
[Link]();
TheCoordclasslookslikethis:
publicclassCoord{
publicintrow=1,col=1;
publicCoord(intr,intc)
{
row=r;
col=c;
}
publicStringtoString()
{
return"["+row+","+col+"]";
}
Thus,toaccessthestoredcoordinates:
Coordc=newCoord(3,4);
[Link]("Row="+[Link]+"Col="+[Link]);
[Link]
10/20
1/15/2016
AlgorithmsandDataStructuresI
//Or,toprintbothusingtoString():
[Link](c);
Anumberofmethods(intheclassMaze)allowustomarkandunmarkcellsasvisited:
markVisited(Coordc):markcellcasvisited.
markUnVisited(Coordc):markcellcasnotvisited.
markAllUnvisited():markallcellsasunvisited.
isVisited(Coordc):seewhethercellchasbeenvisited.
Anumberofmethodsrelatedtofetchingalist(array)ofacell'sneighbors:
Coord[]getUnvisitedClosedNeighbors(Coordc):getcellc'sneighborsthatareclosedofffromc(there's
awallbetween)andhaven'tbeenvisitedyet.
Coord[]getClosedNeighbors(Coordc):getneighborsofcthatshareawall(unbroken)withcwhether
visitedornot.
Coord[]getUnvisitedOpenNeighbors(Coordc):getthoseneighborsofcforwhichwecanwalkthrough
totheneighbor(nowall)andwhichhaven'tbeenvisited.
EachofthesemethodsreturnanarrayofCoordinstances.
Afewadditionalusefulmethods:
copy():makeafullcopyofthemaze,asin:
Mazem=newMaze(5,5);
//...dostuff:breakwallsetc...
Mazem2=[Link]();
//[Link]'taffectm2.
setSolutionPath(LinkedList<Coord>solutionPath):wewillcallthismethodoncewehaveconstructed
asolution.
We'llnowwriteourfirstattempt:
Wewilltrytogenerateamazepathofagivenpathlength.
Thekeyidea:
Algorithm:recursiveGenerate(Coordc)
[Link]
[Link]
//Otherwise...
3.c'=Pickarandomneighborofcellc
[Link](c')
Here'stheprogram:(sourcefile)
publicclassMazeMaker{
//Thesevariableswillbeusedacrossmethods:
staticintdesiredPathLength;
staticMazemaze;
publicstaticvoidmain(String[]argv)
{
generateMaze(5,5);
}
publicstaticvoidgenerateMaze(intnumRows,intnumCols)
{
maze=newMaze(numRows,numCols);
//Wewanttogenerateapathofthislength:
desiredPathLength=numRows*numCols;
//Initially,we'llstartwiththetopleftcellandmarkthatasvisited.
Coordstart=newCoord(0,0);
[Link](start);
[Link]
11/20
1/15/2016
AlgorithmsandDataStructuresI
//Generatethemazepathrecursively.
booleanfound=recursiveGenerate(start,1);
if(!found){
[Link]("Couldnotcreatethewholemaze");
}
[Link]();
}
staticbooleanrecursiveGenerate(Coordc,intpathLength)
{
//Bottomoutcondition1:
if(pathLength==desiredPathLength){
//[Link]'vecreateamazepathofthedesiredlength.
returntrue;
}
//Bottomoutcondition2:seeifthere'saneighbortovisit.
Coord[]validNeighbors=[Link](c);
if((validNeighbors==null)||([Link]==0)){
//There'[Link].
returnfalse;
}
//Otherwise,pickarandomneighborandproceed.
inti=[Link](0,validNeighbors.length1);
//Breakthewallandmarktheneighborasvisited.
[Link](c,validNeighbors[i]);
[Link](validNeighbors[i]);
//Recurse.
returnrecursiveGenerate(validNeighbors[i],pathLength+1);
}
}
Nextattempt:
Simpletailrecursioncangetstuck.
=>Weneedawayto"undo"pathsandtrydifferentneighbors.
Wewillpickaneighbortoexplorerecursively
=>Ifthatdoesn'tworkout,we'lltryanother.
Here'stheprogram:(sourcefile)
publicclassMazeMaker2{
staticintdesiredPathLength;
staticMazemaze;
publicstaticvoidmain(String[]argv)
{
generateMaze(5,5);
}
publicstaticvoidgenerateMaze(intnumRows,intnumCols)
{
maze=newMaze(numRows,numCols);
desiredPathLength=numRows*numCols;
//Initially,we'llstartwiththetopleftcell.
Coordstart=newCoord(0,0);
[Link](start);
//Generatethemazepathrecursively.
[Link]
12/20
1/15/2016
AlgorithmsandDataStructuresI
booleanfound=recursiveGenerate(start,1);
if(!found){
[Link]("Couldnotcreatethewholemaze");
}
[Link]();
}
staticbooleanrecursiveGenerate(Coordc,intpathLength)
{
//Bottomoutcondition1:
if(pathLength==desiredPathLength){
returntrue;
}
//Bottomoutcondition1:seeifwe'restuck.
Coord[]validNeighbors=[Link](c);
if((validNeighbors==null)||([Link]==0)){
returnfalse;
//Otherwise,wehavesomeneighborstoexplore.
//Permutethedirectionsrandomly.
permute(validNeighbors);
for(inti=0;i<[Link];i++){
//Tryneighbori.
[Link](c,validNeighbors[i]);
[Link](validNeighbors[i]);
booleanok=recursiveGenerate(validNeighbors[i],pathLength+1);
if(ok){
//Ifneighboriworkedout,great.
returntrue;
//Otherwise,undoassignmenttoi.
[Link](c,validNeighbors[i]);
[Link](validNeighbors[i]);
}//endfor
//Couldn'tmakeitwork.
returnfalse;
staticvoidpermute(Coord[]coords)
{
for(inti=0;i<[Link];i++){
//Findarandomelementtoplaceintoithplace.
intk=(int)[Link](i,coords.length1);
Coordtemp=coords[i];
coords[i]=coords[k];
coords[k]=temp;
}
}
}
Note:
Thekeyideaistotryasmanyneighborsasneeded:
Algorithm:recursiveGenerate(Coordc)
[Link]
[Link]
[Link]
//Otherwise...
[Link]'ofc
[Link]=recursiveGenerate(c')
[Link]
[Link]
13/20
1/15/2016
AlgorithmsandDataStructuresI
[Link]
[Link]
[Link]
//Wereachhereonlyifeveryneighbordidnotworkout.
[Link]
Notehowweundoabrokenwall:
for(inti=0;i<[Link];i++){
//Tryneighbori.
[Link](c,validNeighbors[i]);
[Link](validNeighbors[i]);
//...recursionhere...
//Toundo:repairthewallandmarkasUNvisited.
[Link](c,validNeighbors[i]);
[Link](validNeighbors[i]);
}//endfor
Amazewithchoices:
Theabovemazepathhasnochoices
=>There'sonlyonewayfromthetoplefttotheendofthepath.
Wewillbuilduponthistocreateamazewithchoices
=>Aftergeneratingthelongpath,we'llbreaksomerandomwalls.
Here'stheprogram:(sourcefile)
publicclassMazeMaker3{
//...variables...
publicstaticvoidmain(String[]argv)
{
generateMaze(5,5);
}
publicstaticvoidgenerateMaze(intnumRows,intnumCols)
{
//...createandgeneratesinglepathmaze...
//Breakafewmorewalls,randomly.
breakRandomWalls(maze,10);
[Link]();
}
staticbooleanrecursiveGenerate(Coordc,intpathLength)
{
//...sameasbefore...
}
staticvoidbreakRandomWalls(Mazemaze,intnumWalls)
{
for(intk=0;k<numWalls;k++){
//Createrandomcoordinates,i.e.,identifyarandomcell.
intx=[Link](0,maze.numRows1);
inty=[Link](0,maze.numCols1);
Coordc=newCoord(x,y);
//Getitsneighborsthatareseparatedbyawall.
Coord[]validNeighbors=[Link](c);
if(validNeighbors!=null){
[Link]
14/20
1/15/2016
AlgorithmsandDataStructuresI
//Pickoneandbreakthewall.
intm=[Link](0,validNeighbors.length1);
[Link](c,validNeighbors[m]);
}
}
}
Let'sturnourattentiontosolvingthemaze:
We'llfirsttryasimpleidea:
Algorithm:recursivelyFindPath(Coordc)
[Link]
[Link]
[Link]
4.//Otherwisesearchfurther...
5.c'=pickarandom"open"neighbor
[Link]'isnull
//Stuck:couldn'tfindapath.
[Link]
[Link]
[Link](c')
Here'stheprogram:(sourcefile)
[Link].*;
publicclassMazeMaker4{
staticintdesiredPathLength;
staticMazemaze;
publicstaticvoidmain(String[]argv)
{
Mazemaze=generateMaze(5,5);
if(maze!=null){
//Wewillseekapathfromthetoplefttothebottomrightcorner.
Coordstart=newCoord(0,0);
Coordend=newCoord(4,4);
solveMaze(maze,start,end);
[Link]();
else{
[Link]("Mazecreationdidnotwork");
}
}
//Apathisalistofcells,i.e.,alistofCoordinstances.
staticLinkedList<Coord>solutionPath;
staticvoidsolveMaze(Mazemaze,Coordstart,Coordend)
{
//We'[Link]:
[Link]();
//Markthestartcellasvisited.
[Link](start);
//Createthelist.
solutionPath=newLinkedList<Coord>();
//Recursivelyfindthepathandfillincoord'sintothelist.
recursivelyFindPath(maze,start,end);
//PassthepathintotheGUI.
[Link](solutionPath);
[Link]
15/20
1/15/2016
AlgorithmsandDataStructuresI
}
staticbooleanrecursivelyFindPath(Mazemaze,Coordc,Coordend)
{
//Firstaddthecurrentcellintothepath.
[Link](c);
//Ifwe'vereachedtheend,we'redone.
if(([Link]==[Link])&&([Link]==[Link])){
returntrue;
}
//Otherwise,let'sfindaneighbortoexplore.
Coord[]validNeighbors=[Link](c);
if(validNeighbors==null){
//Iftherearen'tany,we'redone,butcouldn'tfindapath.
returnfalse;
//Takethefirstoneandexplorefromthere.
[Link](validNeighbors[0]);
returnrecursivelyFindPath(maze,validNeighbors[0],end);
//...Mazegenerationcode...sameasbefore...
}
Asolutionthatworks:
Whenexploringaneighbor,weneedawaytoundo(backtrack)ifitdoesn'tleadtoasolution.
Theideaistotryallpossibleneighbors,asmanyasneeded:
Algorithm:recursivelyFindPath(Coordc)
[Link]
[Link]
[Link]
4.//Otherwisesearchfurther...
[Link]"open"neighborc'
[Link]=recursivelyFindPath(c')
[Link]
[Link]'topath
[Link]
[Link]
[Link]
[Link]
Here'stheprogram:(sourcefile)
[Link].*;
publicclassMazeMaker5{
//...variables...sameasbefore(forgeneration)...
publicstaticvoidmain(String[]argv)
{
//...same...
}
//Apathisalistofcells,i.e.,alistofCoordinstances.
staticLinkedList<Coord>solutionPath;
[Link]
16/20
1/15/2016
AlgorithmsandDataStructuresI
staticvoidsolveMaze(Mazemaze,Coordstart,Coordend)
{
//We'[Link]:
[Link]();
//Markthestartcellasvisited.
[Link](start);
//Createthelist.
solutionPath=newLinkedList<Coord>();
//Recursivelyfindthepathandfillincoord'sintothelist.
recursivelyFindPath(maze,start,end);
//[Link]?
[Link](start);
//PassthepathintotheGUI.
[Link](solutionPath);
}
staticbooleanrecursivelyFindPath(Mazemaze,Coordc,Coordend)
{
//Ifwe'vereachedtheend,we'redone.
if(([Link]==[Link])&&([Link]==[Link])){
returntrue;
}
//Otherwise,let'sfindaneighbortoexplore.
Coord[]validNeighbors=[Link](c);
if(validNeighbors==null){
//Ifwecouldn'tfindanyneighborstoexplore,we'restuck.
returnfalse;
}
//Tryeachneighbor,asmanyasneeded.
for(inti=0;i<[Link];i++){
//Tryneighbori.
[Link](validNeighbors[i]);
booleanfound=recursivelyFindPath(maze,validNeighbors[i],end);
if(found){
//Noticethatweaddthistothefrontofthelist,andonly
//afterthesolutionhasbeenfounduptohere.
[Link](validNeighbors[i]);
returntrue;
//Ifneighborididn'tworkout,undothevisitandcontinue.
[Link](validNeighbors[i]);
}
//Ifwereachedhere,thennoneoftheneighborsworkedout.
returnfalse;
}
}
TheNQueensproblem
Inthisproblem:
WearegivenanNxNchessboardandMqueens(whereM<=N).
Thegoalistoplacethequeensontheboardsothatnoqueen"attacks"another.
[Link]
17/20
1/15/2016
AlgorithmsandDataStructuresI
Forexample(N=8):
Recallthataqueencanattackanysquareinitsrow,columnordiagonal,e.g.
Wewillofcoursesolvethisrecursively:
Thisisanotherexampleofrecursionwithbacktracking.
Keyideas:
We'llproceedcolummbycolumn(lefttoright).
Whensolvingforthecurrentcolumn,trytoplaceaqueenoneachpossiblerow,andsolvethesub
problem(startingwiththenextcolumn)recursively.
Pseudocode:
Algorithm:solve(n,c)
Input:n=thenumberofqueenstoassign,c=thecolumntostartwith
//...Bottomoutconditions...(we'lldothislater)
[Link]
[Link][r,c]isanonattackedsquare
[Link][r,c]
[Link]=solve(n1,c+1)//Assignremainingn1recursively
[Link](found)
[Link]
[Link]
[Link]
[Link]
[Link]
18/20
1/15/2016
AlgorithmsandDataStructuresI
//Wereachhereifnoneoftherowsincolumncworkedout.
[Link]
Thus,wetryeveryrowforaqueenandtrytosolvethesubproblemwithfewerqueens.
=>Ififthatgetssolved,wecanplacethequeenthereandrecursebackup
Thebottomoutconditions:
Checkiftherearenomorequeenstoassign
=>Problemgetssolved.
Checkiftherearenomorecolumnstotry
=>Nosolutionexists.
WewillbuildaclasscalledChessBoardwithmethodsthathidemostofthemessyboardmanipulationdetails:
addQueen(row,col):addaqueeninsquare[row,col].
removeQueen(row,col):removethequeeninsquare[row,col].
booleanisForbidden(row,col):seeif[row,col]isanattackedsquare.
display():tobringupaGUIwiththeboarddisplayed.
Here'stheprogram:(sourcefile)
[Link].*;
[Link].*;
publicclassNQueens{
staticChessBoardboard;
publicstaticvoidmain(String[]argv)
{
solveQueens(8,8);
}
staticvoidsolveQueens(intnumQueens,intsize)
{
board=newChessBoard(size);
booleansolutionExists=solve(numQueens,0);
if(!solutionExists){
[Link]("Nosolutionfor"+numQueens+"ona"+size+"x"+size+"board");
return;
}
[Link]("Solutionfoundfor"+numQueens+"ona"+size+"x"+size+"board");
[Link](board);
[Link]();
}
staticbooleansolve(intnumQueens,intwhichCol)
{
//Bottomoutcondition1:
if(numQueens==0){
//Nonetoassigndone.
returntrue;
}
//Bottomoutcondition2:
if(whichCol>=[Link]()){
//Nocolumnslefttotrydone.
returnfalse;
}
//Tryeveryunforbiddenspotineachrow.
for(introw=0;row<[Link]();row++){
if(){
[Link]
19/20
1/15/2016
AlgorithmsandDataStructuresI
//Trythislocation.
[Link](row,whichCol);
booleansolutionExists=solve(numQueens1,whichCol+1);
if(solutionExists){
returntrue;
}
//Else,undo
[Link](row,whichCol);
}
}
//Couldn'tfindasolution.
returnfalse;
}
}
[Link]
20/20
