Question? Leave a message!




Backtracking algorithms

Backtracking algorithms
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Backtracking algorithms Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Backtracking algorithms 2 Outline In this topic, we will cover: – Traversals of trees and graphs – Backtracking Backtracking algorithms 3 Backtracking Suppose a solution can be made as a result of a series of choices – Each choice forms a partial solution – These choices may form either a tree or DAG • Separate branches may recombine or divergeBacktracking algorithms 4 Backtracking With Dijkstra’s algorithm, we keep track of all current best paths – There are at most V – 1 paths we could extend at any one time – These can be tracked with a relatively small table Suppose we cannot evaluate the relative fitness of solutions – There may just be too many to record efficiently – Are we left with a brute-force search? Suppose there are just too many partial solutions at any one time to keep track of – At any point in time in a game of chess or Go (围棋 or碁), there are a plethora of moves, each valid, but the usefulness of each will varyBacktracking algorithms 5 Sudoku In the first case, consider the game Sudoku: 53 – The search space is 9 5 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7 http://www.sudokuoftheday.com/Backtracking algorithms 6 Sudoku At least for the first entry in the first square, only 1, 3, 7 fit 5 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7 5 1 4 6 5 3 4 6 5 7 4 6 6 3 1 6 3 1 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7Backtracking algorithms 7 Sudoku nd If the first entry has a 1, the 2 entry in that square could be 7 or 8 5 1 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7 5 1 4 6 5 1 4 6 7 6 3 1 8 6 3 1 9 2 5 4 9 2 5 4 6 8 1 6 8 1 8 4 8 4 2 6 1 2 6 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 8 2 7 8 2 7Backtracking algorithms 8 Sudoku nd If the first entry has a 3, the 2 entry in that square could be 7 or 8 5 3 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7 5 3 4 6 5 3 4 6 7 6 3 1 8 6 3 1 9 2 5 4 9 2 5 4 6 8 1 6 8 1 8 4 8 4 2 6 1 2 6 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 8 2 7 8 2 7Backtracking algorithms 9 Sudoku nd If the first entry has a 7, the 2 entry in that square could be 8 5 7 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7 5 7 4 6 8 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 1 2 3 8 2 7Backtracking algorithms 10 Sudoku 5 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 In the next child, there are no 1 2 3 8 2 7 options available for the 5 1 4 6 5 3 4 6 5 7 4 6 next entry 6 3 1 6 3 1 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 5 1 4 6 5 1 4 6 5 3 4 6 5 3 4 6 5 7 4 6 5 7 4 6 7 6 3 1 8 6 3 1 7 6 3 1 8 6 3 1 1 6 3 1 8 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 8 2 7 8 2 7 8 2 7 5 1 4 6 7 6× 3 1 Any candidate solution built from this 9 2 5 4 partial is infeasible 6 8 1 8 4 – We can ignore this branch 2 6 1 9 5 8 1 1 2 3 8 2 7Backtracking algorithms 11 Sudoku 5 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 Three other branches lead to 1 2 3 8 2 7 similar dead ends 5 1 4 6 5 3 4 6 5 7 4 6 6 3 1 6 3 1 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 5 1 4 6 5 1 4 6 5 3 4 6 5 3 4 6 5 7 4 6 7 6 3 1 8 6 3 1 7 6 3 1 8 6 3 1 8 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 8 2 7 8 2 7 5 1 4 6 5 3 4 6 5 7 4 6 7 6× 3 1 7 6× 3 1 8 6× 3 1 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7Backtracking algorithms 12 Sudoku 5 4 6 6 3 1 9 2 5 4 6 8 1 8 4 2 6 1 9 5 8 1 With the other two, there is only 1 2 3 8 2 7 one candidate for each of the 5 1 4 6 5 3 4 6 5 7 4 6 last two 6 3 1 6 3 1 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 entries 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 5 1 4 6 5 1 4 6 5 3 4 6 5 3 4 6 5 7 4 6 7 6 3 1 8 6 3 1 7 6 3 1 8 6 3 1 8 6 3 1 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 9 2 5 4 6 8 1 6 8 1 6 8 1 6 8 1 6 8 1 8 4 8 4 8 4 8 4 8 4 2 6 1 2 6 1 2 6 1 2 6 1 2 6 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 8 2 7 8 2 7 8 2 7 8 2 7 8 2 7 5 1 4 6 5 3 4 6 8 6 7 3 1 8 6 7 3 1 3 9 2 5 4 1 9 2 5 4 6 8 1 6 8 1 8 4 8 4 2 6 1 2 6 1 9 5 8 1 9 5 8 1 1 2 3 1 2 3 8 2 7 8 2 7Backtracking algorithms 13 Sudoku It may seem that this is a reasonably straight-forward method; however, the decision tree continues to branch quick once we start filling the second squareBacktracking algorithms 14 Sudoku 54 A binary tree of this height would have around 2– 1 nodes – Fortunately, as we get deeper into the tree, more get cutBacktracking algorithms 15 Implementation Our straight-forward implementation takes a 9 × 9 matrix – Default entries are values from 1 to 9, empty cells are 0 – Two helper functions: bool next_location( int99, int &i, int &j ) • Finds the next location empty location returning false if none is found bool is_valid( int99, int i, int j, int value ) • Checks if there are any conflicts created if matrixij is assigned value – The backtracing function: • Finds the next unoccupied cell • For each value from 1 to 9, it checks if it is valid to insert that it there – If so, backtracking is called recursively on the matrix with that entry set The main function creates the initial matrix and calls backtrackBacktracking algorithms 16 Implementation // Find the next empty location in 'matrix' // If one is found, assign 'i' and 'j' the indexes of that entry // Otherwise, return false // - In this case, the values of 'i' and 'j' are undefined bool next_location( int matrix99, int &i, int &j ) for ( int i1 = 0; i1 3; ++i1 ) // If 'value' already appears in for ( int j1 = 0; j1 3; ++j1 ) // - the row 'm' for ( int i2 = 0; i2 3; ++i2 ) // - the column 'n' for ( int j2 = 0; j2 3; ++j2 ) // - the 3x3 square of entries it (m, n) appears in i = 3i1 + i2; // return true, otherwise return false j = 3j1 + j2; bool is_valid( int matrix99, int m, int n, int value ) // Check if 'value' already appears in either a row or column // return 'true' if we find an for ( int i = 0; i 9; ++i ) // unoccupied entry if ( (matrixmi == value) ( matrixin == value ) ) if ( matrixij == 0 ) return false; return true; // Check if 'value' already appears in either a row or column int ioff = 3(m/3); int joff = 3(n/3); return false; // all the entries are occupied for ( int i = 0; i 3; ++i ) for ( int j = 0; j 3; ++j ) if ( matrixioff + ijoff + j == value ) return false; // 'value' already in the 3x3 square return true; // 'value' could be added Backtracking algorithms 17 Implementation bool backtrack( int matrix99 ) int i, j; // If the matrix is full, we are done if ( next_location( matrix, i, j ) ) return true; for ( int value = 1; value = 9; ++value ) if ( is_valid( matrix, i, j, value ) ) // Assume this entry is part of the // solutionrecursively call backtrack matrixij = value; // If we found a solution, return // otherwise, reset the entry to 0 if ( backtrack( matrix ) ) return true; else matrixij = 0; // No solution foundreset the entry to 0 return false; Backtracking algorithms 18 Implementation int main() int matrix99 = 5, 0, 4, 0, 0, 0, 0, 6, 0, 0, 6, 0, 3, 0, 0, 1, 0, 0, 0, 9, 2, 5, 4, 0, 0, 0, 0, 6, 0, 8, 0, 0, 1, 0, 0, 0, 0, 0, 0, 8, 0, 4, 0, 0, 0, 0, 0, 0, 2, 0, 0, 6, 0, 1, 0, 0, 0, 0, 9, 5, 8, 1, 0, 0, 0, 1, 0, 0, 2, 0, 3, 0, 0, 8, 0, 0, 0, 0, 2, 0, 7 ; // If found, print out the resulting matrix if ( backtrack( matrix ) ) for ( int i = 0; i 9; ++i ) for ( int j = 0; j 9; ++j ) std::cout matrixij " "; std::cout std::endl; return 0; Backtracking algorithms 19 Implementation In this case, the traversal: – Recursively calls backtrack 874 times • The last one determines that there are no unoccupied entries – Checks if a placement is valid 7658 times 5 3 4 1 7 8 9 6 2 8 6 7 3 2 9 1 4 5 1 9 2 5 4 6 3 7 8 6 7 8 9 3 1 5 2 4 2 1 5 8 6 4 7 9 3 3 4 9 2 5 7 6 8 1 4 2 3 7 9 5 8 1 6 7 5 1 6 8 2 4 3 9 9 8 6 4 1 3 2 5 7Backtracking algorithms 20 Backtracking This should give us an idea, however: – Perform a traversal – Do not continue traversing if a current node indicates all descendants are infeasible solutions