Backtracking Algorithm

Posted By on October 21, 2014

Download PDF
Algorithm to solve Tower of Hanoi Problem
Principle of Optimality

Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve an optimization problem. Backtracking is also known as depth-first search or branch and bound. While backtracking is useful for hard problems to which we do not know more efficient solutions, it is a poor solution for the everyday problems that other techniques are much better at solving.

However, dynamic programming and greedy algorithms can be thought of as optimizations to backtracking, so the general technique behind backtracking is useful for understanding these more advanced concepts. Learning and understanding backtracking techniques first provides a good stepping stone to these more advanced techniques because you won’t have to learn several new concepts all at once.

steps to follow ::

for example,


  1. Starting at Root, your options are A and B. You choose A.
  2. At A, your options are C and D. You choose C.
  3. C is bad. Go back to A.
  4. At A, you have already tried C, and it failed. Try D.
  5. D is bad. Go back to A.
  6. At A, you have no options left to try. Go back to Root.
  7. At Root, you have already tried A. Try B.
  8. At B, your options are E and F. Try E.
  9. E is good. Congratulations!


The backtracking algorithm.

Here is the algorithm (in pseudocode) for doing backtracking from a given node n:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        return false
Algorithm to solve Tower of Hanoi Problem
Principle of Optimality

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby