Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.

Question

Suresh Chand · Accepted Answer

Backtracing is an algorithmic method to solve a problem in an additional way. Backtracking is an algorithmic technique to solve a problem in an incremental way. It uses a recursive approach to solve the problems. We can say that backtracking is used to find all possible combinations to solve an optimization problem. Backtracking is a general algorithm for finding solutions to some computational problem. We have a set of several choices. If one choice from the set of choices proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. In backtracking, you use recursion in order to explore all the possibilities until you get the best result for the problem. The difference between backtracking and recursion are Sl.N Recursion Backtracking 1 Recursion does not always need backtracking Backtracking always uses recursion to solve problems 2 A recursive function solves a particular problem by calling a copy of itself and solving smaller subproblems of the original problems. Backtracking at every step eliminates those choices that cannot give us the solution and proceeds to those choices that have the potential of taking us to the solution. 3 Recursion is a part of backtracking itself and it is simpler to write. Backtracking is comparatively complex to implement. 4 Applications of recursion are Tree and Graph Traversal, Towers of Hanoi, Divide and Conquer Algorithms, Merge Sort, Quick Sort, and Binary Search. Application of Backtracking is N Queen problem, Rat in a Maze problem, Knight’s Tour Problem, Sudoku solver, and Graph coloring problems. N-queen Problem: This problem is to find an arrangement of N queens on a chess board, such that no queen can attack any other queens on the board. The chess queens can attack in any direction in a horizontal, vertical, or diagonal way. A binary matrix is used to display the positions of N Queens, where no queens can attack other queens. Algorithm: Step 1: Start in the leftmost column Step 2: If all queens are placed return true Step 3: Try all rows in the current column. Do following for every tried row. Step 3.1 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. Step 3.2 If placing the queen in [row, column] leads to a solution then return true. Step 3.3 If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step 3.1 to try other rows. Step 4: If all rows have been tried and nothing worked, return false to trigger backtracking. Step 5: End Analysis: Solution of N Queen problem backtracking checks for all possible arrangements of N queens on the chessboard. And check for the validity of the solution. Now a number of possible arrangements of N queens on N x N chessboard in N!. So average and worst case complexity of the solution is O(N!). The best case occurs if we find our solution before exploiting all possible solutions, the best, average and worst case complexity remains O(N!) Example: Given a 4 x 4 chessboard, arrange four queens in a way, such that no two queens attack each other. That is, no two queens are placed in the same row, column, or diagonal. The solution of the 4-queen problem can be seen as four tuples (x1, x2, x3, x4), where xi represents the column number of queen Qi. Two possible solutions for the 4-queen problem are (2, 4, 1, 3) and (3, 1, 4, 2).

Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.

Leave your Answer:

Hits Counter

Question

Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.

Leave your Answer: