A maze is in the form of a 2D matrix in which some cells/blocks are blocked. One of the cells is termed as a source cell, from where we have to start. And another one of them is termed as a destination cell, where we
have to reach. We have to find a path from the source to the destination without moving into any of the blocked cells. A picture of an unsolved maze is shown below, where grey cells denote the dead ends and white cells denote the cells which can be accessed.
To solve these types of puzzle, we first start with the source cell and move in a direction where the path is not blocked. If the path taken makes us reach the destination, then the puzzle is solved. Otherwise, we come back and change our direction of the path taken.
The solution of this maze would look like:
If this is your very first foray into Backtracking, fear not — it’s mine, too! Let’s tackle it together — and try not to lose our sanity in the process. So many things in this world would have never come into existence if there hadn’t been an issue problem that needed solving. This truth applies to almost everything, but boy, is it obvious in the world of computer science?
So, it’s a big “YES”, but I do think that it’s unique in one way: computer science’s innovations rely and build upon its own abstractions. But what leads to the need for Backtracking algorithms?
What is Backtracking?
Backtracking is a famous algorithmic-technique for solving/resolving problems recursively by trying to build a solution incrementally. Solving one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree) is the process of backtracking.
According to the wiki definition, Backtracking can be termed as a general algorithmic technique that
considers searching every possible combination in order to solve a computational problem.
There are three types of problems in backtracking:
- Decision Problem: In this, we search for a feasible solution
- Optimisation Problem: In this, we search for the best solution
- Enumeration Problem: In this, we find all feasible solutions
Backtracking is a standard problem-solving technique mainly based on recursion. A backtracking algorithm makes an effort to build a solution to a computational problem incrementally. Whenever the algorithm needs to choose between multiple alternatives to the next component of the solution, it simply tries all possible options recursively step-by-step.
Depth First Search (DFS) uses the concept of backtracking at its very core. So, in DFS, we basically try exploring all the paths from the given node recursively until we reach the goal. After we search in a particular branch of a tree in DFS, we can land up in two possible states.
- We land on the goal state in which case we simply exit.
- Or, we did not find the goal state and we hit a dead end. In this scenario, we backtrack to the last checkpoint and we then try out a different branch.
Difference between Recursion and Backtracking
In recursion, function calls itself until it reaches a base case. In backtracking, we use recursion in order to explore all the possibilities until we get the best result for the problem.
Popular backtracking problems
- The knight’s tour problem
- Rat in a Maze
- N-Queens problem
- m colouring problem
- Hamiltonian cycle
- Solving cryptarithmetic puzzles
- Magnet Puzzle
What is backtracking in stack?
Recursion uses a call stack to keep the value of each recursive call and then pop as the function ends. We can eliminate recursion by using our own stack to do the same thing.
Does turning left in a maze work?
Always turn left/right when you are in a maze and you will find your way to the destination. If you always turn to the same direction, you will eventually find the exit or whatever the maze is about finding.
It is easy to implement this kind of processing by constructing a tree of choices being made, called the state-space tree. Its root represents an initial state before the search for a problem begins. The nodes of the first
level in the tree represent the options made for the first component of a solution, the nodes of the second level show the choices for the second component, and so on.
A node in a state-space tree is termed as promising if it corresponds to a partially constructed solution that may still lead to a complete solution of the problem; otherwise, it is termed as non-promising. Leaves illustrate either non-promising dead ends/blocked blocks or complete solutions found by the algorithm.
In most of the cases, a state-space tree for a backtracking algorithm is constructed in the manner of depth-first search. If the current node is termed as promising, its child is generated by adding the first remaining legitimate choice for the next component of a solution, and the processing moves to this child.
If the current node turns out to be non-promising, the algorithm recursively backtracks to the node’s parent to
consider the next possible option for its last component; if there is no such available choice, it backtracks one more level up the tree, and so on. In the end, if the algorithm reaches a complete solution to the problem, it either stops (if just one solution is required) or continues searching for other possible solutions.
Backtracking is one of the famous algorithms because of its simplicity and elegance; it doesn’t always have great performance, but the branch cutting part is really amazing and gives you the notion of progress in performance while you code.
Algorithm to solve a rat in a maze:
- Create a solution matrix, initially filled with 0’s.
- Create a recursive function, which takes an initial matrix (Maze), output matrix (Solution) and position of rat (i, j).
- If the position is out of the matrix or the position is not valid then return.
- Mark the position output[i][j] as 1 and check if the current position is the destination or not. If the destination is reached print the output matrix and return.
- Recursively call for position (i+1, j) and (i, j+1).
- Unmark position (i, j), i.e output[i][j] = 0.
Step 1: Include the header file, define the original maze and initialise the solution matrix.
Step 2: Assign ‘0’ to all values of the solution matrix and call the ‘solveMaze’ function.
Step 3: Define ‘solveMaze’ function, which is the main implementation of the backtracking algorithm.
Step 4: Define ‘printMaze’ and ‘printSolution’ function.
Original Maze: 0 means the block is a dead end and 1 means the block can be used in the path from source to destination.
Solution Path: Following ‘1’ from the source node to the destination node defines the final solution.
Explanation of the Code:
- printMaze(): This function is just printing the original maze matrix.
- printSolution(): This function is just printing the solution matrix derived after applying the backtracking algorithm.
- solveMaze(): This is the main function where we are implementing our backtracking algorithm. First, we are checking if our cell/block is the destination cell or not if (r==SIZE-1) and (c==SIZE-1). If it is the destination cell then our maze is already solved. If not, then we search whether it is a valid cell to move or not. A valid cell must be in the 2D-matrix i.e., indices must between 0 to SIZE-1 i.e r>=0 && c>=0 && r
- Time Complexity: O(2^(n^2)): The recursion can run upper bound 2^(n^2) times.
- 2) Space Complexity: O(n^2): Output matrix is required so an extra space of size n*n is needed.
- Puzzles such as eight queens puzzle, crosswords, verbal arithmetic, Sudoku and Peg Solitaire.
- Combinatorial optimisation problems such as parsing and the knapsack
Pros and Cons of using Backtracking algorithm:
- It’s very intuitive to code. It’s almost like a small kid trying to solve the problem.
- It is a step-by-step representation of a solution to a given problem, which is very easy to understand
- It is easy to first develop an algorithm, and then convert it into a flowchart and then into a computer program.
- It is very easy to implement and contains fewer lines of code. Almost all of the backtracking codes are generally few lines of recursive function code.
- It has got a definite procedure.
- More optimal algorithms for the given problem may exist.
- Very time inefficient in lot of cases when branching factor is large.
- Large space complexity because we are using recursion so function information is stored on stack.
- Backtracking is like a sort of permutation in steroids, once a pattern doesn’t match we find another one until there is no more available source, or a certain pattern matched.
- Backtracking can almost solve any problem, e.g. Chess(famous 8 queens problem) or Sudoku (complete solution set), due to its brute-force nature (analogy to permutation).
- Backtracking requires recursion which can be something worse, because CPU stack space is limited and can be consumed quickly by recursion.
- Backtracking takes polynomial time, oh no!
- Backtracking is non-deterministic unless you tracked it.
- Backtracking is hard to do/simulate by human simulate.
- 7) Backtracking can rarely be tail-call optimised.
In a nutshell, we can say three things on behalf of backtracking :
- It is typically applied to difficult combinatoric problems for which no efficient algorithm for finding, exact solutions possibly exists.
- Backtracking solves each instance of a problem in an acceptable amount of time.
- It generates all elements of the problem state.
By Deepak Jain