Recent Posts

Backtracking in C

Written by

Pooja Rao

Backtracking in C

What does the name itself suggest ?

Backtracking means taking a step back, tracing the route back upto a particular checkpoint from where you can again go ahead and take another route to your desired destination.

Now, how is this approach applicable in programming, where is it used, how is it applied will be learnt in the next few sections.

Background and Understanding basics

  1. Introduction:
    • Backtracking is the refinement method of Brute-Force method. Backtrack method means it finds the number of sub solutions and each may have number of sub divisions, and solution chosen for exactly one.
    • Backtracking is recursive in nature.
    • Definition according to Wikipedia:

“Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.”

  1. Example:

    • To understand the above definition consider that you have to go from starting location ‘A’ to destination ‘B’. In between then path you come across a cross road having 3 paths in front of you. They all are leading you forward, however there is no assurance all will lead to destination ‘B’.
    • At this point in time, the option you have is to try all the paths and check if you reached the spot ‘B’. If the first road does not lead you to ‘B’ , you come back (backtrack your route) at the crossroad again and try new paths until one of them takes you to your destination.
    • So basically 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.

  2. Exact functioning of backtracking:

Backtracking is similar to permutations and combinations, where we try different paths / solutions for the same problem.

  • We start with a possible solution of the problem, and move ahead with this approach towards one of the solutions that will satisfy all constraints.
  • We could find one or all possible solutions for the problem we are solving.
  • At each step we look for a candidate, and if the path taken is not leading us to the solution, we backtrack one level back, and start with new candidate.
  • If that level again does not contain the correct solution we backtrack one level further up in hierarchy and so on.
  • If we end up at the root, we say that the solution is not available in combination with the said constraints.
  • Else, if we find a potential candidate which will lead us to solution, it will become part of partial solution and that would be used as a part of the final solution.
  • If we need to find one solution we could stop, and if we wish to find all we could store them and display all of them after all possible solution options are checked.
  1. Applications:

Backtracking can be applied only for problems which work with concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution.

  • Backtracking used for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.
  • It is often a convenient technique for parsing, other combinatoric optimisation problems like travelling salesman problem etc.
  • It is also the basis of the so-called logic programming languages such as Icon, Planner etc.
  • It is used to search sub-directories within directories.
  • Used in car navigation system as well.

EXAMPLE: TO SOLVE THE N-QUEEN PROBLEM

Problem Statement:

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem.

Q – denotes queen.

For n = 4; i.e. no. of queens is 4:

Output 1:

{ 0,  Q,  0,  0}.

{ 0,  0,  0,  Q}

{ Q,  0,  0,  0}

{ 0,  0,  Q,  0}

Output 2:

{ 0,  0,  Q,  0}

{ Q,  0,  0,  0}

{ 0,  0,  0,  Q}

{ 0,  Q,  0,  0}

Points to note and constraints:

  • A queen attacks horizontally, vertically an diagonally with number of steps allowed.
  • No two queens should be placed horizontally, vertically or diagonally. In other words, any queen should not be in the same row, column or diagonal of any other queen.
  • We start with N = 4, as for N = 1 to 3 solution is not possible given the constraints.

ALGORITHM:

  1. Start in the leftmost column
  2. If all queens are placed, return true
  3. Try all rows in the current column
  4. If the queen can be placed safely in the current row, mark it as part of the solution and recursively check if this placement leads to a valid solution
  5. If the placement leads to a solution, return true
  6. If the placement does not lead to a solution, unmark it and try other rows
  7. If all rows have been tried and no solution has been found, return false to trigger backtracking

Explanation:

  • Backtracking is a recursive method used to find solutions to problems that involve partial solutions.
  • In this case, we are using backtracking to find solutions to the N Queen problem, which involves placing N queens on an N x N chessboard without any of the queens attacking each other.
  • We have implemented three functions to help us solve this problem:
    1. The nqueen_function is responsible for placing all queens on the chessboard in a way that satisfies the mentioned conditions.
    2. The nqueen_function calls the placeholder function, which checks if it is possible to place a queen in a particular column without any threats from previously placed queens, both column-wise and diagonally.
    3. If a queen can be placed in the column, the placeholder function returns true (1). If it is not possible to place a queen, the function returns false (0). If a false value is returned, the nqueen_function backtracks to the previous step and tries other options for placing the previous queen. This process continues until a feasible solution is reached.
  • The chess_board array is used to record the column in which the queen is placed for each row.
  • Once all queens have been placed on the chessboard, the display function is called from within the nqueen_function to print the final or possible solutions.
  • It's important to note that backtracking is a time-consuming algorithm and is not particularly efficient. We will now trace the initial steps of solving this problem, starting with an empty chessboard.

Step 1: In the first iteration we will try and place queen in first row. Hence, function call is row = 1 and n = 4 (number of queens / size of board).

  1   2   3   4
1 [Q] *   *   *
2 *   *   *   *
3 *   *   *   *
4 *   *   *   *

First, placeholder function is called to check if queen can be placed in first column, hence col = 1. Since, no queen is placed on board before, so no threat and the placeholder function returns value 1 = true.

Thus, the array chess_board which houses the columns for respective rows where queen is placed will look as follows: chess_board[1] = 1 ; where value 1 is for column 1 of row 1.

Step 2: Since all queens are not yet placed, we move to the next iteration to place queen in second row. Hence, function call is row = 2 and n = 4 (number of queens / size of board).

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   *   *
4 *   *   *   *

Placeholder function is called to check if queen can be placed in first column, however since queen in first row is placed in column 1, therefore queen 2, cannot be placed there, hence 0 = false is returned to the calling function.

We now check if queen 2 can be placed in next column i.e col = 2. Since there is threat of diagonal attack from queen 1, hence value returned is 0  = false, thus queen 2 still not being placed.

Column 3 is next checked as a possible location for queen 2 to be placed, since no threat is observed queen 2 is placed in column 3.

Thus, the array chess_board after queen 2 is placed will look as follows: chess_board[2] = 3 ; where value 3 is for column 3 of row 2.

Step 3: Since all queens are not yet placed, we move to the next iteration to place queen in third row. Hence, function call is row = 3 and n = 4.**

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   [Q] *
4 *   *   *   *

When we try and place queen 3, we have threat in all the columns either in a straight line or diagonally from previously placed queens. A value 0 = false is returned by n queen(row =3, n =4) to the calling function of n queen(row = 2, n = 4).

Step 4: Since, Backtracking happens, we again try and re-place previously placed queen, queen 2.

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   *   *
4 *   *   *   *

Since first two columns were previously rejected, the remaining two options are tried out of which column 4 faces no threat.

Thus chess_board[2] = 4 , 4 stands for column 4 of row 2.

Step 5: We again now come back to row 3 and try and place queen 3.

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   [Q] *
4 *   *   *   *

After the usual checks, column 2 satisfies all conditions for row 3’s queen. Thus queen 3 is placed in column 2.

chess_board[3] = 2. 2 stands for column 2 of row 3.

Step 6: Since all queens are not yet placed, we move to the next iteration to place queen in fourth row. Hence, function call is row = 4 and n = 4.

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   [Q] *
4 *   *   *   [Q]

For queen 4, in row 4 again none of the columns are feasible for its placement. Backtracking happens and false is returned to the calling function n queen of the previous level.

Step 7: Backtrack and re-place the queen at level 3 / row 3.

  1   2   3   4
1 [Q] *   *   *
2 *   [Q] *   *
3 *   *   *   *
4 *   *   *   *

When we backtrack to row 3 for solution, we just have the fourth column to try; however even column 4 is not feasible; hence we again backtrack to a level upward to find the possible solution.

Step 8: Backtrack and re-place the queen at row 2.

  1   2   3   4
1 [Q] *   *   *
2 *   *   *   *
3 *   *   *   *
4 *   *   *   *

Now, when trying to place queen 2, we have exhausted all options and hence we now backtrack to the root i.e. level 1 – row 1.

Step 9: Backtrack and re-place the queen at row 1.

  1   2   3   4
1 [Q] *   *   *
2 *   *   *   *
3 *   *   *   *
4 *   *   *   *

Queen 1 is placed in column 2 as that was the next option available with us having no conflict. So on and so forth we keep trying and backtrack until we reach the final solution.

chess_board array would look like this post the solution 1 to 4 queen problem is found.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int chess_board[20], count;

void nqueen_function(int row, int num)
{
    int col;
    for (col = 1; col <= num; col++)
    {
        if (placeholder(row, col)) //function call to check where to place the queen
        {
            chess_board[row] = col;
            if (row == num) //ensures if all queens are placed or not
            {
                display(num); //once all queens placed; display solution.
            }
            else
            {
                nqueen_function(row + 1, num); //function call to place remaining queens.
            }
        }
    }
}

int placeholder(int row, int col)
{
    int count;
    for (count = 1; count <= row - 1; count++)
    {
        if (chess_board[count] == col) //checks if there is any threat from queen placed previously.
        {
            return 0;
        }
        else
        {
            if (abs(chess_board[count] - col) == abs(count - row)) //check for diagonal conflicts.
            {
                return 0;
            }
        }
    }
    return 1; //no threats, queen can be placed.
}

int display(int num)
{
    int m, n;
    printf("\n\n\tPossible Solution %d:\n\n", ++count);
    for (m = 1; m <= num; m++)
    {
        printf("\t[%d]", m);
    }
    for (m = 1; m <= num; m++)
    {
        printf("\n\n[%d]", m);
        for (n = 1; n <= num; n++)
        {
            if (chess_board[m] == n)
            {
                printf("\tQ"); //queen at (i,j) position.
            }
            else
            {
                printf("\t*"); //empty slot.
            }
        }
    }
}

int main()
{
    int num;
    printf("\nEnter Number of Queens:\t");
    scanf("%d", &num);
    if (num <= 3)
    {
        printf("\nNumber should be greater than 3 to form a Matrix\n");
    }
    else
    {
        nqueen_function(1, num); //call to nqueen function
    }
    printf("\n\n");
    return 0;
}

Output:

Enter Number of Queens: 4
  
Possible Solution 1:

	[1]	[2]	[3]	[4]

[1]	*	Q	*	*
[2]	*	*	*	Q
[3]	Q	*	*	*
[4]	*	*	Q	*


Possible Solution 2:

	[1]	[2]	[3]	[4]

[1]	*	*	Q	*
[2]	Q	*	*	*
[3]	*	*	*	Q
[4]	*	Q	*	*

Backtracking as observed is a less efficient, memory consuming and time consuming approach.

Learn C Programming

Backtracking in C