All about backtracking ! :D
Imagine you are given a task of placing N number of queens on an N X N chessboard such that no queen attacks the other. Solving it manually is easy for a very small value of N, but if the value of N is increased to a very high value, Energy and time required will be exhausting and in this era of automation, this is not acceptable. To find a solution to this problem, there is a very very interesting concept up for you called, BACKTRACKING.
Backtracking: It is like a candidate elimination method. We incrementally build the candidates to the solution(solve the problem step by step), and eliminates the candidate(backtrack) as soon as it determines that the candidate cannot provide a valid solution.
Backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.
The N-Queen Problem in Detail:
You are given a board of dimensions N X N and your task is to place N queens on this board in such a fashion that no queen attacks the other.
Solution:-
Place the queen column wise from leftmost column, check whether queen is safe in row and is safe diagonally If there is no valid(safe) place left on the board we backtrack i.e we try change the position of last queen placed safely, if it is not possible then we backtrack further and so on.
Algorithm:-
Step 1:- Start with the leftmost column.
Step 2:- Try all rows in the current column. Do the following for every row iteratively.
a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution(board[row][column]=1) and recursively check, if placing the queen there leads to a solution.
b) If placing the queen, in [row, column], leads to a solution, then return
true.
c) If placing queen doesn’t lead to a solution then umark this [row,
column] (Backtrack) and go to step (a) to try other rows.
Step 3:- If all rows have been tried and nothing worked, return false to trigger backtracking.
Let’s understand this with an simple example
Assume the value of N is 4.
After placing the queens, the board should look like this :
Tracing the algorithm :
We will represent position with index.
Step 1:-Place the queen in the left most column. If it is safe, we place the queen at (0,0).
Step 2:- Recurse to next column. We again check if the row,column is safe to be placed. If yes, we place second queen. If no, we check for other rows. Currently, our queen is safe at (2,1), since (0,1) and (1,1) are not safe.
Step 3: Repeat step 2 for the next column. Here comes the hitch in the matter, since there is no valid position left for the third queen in the third column. (see the image)
Step 4: Time has come to backtrack. We assume that second queen is placed at a wrong position and hence,we need to find another valid position. We place the second queen at (3,1) and place third queen at (1,2) and now board looks like
Step 5 : Now we try to place fourth queen, but there is no valid position left on the board.
We backtrack again and try to find another valid position for the third queen. But this position does not exist either. Hence, we now backtrack again to find a position for the second queen. Again we don’t have a position left and again we backtrack. So, we place the first queen at (1,0) and repeat the steps again (second queen(3,1) , third(0,2)) until valid positions are found for all the queens..
Code in C++:
#include <iostream>
using namespace std;
int n;
//To check whether the queen can be placed in given row, is it safe from all the direction
bool safety(int board[][100], int row, int col)
{
int i,j;
//checking safety in row
for(i=0;i<col;i++)
if(board[row][i]==1)
return false;
//checking safety from upper diagonal
for(i=row,j=col;i>=0&&j>=0;j — ,i — )
if(board[i][j]==1)
return false;
//checking safety from lower diagonal
for(i=row,j=col;i<n&&j>=0;j — ,i++)
if(board[i][j]==1)
return false;
return true;
}
//Placing queen in specified column if it is safe
bool placeQueen(int board[][100], int col)
{
int i;
//Base condition all columns are checked all the queens might have been placed
if(col==n)
return true;
for(i=0;i<n;i++)
{
if(safety(board, i, col)) //Check safety at (i,col)
{
board[i][col]=1; //Place the queen initially
if(placeQueen(board, col+1))
return true; //Queen is placed safely in col =col+1
board[i][col]=0; //backtracking step, queen is removed from (i,col) since no row in col+1 is safe
}
}
return false;
}
//function to print the solved board
void print(int board[][100])
{
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++)
cout<<board[i][j]<<” “;
cout<<endl;
}
}
//Main function
int main()
{
cout<<”Enter the dimension of the board”;
cin>>n;
int board[100][100];
bool possible=placeQueen(board, 0);
cout<<”solution”<<endl;
if(possible) // If solution is possible
print(board);
else
cout<<”impossible”<<endl;
return 0;
}
If you wish to have a better illustration of what exactly happens, click here. (Source :Wikipedia)
Find the codes in following languages by clicking on the links below :
Java :- https://github.com/shenoyaditya11/Algorithms/blob/master/Queens.java
Python : https://github.com/samyuktaprabhu/Algorithms/blob/master/NQueens.py
Add-ons :
- This is a very efficient algorithm, which considers all (n2)n possible placements of n-queens, and then filters these to remove all placements that place two queens either on the same square or in mutually attacking positions leaving, n2!/(n*(n-1))! possible queen placements.
- Based on the concept of Backtracking, there are several other interesting examples and problems available. Some of them are :
→ Knight’s Tour Problem
→ Rat In a Maze Problem
→ Subset Sum
And so on…
Feel free to suggest for changes by commenting in the comment section below. :)
Thank You.
— Written by Aditya Shenoy and Samyuktha Prabhu
#IndiaStudents #algorithms #coding #programming #code #programmer #computerscience #computer