Backtracking in C
Track completion, mastery, and revision.
What does the name itself suggest?
Backtracking means taking a step back, tracing the route back up to 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? These questions will be answered in the next few sections.
Background and Understanding Basics
1. Introduction:
* Backtracking is a refinement method of the Brute-Force method. The backtrack method means it finds the number of sub-solutions, and each may have several sub-divisions, and the solution is 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."
2. Example:
* To understand the above definition, consider that you have to go from starting location 'A' to destination 'B'. Along the path, you come across a crossroad with 3 paths in front of you. They all lead forward, but there is no guarantee that all will lead to destination 'B'.
* At this point, the option you have is to try all the paths and check if they lead to spot 'B'. If the first road does not lead you to 'B', you come back (backtrack your route) to the crossroad again and try new paths until one of them takes you to your destination.
* So basically, we attempt to solve a sub-problem, and if we don't reach the desired solution, we undo whatever we did for solving that sub-problem and try solving another sub-problem.
3. 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 to the problem and move ahead with this approach toward 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 a new candidate.
* If that level again does not contain the correct solution, we backtrack one level further up in the hierarchy, and so on.
* If we end up at the root, we say that the solution is not available in combination with the given constraints.
* Else, if we find a potential candidate that will lead us to the solution, it will become part of the partial solution and be used as 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.
4. Applications:
Backtracking can be applied only for problems that work with the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.
* Backtracking is used for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.
* It is often a convenient technique for parsing and other combinatoric optimization problems like the traveling 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 systems as well.
EXAMPLE: TO SOLVE THE N-QUEEN PROBLEM
Problem Statement:
The N-Queen problem is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, the following is a solution for the 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, and diagonally with any 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 as any other queen.
-
We start with N = 4, as for N = 1 to 3, a 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_boardarray 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
displayfunction is called from within thenqueen_functionto 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 to place the queen in the first row. Hence, the function call is row = 1 and n = 4 (number of queens / size of the board).
1 2 3 4
1 [Q] * * *
2 * * * *
3 * * * *
4 * * * *
First, the placeholder function is called to check if the queen can be placed in the first column, hence col = 1. Since no queen is placed on the board before, there is no threat, and the placeholder function returns value 1 = true.
Thus, the array chess_board, which houses the columns for respective rows where the 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 the queen in the second row. Hence, the function call is row = 2 and n = 4 (number of queens / size of the board).
1 2 3 4
1 [Q] * * *
2 * [Q] * *
3 * * * *
4 * * * *
The placeholder function is called to check if the queen can be placed in the first column; however, since the queen in the first row is placed in column 1, 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 the next column, i.e., col = 2. Since there is a threat of a diagonal attack from queen 1, the value returned is 0 = false, so queen 2 is still not 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 the queen in the third row. Hence, the function call is row = 3 and n = 4.
1 2 3 4
1 [Q] * * *
2 * [Q] * *
3 * * [Q] *
4 * * * *
When we try to place queen 3, we have a threat in all the columns, either in a straight line or diagonally from previously placed queens. A value 0 = false is returned by nqueen(row = 3, n = 4) to the calling function nqueen(row = 2, n = 4).
Step 4: Since backtracking happens, we again try to re-place the previously placed queen, queen 2.
1 2 3 4
1 [Q] * * *
2 * [Q] * *
3 * * * *
4 * * * *
Since the 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, where 4 stands for column 4 of row 2.
Step 5: We now come back to row 3 and try to 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 the queen in the fourth row. Hence, the 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, none of the columns are feasible for its placement. Backtracking happens, and false is returned to the calling function nqueen 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 a 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 backtracking until we reach the final solution.
The chess_board array would look like this after solution 1 to the 4-queen problem is found.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int chess_board[20], count;
int placeholder(int row, int col);
void nqueen_function(int row, int num);
void display(int num);
void nqueen_function(int row, int num) {
int col;
for (col = 1; col <= num; col++) {
if (placeholder(row, col)) { // Check if queen can be placed
chess_board[row] = col;
if (row == num) { // All queens placed
display(num);
} else {
nqueen_function(row + 1, num); // Place remaining queens
}
}
}
}
int placeholder(int row, int col) {
int i;
for (i = 1; i <= row - 1; i++) {
if (chess_board[i] == col) { // Same column
return 0;
}
if (abs(chess_board[i] - col) == abs(i - row)) { // Diagonal conflict
return 0;
}
}
return 1; // Safe position
}
void 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");
} else {
printf("\t*");
}
}
}
}
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);
}
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.
Finished reading?