Introduction to Backtracking Algorithm - Learnengineeringforu

So, while solving a problem using recursion, we break the given problem into smaller ones. Let's say we have a problem $A$ and we divided it into three smaller problems $B$, $C$ and $D$. Now it may be the case that the solution to $A$ does not depend on all the three subproblems, in fact we don't even know on which one it depends.Let's take a situation. 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 subproblem, and if we don't reach the desired solution, then undo whatever we did for solving that subproblem, and try solving another subproblem.Let's take a standard problem.N-Queens Problem: Given a chess board having $N\times N$ cells, we need to place $N$ queens in such a way that no queen is attacked by any other queen. A queen can attack horizontally, vertically and diagonally.So initially we are having $N\times N$ unattacked cells where we need to place $N$ queens. Let's place the first queen at a cell $(i,j)$, so now the number of unattacked cells is reduced, and number of queens to be placed is $N-1$. Place the next queen at some unattacked cell. This again reduces the number of unattacked cells and number of queens to be placed becomes $N-2$. Continue doing this, as long as following conditions hold.

1. The number of unattacked cells is not 
2. The number of queens to be placed is not 

If the number of queens to be placed becomes , then it's over, we found a solution. But if the number of unattacked cells become $0$, then we need to backtrack, i.e. remove the last placed queen from its current cell, and place it at some other cell. We do this recursively.Complete algorithm is given below:

is_attacked( x, y, board[][], N)
    //checking for row and column
    if any cell in xth row is 1
        return true
    if any cell in yth column is 1
        return true

    //checking for diagonals
    if any cell (p, q) having p+q = x+y is 1          
        return true
    if any cell (p, q) having p-q = x-y is 1
        return true
    return false


N-Queens( board[][], N )
    if N is 0                     //All queens have been placed
        return true
    for i = 1 to N {
        for j = 1 to N {
            if is_attacked(i, j, board, N) is true
                skip it and move to next cell
            board[i][j] = 1            //Place current queen at cell (i,j)
            if N-Queens( board, N-1) is true    // Solve subproblem
                return true                   // if solution is found return true
            board[i][j] = 0            /* if solution is not found undo whatever changes 
                                       were made i.e., remove  current queen from (i,j)*/
        }
    }
    return false

Here's how it works for $N=4$.

So, at the end it reaches the following solution:

So, clearly, the above algorithm, tries solving a subproblem, if that does not result in the solution, it undo whatever changes were made and solve the next subproblem. If the solution does not exists $(N=2)$, then it returns $false$.