RecursiveBacktracking.pdf

《RecursiveBacktracking.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Topic13BacktrackingRecursiveBacktrackingStartSuccess!"Inancienttimes,beforecomputerswereinvented,alchemistsstudiedthemysticalpropertiesofSuccess!numbers.Lackingcomputers,theyhadtorelyondragonstodotheirworkforthem.Thedragonswerecleverbeasts,butalsolazyandbad-tempered.FailureTheworston

2、eswouldsometimesburntheirkeepertoacrispwithasinglefierybelch.ButmostdragonsProblemspaceconsistsofstates(nodes)andactionsweremerelyuncooperative,asviolencerequiredtoo(pathsthatleadtonewstates).Wheninanodecanmuchenergy.ThisisthestoryofhowMartin,ancanonlyseepathstoconnectednodesalchemis

3、t’sapprentice,discoveredrecursionbyoutsmartingalazydragon."Ifanodeonlyleadstofailuregobacktoits"parent"-DavidS.Touretzky,CommonLisp:AGentleIntroductiontonode.Tryotheralternatives.IftheseallleadtofailureSymbolicComputationthenmorebacktrackingmaybenecessary.CS3142RecursiveBacktrackingA

4、MoreConcreteExampleSolvingSudoku–BruteForce
Sudoku
Abruteforcealgorithmisa
9by9matrixwithsomesimplebutgeneralnumbersfilledinapproach
allnumbersmustbebetween
Tryallcombinationsuntil1and9youfindonethatworks
Goal:Eachrow,eachcolumn,
Thisapproachisn’tclever,andeachminimatrixmustcontainth

5、enumbersbetweenbutcomputersarefast1and9onceeach
Thentryandimproveon–noduplicatesinrows,columns,thebruteforceresutsorminimatricesCS3143CS3144RecursiveBacktrackingRecursiveBacktrackingSolvingSudokuAttendanceQuestion1
BruteforceSudokuSoluton
Afterplacinganumberinacellisthe–ifnotopencell

6、s,solvedremainingproblemverysimilartotheoriginal1–scancellsfromlefttoright,problem?toptobottomforfirstopenA.YescellB.No–Whenanopencellisfoundstartcyclingthroughdigits1to9.–Whenadigitisplacedcheckthatthesetupislegal–nowsolvetheboardCS3145CS3146RecursiveBacktrackingRecursiveBacktrackin

7、gSolvingSudoku–LaterStepsSudoku–ADeadEnd112124
Wehavereachedadeadendinoursearch12489124812489uhoh!
WiththecurrentsetupnoneoftheninedigitsworkinthetoprightcornerCS3147CS3148RecursiveBacktrackingRecursiveBacktrackingBackingUpCharacteristicsofBruteForce
Whenthesearchreachesadead12489and

8、Backtracking