Topic 10 RiBktkiRecursive Backtracking"In ancient times, before computers were invented,In ancient times, before computers were invented, alchemists studied the mystical properties of numbers. Lacking computers, they had to rely on dragons to do their work for them The dragonsdragons to do their work for them. The dragons were clever beasts, but also lazy and bad-tempered. The worst ones would sometimes burn their keeper to a crisp with a single fiery belch But most dragonsto a crisp with a single fiery belch. But most dragons were merely uncooperative, as violence required too much energy. This is the story of how Martin, an alchemist’s apprentice discovered recursion byalchemist s apprentice, discovered recursion by outsmarting a lazy dragon."- David S. Touretzky, Common Lisp: A Gentle Introduction to Symbolic ComputationCS 307 Fundamentals of Computer Science Recursive Backtracking1Symbolic ComputationBacktrackingStartSuccess!Success!FailureProblem space consists of states (nodes) and actionsp()(paths that lead to new states). When in a node cancan only see paths to connected nodesIf a node only leads to failure go back to its "parent"node. Try other alternatives. If these all lead to failureCS 307 Fundamentals of Computer Science Recursive Backtracking2ythen more backtracking may be necessary.A More Concrete ExampleSdkSudoku9 by 9 matrix with some b fill d inumbers filled inall numbers must be between 1 and 91 and 9Goal: Each row, each column, and each mini matrix mustand each mini matrix must contain the numbers between 1 and 9 once each1 and 9 once each– no duplicates in rows, columns, or mini matricesCS 307 Fundamentals of Computer Science Recursive Backtracking3Solving Sudoku – Brute ForceA brute force algorithm is a simple but general approachTry all combinations until you find one that worksThis approach isn’t clever, s app oac s c e e ,but computers are fastThen try and improve onThen try and improve on the brute force resutsCS 307 Fundamentals of Computer Science Recursive Backtracking4Solving SudokuBrute force Sudoku Soluton– if not open cells, solved1– scan cells from left to right, top to bottom for first open llcell– When an open cell is found t t li th h di it 1start cycling through digits 1 to 9. When a digit is placed check–When a digit is placed check that the set up is legalnow solve the boardCS 307 Fundamentals of Computer Science Recursive Backtracking5–now solve the boardAttendance Question 1After placing a number in a cell is the remaining problem very similar to the original problem?A. YesB. NoCS 307 Fundamentals of Computer Science Recursive Backtracking6Solving Sudoku – Later Steps1 12 12 412 481248912489uh oh!uh oh!CS 307 Fundamentals of Computer Science Recursive Backtracking7Sudoku – A Dead EndWe have reached a dead end in our search12 489With the current set up none of the nine digits work in the top right cornerCS 307 Fundamentals of Computer Science Recursive Backtracking8gpgBacking UpWh h h h d dWhen the search reaches a dead end in backs upto the previous cell it was trying to fill and goes12 489cell it was trying to fill and goes onto to the next digitWe would back up to the cell withWe would back up to the cell with a 9 and that turns out to be a dead end as well so we back up again1249pg– so the algorithm needs to remember what digit to try next1249Now in the cell with the 8. We try and 9 and move forward again.CS 307 Fundamentals of Computer Science Recursive Backtracking9Characteristics of Brute Forceand Backtrackingand BacktrackingBrute force algorithms are slowgThe don't employ a lot of logic–For example we know a 6 can'tgointhelast3For example we know a 6 can t go in the last 3 columns of the first row, but the brute force algorithm will plow ahead any waygp yyBut, brute force algorithms are fairly easy to implement as a first pass solutionimplement as a first pass solution– backtracking is a form of a brute force algorithmCS 307 Fundamentals of Computer Science Recursive Backtracking10Key InsightsAf i l i di i i ll lAfter trying placing a digit in a cell we want to solve the new sudoku boardIsn't that a smaller (or simpler version) of the same–Isn't that a smaller (or simpler version) of the same problem we started with?!?!?!?After placing a number in a cell the we need toAfter placing a number in a cell the we need to remember the next number to try in case things don't work out.We need to know if things worked out (found a solution) or they didn't, and if they didn't try the next numberIf we try all numbers and none of them work in our CS 307 Fundamentals of Computer Science Recursive Backtracking11cell we need to report back that things didn't workRecursive BacktrackingProblems such as Suduko can be solved using recursive backtrackingrecursive because later versions of the problem are just slightly simpler versions of the originalbacktracking because we may have to try bac ac g because e ay a e o ydifferent alternativesCS 307 Fundamentals of Computer Science Recursive Backtracking12Recursive BacktrackingP d d f i b kt kiPseudo code for recursive backtracking algorithms If at a solution, report successfor( every possible choice from current state /for( every possible choice from current state / node)Make that choice and take one step along pathUitlthblfthd/ttUse recursion to solve the problem for the new node / stateIf the recursive call succeeds, report the success to the next high levelB k t f th t h i t t th t t t thBack out of the current choice to restore the state at the beginning of the loop.Report failureCS 307 Fundamentals of Computer Science Recursive Backtracking13pGoals of BacktrackingPossible goalsPossible goals– Find a path to successFind all paths to success–Find all paths to success– Find the best path to successN t ll bl tl lik dNot all problems are exactly alike, and finding one success node may not be the dfth hend of the searchStartSuccess!Success!CS 307 Fundamentals of Computer Science Recursive Backtracking14The 8 Queens ProblemThe 8 Queens ProblemCS 307 Fundamentals of Computer Science Recursive Backtracking15The 8 Queens ProblemA classic chess puzzle– Place 8 queen pieces on a chess board so that none of them can attack one anotherCS 307 Fundamentals of Computer Science Recursive Backtracking16The N Queens ProblemPl NQ Nb N h b d th tPlace N Queens on
View Full Document