Backtracking Algorithm.pptx

Analysis and design of Algorithm
Backtracking algorithm and its comparison with Dynamic programing problems

1. Backtracking Algorithm

2. Objectives Backtracking Programming Technique Applications N-Queens Problem Complexity of N-Queens Problem Backtracking vs Dynamic Programming Algorithms

3. Backtracking Programming Technique A backtracking algorithm tries to build a solution to a computational problem incrementally. Whenever the algorithm needs to decide between multiple alternatives to the next component of the solution, it simply tries all possible options recursively.

4. Applications N-Queens Problem Subset sum Problem Rat in a Maze Problem Sudoku Hamiltonian Cycle Longest Common Subsequence

5. N-Queen Problem Goal: position n queens on a n x n board such that no two queens threaten each other No two queens may be in the same row, column, or diagonal Sequence: n positions where queens are placed Set: n2 positions on the board Criterion: no two queens threaten each other

6. 4-Queen Problem Solution 4-Queen Problem Assign each queen a different row Check which column combinations yield solutions Each queen can be in any one of four columns: 4 x 4 x 4 x 4 = 256 Q Q Q Q

7. Complexity of N-Queens Problem Theta( n^n ) For example- 4-Queens problem the complexity is- Theta(4^4)

8. Algorithm Start in the leftmost column 2) If all queens are placed return true 3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in [row, column] leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows. 4) If all rows have been tried and nothing worked, return false to trigger backtracking .

9. Backtracking vs Dynamic Programming Dynamic Programming – subsets of a solution are generated  Backtracking – Technique for deciding that some subsets need not be generated Efficient for many large instances of a problem (but not all)