Backtracking in C

Written By -

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.

 

  1. 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.  Do following for every tried row:

  1. a) If the queen can be placed safely in this row then mark this [row, column] as part of the

solution and recursively check if placing  queen here leads to a solution.

  1. b) If placing queen in [row, column] leads to a solution then return true.
  2. c) If placing queen doesn’t lead to a solution then unmark this [row, column] (Backtrack)

and go to step (a) to try other rows.

4) If all rows have been tried and nothing worked, return false to trigger backtracking.

 

 

Explanation:

 

  • As previously discussed backtracking is a sort of recursion, we shall see how it is implemented through the program.
  • Consider a n x n chessboard, that is n rows and n columns. This value is to be greater than or equal to 4, as for n = 1/2/3, there is no solution possible with the said constraints of no queen attacking the other.
  • We have created 3 functions in order to facilitate us in problem solving.
  • The n queen function: is used for ensuring placement of all queens onto the chessboard satisfying the mentioned conditions, that no queen should be able to attack the other queen on the board.
  • The queen function calls the placeholder function, which checks if there is any threat from any of the queens previously placed both column wise and diagonally.
  • If a queen can be placed in the particular column, then the function placeholder will return true i.e 1 else the function checks will return false i.e 0.
  • Whenever we encounter a phase where the placement of queen in current row is not possible in any of the columns due to the positioning of queens in previous rows,

a false value (0) is returned to the calling function placeholder, then we backtrack a level up and try other options for the previous row’s queens placements. And so on it continues until a feasible solution is reached.

  • chess_board[] is the array which is used to record in which column for that particular ith row of chessboard , the queen is placed. So the track of queen positioning is maintained by this array.
  • Once, all the queens have been placed on satisfying the requirement the display function is called from within the n queen function ; which prints the final / possible solutions.
  • Remember that backtracking is used in problems which align to the concept of partial solutions..
  • It is a time consuming algorithm and not efficient in nature. We shall trace some initial steps of solving this problem
  • Initially the chess board will be empty.
  • 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.

 

  chess_board 1
Index (denotes row) -> 1 2 3 4

 

  • 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 X X 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.

 

  chess_board 1 3
Index (denotes row) -> 1 2 3 4

 

 

  • 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 X X Q
  3 X X X X
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 X X X 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.

 

  chess_board 1 4
Index (denotes row) -> 1 2 3 4

 

 

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

 

1 2 3 4
1 Q
2 X X X Q
  3 X 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.

 

  chess_board 1 4 2
Index (denotes row) -> 1 2 3 4

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 X X X Q
  3 X Q
4 X X X X

 

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 X X X X
  3 X X X X
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 X Q
2 X X X X
  3 X X X X
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 X Q
2 X X X X
  3 X X X X
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:

  chess_board 2 4 1 3
Index (denotes row) -> 1 2 3 4

 

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.

Report Error/ Suggestion

Related Posts:

[yuzo_views]











CopyRight © 2019

CopyRight © 2019