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 Example8Sdk8Sudoku89 by 9 matrix with some b fill d inumbers filled in8all numbers must be between 1 and 91 and 98Goal: 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 Force88A brute force algorithm is a simple but general approach8Try all combinations until you find one that works8This approach isn’t clever, s app oac s c e e ,but computers are fast8Then try and improve onThen try and improve on the brute force resutsCS 307 Fundamentals of Computer Science Recursive Backtracking4Solving Sudoku88Brute 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 188After 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 End88We have reached a dead end in our search12 4898With the current set up none of the nine digits work in the top right cornerCS 307 Fundamentals of Computer Science Recursive Backtracking8gpgBacking Up8Wh h h h d d8When 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 digit8We 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 next12498Now 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 Backtracking8Brute force algorithms are slowg8The 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 yy8But, 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 Insights8Af i l i di i i ll l8After 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?!?!?!?8After 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.8We need to know if things worked out (found a solution) or they didn't, and if they didn't try the next number8If 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 Backtracking88Problems such as Suduko can be solved using recursive backtracking8recursive because later versions of the problem are just slightly simpler versions of the original8backtracking 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 Backtracking8Possible goalsPossible goals– Find a path to successFind all paths to success–Find all paths to success– Find the best path to success8N t ll bl tl lik d8Not 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 Problem88A 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 Problem8Pl NQ Nb N h b d th t8Place N Queens on an N by N chessboard so that none of them can attack each other8Number of
View Full Document
Unlocking...