Topic 10 Recursive BacktrackingBacktrackingA More Concrete ExampleSolving Sudoku – Brute ForceSolving SudokuAttendance Question 1Solving Sudoku – Later StepsSudoku – A Dead EndBacking UpCharacteristics of Brute Force and BacktrackingKey InsightsRecursive BacktrackingSlide 13Goals of BacktrackingThe 8 Queens ProblemSlide 16The N Queens ProblemAttendance Question 2Reducing the Search SpaceA Solution to 8 QueensN QueensSlide 22Another Backtracking Problem A Simple MazeThe Local ViewModified Backtracking Algorithm for MazeBacktracking in ActionSlide 27Slide 28Slide 29Slide 30Slide 31Path Eventually FoundMore Backtracking ProblemsOther Backtracking ProblemsThe CD problemAnother Backtracking ProblemAirline List – Part 1Airline List - Part 2Airline List - Part 3Problem ExampleCS 307 Fundamentals of Computer Science Recursive Backtracking1Topic 10 Recursive Backtracking"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 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 dragons were merely uncooperative, as violence required too much energy. This is the story of how Martin, an alchemist’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 Backtracking2BacktrackingStartSuccess!Success!FailureProblem space consists of states (nodes) and actions(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 failurethen more backtracking may be necessary.CS 307 Fundamentals of Computer Science Recursive Backtracking3A More Concrete ExampleSudoku9 by 9 matrix with some numbers filled inall numbers must be between 1 and 9Goal: Each row, each column, and each mini matrix must contain the numbers between 1 and 9 once each–no duplicates in rows, columns, or mini matricesCS 307 Fundamentals of Computer Science Recursive Backtracking4Solving Sudoku – Brute ForceA brute force algorithm is a simple but general approachTry all combinations until you find one that worksThis approach isn’t clever, but computers are fastThen try and improve on the brute force resutsCS 307 Fundamentals of Computer Science Recursive Backtracking5Solving SudokuBrute force Sudoku Soluton–if not open cells, solved–scan cells from left to right, top to bottom for first open cell–When an open cell is found start cycling through digits 1 to 9. –When a digit is placed check that the set up is legal–now solve the board1Attendance 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 Backtracking6CS 307 Fundamentals of Computer Science Recursive Backtracking7Solving Sudoku – Later Steps1 1 2 1 2 41 2 4 81 2 4 8 9uh oh!CS 307 Fundamentals of Computer Science Recursive Backtracking8Sudoku – A Dead EndWe have reached a dead end in our searchWith the current set up none of the nine digits work in the top right corner1 2 4 8 9CS 307 Fundamentals of Computer Science Recursive Backtracking9Backing UpWhen the search reaches a dead end in backs up to the previous cell it was trying to fill and goes onto to the next digitWe would back up to the cell with a 9 and that turns out to be a dead end as well so we back up again–so the algorithm needs to remember what digit to try nextNow in the cell with the 8. We try and 9 and move forward again.1 2 4 8 91 2 4 9CS 307 Fundamentals of Computer Science Recursive Backtracking10Characteristics of Brute Forceand BacktrackingBrute force algorithms are slowThe don't employ a lot of logic–For 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 wayBut, brute force algorithms are fairly easy to implement as a first pass solution–backtracking is a form of a brute force algorithmCS 307 Fundamentals of Computer Science Recursive Backtracking11Key InsightsAfter trying placing a digit in a cell we want to solve the new sudoku board–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 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 cell we need to report back that things didn't workCS 307 Fundamentals of Computer Science Recursive Backtracking12Recursive 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 different alternativesCS 307 Fundamentals of Computer Science Recursive Backtracking13Recursive BacktrackingPseudo code for recursive backtracking algorithms If at a solution, report successfor( every possible choice from current state / node)Make that choice and take one step along pathUse recursion to solve the problem for the new node / stateIf the recursive call succeeds, report the success to the next high levelBack out of the current choice to restore the state at the beginning of the loop.Report failureCS 307 Fundamentals of Computer Science Recursive Backtracking14Goals of BacktrackingPossible goals–Find a path to success–Find all paths to success–Find the best path to successNot all problems are exactly alike, and finding one success node may not be the end of the searchStartSuccess!Success!CS 307 Fundamentals of Computer Science Recursive Backtracking15The 8 Queens ProblemCS 307 Fundamentals of Computer Science Recursive Backtracking16The 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 Backtracking17The N Queens ProblemPlace N Queens on an N by N chessboard so that none of them can attack each otherNumber of possible placements?In 8 x 864 * 63 * 62 * 61 * 60 *
View Full Document
Unlocking...