Backtracking Algorithm Made Simple

What is backtracking?

Backtracking, commonly described as a “depth-first search”  algorithm, involves exploring all possible solutions by going as deep as possible along each branch before “backtracking” and trying a different path. This process is repeated until a solution is found or all the possibilities are exhausted.

Lets take an example

Suppose you are standing in front of three tunnels, one of which is having a bag of gold at its end, but you don't know which one. So you'll try all three. First go in tunnel 1, if that is not the one, then come out of it, and go into tunnel 2, and again if that is not the one, come out of it and go into tunnel 3. So basically in backtracking we attempt solving a sub problem, and if we don't reach the desired solution, then undo whatever we did for solving that sub problem, and try solving another sub problem.

Backtracking algorithm

backtrack (A)

    If A is not a solution

          Return false

    If A is a new solution

           Add to list of solutions

    backtrack(expand A)

State-Space Tree

State-space tree is a data structure used in Artificial intelligence and computer science for representing the state space of a problem in a tree-like fashion. The nodes of the tree represent the states of the problem and the edges represent the actions that lead from one state to another. The tree helps to efficiently keep track of explored states and avoid exploring the same state multiple times. The diagram below represents a state-space tree of backtracking.

state-space tree

How does backtracking work?

Lets try and solve a problem:

You want to find all the possible ways to arrange the first three alphabets a,b and c such that c cannot be next to a.

The first step will be to create a state-space tree and look for all possible solutions. We will only keep the solutions that meet the constraints

The following will be the possible solution to the problem:

(a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a)

The only solutions that were able to meet the constraints were only (a, b, c) and (c, b, a)

Application areas in backtracking

 Backtracking algorithm has a wide range of applications which include:

• maze solving problems

• N-Queen problem

• the Knight tour problem

•  search for all Hamilton paths in a graph.