Algorithm

Getting Started with AlgorithmWhat is an Algorithm?

Characteristics of Algorithm1 Topic

Analysis Framework

Performance Analysis3 Topics

Mathematical Analysis2 Topics

Sorting AlgorithmSorting Algorithm10 Topics

Searching Algorithm6 Topics

Fundamental of Data StructuresStacks

Queues

Graphs

Trees

Sets

Dictionaries

Divide and ConquerGeneral Method

Binary Search

Recurrence Equation for Divide and Conquer

Finding the Maximum and Minimum

Merge Sort

Quick Sort

Stassen’s Matrix Multiplication

Advantages and Disadvantages of Divide and Conquer

Decrease and ConquerInsertion Sort

Topological Sort

Greedy MethodGeneral Method

Coin Change Problem

Knapsack Problem

Job Sequencing with Deadlines

Minimum Cost Spanning Trees2 Topics

Single Source Shortest Paths1 Topic

Optimal Tree Problem1 Topic

Transform and Conquer Approach1 Topic

Dynamic ProgrammingGeneral Method with Examples

Multistage Graphs

Transitive Closure1 Topic

All Pairs Shortest Paths6 Topics

BacktrackingGeneral Method

NQueens Problem

Sum of Subsets problem

Graph Coloring

Hamiltonian Cycles

Branch and Bound2 Topics

0/1 Knapsack problem2 Topics

NPComplete and NPHard Problems1 Topic
NQueens Problem
One of the most common examples of the backtracking is to arrange N queens on an NxN chessboard such that no queen can strike down any other queen. A queen can attack horizontally, vertically, or diagonally. The solution to this problem is also attempted in a similar way. We first place the first queen anywhere arbitrarily and then place the next queen in any of the safe places. We continue this process until the number of unplaced queens becomes zero (a solution is found) or no safe place is left. If no safe place is left, then we change the position of the previously placed queen.
The above picture shows an NxN chessboard and we have to place N queens on it. So, we will start by placing the first queen.
Now, the second step is to place the second queen in a safe position and then the third queen.
Now, you can see that there is no safe place where we can put the last queen. So, we will just change the position of the previous queen. And this is backtracking.
Also, there is no other position where we can place the third queen so we will go back one more step and change the position of the second queen.
And now we will place the third queen again in a safe position until we find a solution.
We will continue this process and finally, we will get the solution as shown below.
As now you have understood backtracking, let us now code the above problem of placing N queens on an NxN chessboard using the backtracking method.
Implementation
#include <stdio.h>
//Number of queens
int N;
//chessboard
int board[100][100];
//function to check if the cell is attacked or not
int is_attack(int i,int j)
{
int k,l;
//checking if there is a queen in row or column
for(k=0;k<N;k++)
{
if((board[i][k] == 1)  (board[k][j] == 1))
return 1;
}
//checking for diagonals
for(k=0;k<N;k++)
{
for(l=0;l<N;l++)
{
if(((k+l) == (i+j))  ((kl) == (ij)))
{
if(board[k][l] == 1)
return 1;
}
}
}
return 0;
}
int N_queen(int n)
{
int i,j;
//if n is 0, solution found
if(n==0)
return 1;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
//checking if we can place a queen here or not
//queen will not be placed if the place is being attacked
//or already occupied
if((!is_attack(i,j)) && (board[i][j]!=1))
{
board[i][j] = 1;
//recursion
//wether we can put the next queen with this arrangment or not
if(N_queen(n1)==1)
{
return 1;
}
board[i][j] = 0;
}
}
}
return 0;
}
int main()
{
//taking the value of N
printf("Enter the value of N for NxN chessboard\n");
scanf("%d",&N);
int i,j;
//setting all elements to 0
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
board[i][j]=0;
}
}
//calling the function
N_queen(N);
//printing the matix
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("%d\t",board[i][j]);
printf("\n");
}
}
Explanation of the code
is_attack(int i,int j)
→ This is a function to check if the cell (i,j) is under attack by any other queen or not. We are just checking if there is any other queen in the row ‘i’ or column ‘j’. Then we are checking if there is any queen on the diagonal cells of the cell (i,j) or not. Any cell (k,l) will be diagonal to the cell (i,j) if k+l is equal to i+j or kl is equal to ij.
N_queen
→ This is the function where we are really implementing the backtracking algorithm.
if(n==0)
→ If there is no queen left, it means all queens are placed and we have got a solution.
if((!is_attack(i,j)) && (board[i][j]!=1))
→ We are just checking if the cell is available to place a queen or not. is_attack
function will check if the cell is under attack by any other queen and board[i][j]!=1
is making sure that the cell is vacant. If these conditions are met then we can put a queen in the cell – board[i][j] = 1
.
if(N_queen(n1)==1)
→ Now, we are calling the function again to place the remaining queens and this is where we are doing backtracking. If this function (for placing the remaining queen) is not true, then we are just changing our current move – board[i][j] = 0
and the loop will place the queen on some another position this time.