Backtracking

Types of Backtracking Problems:

Problems associated with backtracking can be categorized into 3 categories. They are:

• Decision Problems – Here, we search for a feasible solution.
• Optimization Problems – For this type, we search for the best solution.
• Enumeration Problems – We find set of all possible feasible solutions to the problems of this type.
  
  

Backtracking Problem Identification

• Every problem that has clear and well established constraints on any objective solution which incrementally aids candidate to the solution and abandons a candidate (“backtracks”) whenever it determines that the candidate is not able to reach a feasible solution. Such problems can be solved by Backtracking. The backtracking algorithms are generally exponential in nature with regards to both time and space.
• However, most of the commonly discussed problems, can be solved using other popular algorithms like Dynamic Programming or Greedy Algorithms in O(n), O(logn) or O(n* logn) time complexities in order of input size. Hence, in such cases, usage of backtracking becomes an overkill.
• But, there still remain some problems that only have backtracking algorithms as the means of solving them till date.
• Consider a real life scenario. We have three boxes and we are told that only one of them has a gold coin in it and we do not know exactly which box has it. So, in order to identify which box has the coin, we will have no other option than opening all the boxes one by one.
• 
• The first box is checked first. If it does not contain the coin, we close it and check the second box and so on until we find the coin. This is nothing but utilisation of backtracking algorithm in real life. It is the process of solving all sub-problems one by one to reach the best possible solution for any given problem.
• Let us take a technical example and understand backtracking more clearly. Given an instance of any problem P and data D corresponding to the instance, all the constraints that are to be satisfied for solving the problem as C. The backtracking algorithm will then be:
• The algorithm begins to build up a solution, starting with an empty solution set S. S = {}
• All possible moves are added to S one by one. Firstly, we add to S the first move that is left. This now creates a new sub-tree s in the state space tree.
• Check if S+s is valid by seeing if it satisfies each of the constraints defined in C.
• If S+s is valid, then the sub-tree s is “eligible” to add more “children”.
• Else, the entire sub-tree s is useless, so go back to step 1 using argument S.
• In case of “eligibility” of the newly formed sub-tree s, go back to step 1 using argument S+s.
• If S+s returns that it is a solution for the entire data D. Return the result and terminate the algorithm.
• If not, then return that there doesn’t exist any possible solution for the current s and hence discard it.

Application

Backtracking has found numerous applications for solving real life commonly encountered problems by satisfying certain constraints. Problems like crosswords, verbal arithmetic, Sudoku, and many other puzzles can be solved by using backtracking approach.

• N-Queens Problem: Backtracking is also used in solving N queens problem in N*N chessboard. The problem basically deals with placing N queens on NN board without threatening each other. That is no two queens share the same row, column, or diagonal on the chessboard.

• By using backtracking, the idea for solving this problem is to place queens 1 by 1 in different columns, starting from the leftmost column. While placing the queen, we check whether it is safe to place the queen at that cell by checking with already placed queens. If we find a row for which there are no queens placed in the current column under consideration, we mark this cell (ith row and jth column) as part of the solution. If we are not able to find any such rows, then we backtrack and return false.
• Maze Problems:: Backtracking is used to solve maze related problems. The most common problem is rat in a maze problem. The problem statement says that a maze in the form of N*N binary matrix of blocks is given where source block (starting point) is the top left most block i.e., maze[0][0] and destination block (ending point) is bottom rightmost block i.e., maze[N-1][N-1]. A rat begins to move from start point and has to reach the destination but it can move only in 2 directions - forward and down. Additionally, the maze matrix has certain dead ends defined. The value 0 means the cell is a dead-end and 1 means the cell can be used as path to move from source to destination.

• Graph coloring problem: Read More
• Backtracking is also used in graphs to find Hamiltonian cycles. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path (path which visits each vertex exactly once) in such a way that there exists an edge (in the graph) from the last vertex to the first vertex of the Hamiltonian Path. This has a lot of application in the field of computer graphics.
• Apart from these, backtracking is also used in the area of solving cryptarithmetic puzzles, magnet puzzles, finding subset sum problems and many more!

FAQ

• What are backtracking algorithms?
  • Backtracking is an algorithmic technique for finding all solutions to some computational problems that have certain constraints and incrementally builds candidates to the solutions while abandoning a candidate if it does not lead to valid solutions.
• How Backtracking algorithms work?
  • Backtracking uses recursive approach to find feasible solution by building a solution incrementally with time and removing the solutions that dont lead to feasible solution for the problem based on the constraints given.
• When is backtracking used?
  • Backtracking is normally used when we are faced with a multiple number of options and we have to choose one among them based on the constraints given. After the choice we will be having a new set of options which is where the recursion comes to the rescue. The procedure is repeated untill we get a feasible solution.
• Is backtracking better than brute force algorithms?
  • Brute force algorithms are those which computes every possible solution to a problem and then selects the best one among them that fulfills the given requirements.
  • Whereas, backtracking is a refined brute force technique where the implicit constraints are evaluated after every choice (not as in brute force where evaluation is done after all solutions have been generated). This means that potential non-satisfying solutions can be rejected before the computations have been ‘completed’.
• What is the time complexity of backtracking algorithm?
  • The time complexity of the algorithm will be a measure specific to what problem we are trying to solve.
• What is the difference between recursion and backtracking?
  • In recursion, a function simply calls itself until reaches a base case.
  • Whereas, in backtracking we use recursion for exploring all the possibilities until we get the best and feasible result for any given problem.