Hello friends my name is Tushar and today I'm going to talk about N-queen
problem.
So you're given an NxN board and there are N queens
You have to find any placement of these queens on the board so that they do not
attack each other. For example we have 4x4 board and this is one of
an arrangement such that these queens are not attacking each other.Here we're going to
use backtracking to solve this problem and i'm going to discuss in a little bit
how backtracking is going to work.
So how does the Queen attack? Queen attacks on the same rank,same file and
diagonally.So next let's first talk about how to find out if a square is
under attack from a queen or not.Let suppose the Queen was placed at square (1,2)
so row 1 column 2
so all this quares will be under attack from this Queen
Let's understand how.So all the,all the squares which are on the same row will
be under attack.All the squares which are on the same row will have the same row
value as the queen's square row value. So 1,(1,0),(1,1) and (1,3).
Similarly all the squares which are on the same column will be under attack.
So these are the 3 squareS which are on the same column and how we know that because
their column value 2,2 and 2 is same as the Queen's square's column value.
finally we have two kinds of diagonals so one going from top left to bottom right and the
other one going from bottom left to top right.For the one's going from top left
to bottom right
these are the two diagonals (0,1) and (2,3).
So to find out which are those,which are the squares we use the formula row -
- column so if you look at this one minus
if you do row-column here,this value will be 1-2 which is -1.
So any square
who's,who's row-column value is -1 will be on the same diagonal
as this queen so they will also be under attack.
So if you look at this square(0,1) which is this value,0-1 is -1 and 2,
3,2-3 is also -1 which is this square.So both the squares are on the same diagonal
of this queen so they are under attack. For the other diagonal going from bottom
left to top right
we use the formula row plus, row+column.
So this one is row
-column and this is row+column. So if you look at this 1+2 is
3,so any square whose sum is 3 will be on the same diagonal as this screen
so 3+0 is 3 which is this square,2+1 is 3 which is this square
and 0 plus 3 is 3 which is this square and as you can see they are on the same diagonal as queen
and so they are also under attack.
So next let's apply this simple formula on a real example.As i said before we're
going to use backtracking to solve this problem.Since our board is 4x4
our recursion will be 4 level deep.At the 0th level of recursion we're gonna
place the 0th queen on the 0th row. At the 1st level of the recursion
we're going to place the 1st queen on the 1st row such that she does not
attack the 0th queen.At the 2nd level of recursion we're gonna place 2nd queen
on the 2nd row such that she does not attack the 1st and the 0th queen and so on.
At any point of time if we cannot find a square for a queen on that row we're gonna
return false to the calling function and that,that level of recursion will then
try to place the queen on the next available
square of that row and if that doesn't work out then that function itself is
return false to the calling function above it and so on.
Also I've seen that lot of people struggle with recursion.
It really helps if you think of recursion as a tree because then you
can visualize how the,how the recursive calls are going back and forth
and that is what we're going to do next.
Also to save one time I have drawn some squares beforehand but assume that when
the recursion starts for the first time, only this
0th level exists.So next let's do this example. Here we're gonna place the 0th queen
on the 0th column of the 0th row,so queen goes here
she goes here and we're gonna note the position (0,0).Then we're gonna go into the
recursion and try to place the 1st queen on the 1st row such that she
does not attack the 0th queen.
So from here we go into the recursion,so we cannot place the 1st
queen on this square,we cannot place it on this square,this is the first available
square which is not under attack.
So we're gonna place the queen here and in this recursion tree I'm going to
place the queen here and then I'm also going to note this position (1,2) and
then again we're gonna go into the recursion.
So now we're going to look for the first available position for the queen 2.So this
square is under attack.Why,because it has the same column as this queen,this square is
under attack,why,because the difference of the sum of row+column for this
particular portion is 2+1,3 which is same as 1+2,3
so it must be diagonally with this queen which is why it is under attack.
similarly this,this
this square is under attack from this queen and this square is also under attack from
this queen
so this position is (2,3) so 2-3 is - 1 and 1-2 is also -1 which is
why it's under diagonally attack.
So we figure out we cannot place queen 2 on any of the square of row
2 so this function here is going to return false to the previous function
saying that I cannot find a place for the Queen.
So what this guy is going to do or the first level of recursion is going to do is
try to find the next available place for this queen.So it's going to place the
Queen here or I'm going to say that I'm going to place the queen here and in the
positions now we're going to say that the Queen's,that's 1st queen is placed
in (1,3).Then we are going to again look for,we're again gonna go into the
recursion and look for a position for queen 2,a square for queen 2.
So this square is under attack from this queen.
This square is available so we're gonna place the queen here and in this recursion tree
we're going to place a queen here and I'm going to note that,I'm placing the
queen on (2,1)
and then we're gonna go again into the recursion looking for a square for
queen 3 on the 3rd row.
So this,this square is under attack,this square is under attack,this square is under
attack and this square is also under attack.
So we cannot find a position for queen 3
so this function is going to return false saying that I could not find the
the
position for queen 3 on the 3rd row.
So then,2nd,the Queen at the 2nd row is trying to look for next available
square so this square is under attack from both the queens and this square is also under
attack from both the queens which means that queen 2 cannot be placed on any further,
other squares so this is going to return false to it's calling function
indiicating that I cannot find any other square for this queen we're gonna
remove this (2,1) from my positions list.position list is going to store our final
result
and this is going to return false to this queen.This,
the row 1 queen is already,is already reached its,its end so it will return
false to the 0th level queen.
So what we're going to do is we're going to remove this queen from here and we're gonna
remove it from the positions.So then, this queen is going to place itself on
the next available square.
So the next available square is this
(0,1)
and then it's going to again go into the recursion
So then we're going to again look for a square,for a queen 1.
So this square is under attack because 0+1 is 1 and 1+0 is 1 so it's on the diagonal
this square is under attack
this square is also under attack,this is the first available square.
So queen will go into the recursion from this particular position so we go into the
2nd level of recursion looking for a position for 2nd queen
So this square is not under attack
Also we're gonna note its position (1,3)
So this square is not under attack so we can place the 2nd queen here,its position
is (2,0) and here we're going to place this
queen here and then we go again into the recursion looking for a sqaure
for queen 3.So queen 3 cannot be placed on this square,it cannot be placed
on this square,it can be placed on this
square here so this time this position is (3,2) and this positon is(3,
2)
and now we have reached the,we have, we have done 3 levels of recursion
it means that we were able to place all the queens.So this is going to return
true,this is going to return true and this is going to return true which tells
this guy that all the queen were able to place themselves such that they're
not attacking each other and this here will be our
final result.(0,1) this Queen,(1,3) this queen, (2,0) is this queen and (3,2) is this Queen.
So the time complexity for this algorithm is exponential because of this
backtracking and going back and forth in the worst case it can go exponential and
the space complexity is O(n)
because our recursion in the worst case will be n level deep for an
NxN board.
So next let's look at the code for this algorithm.The main function here is solve
NQueenOneSolution,so we are looking for one placement of n queens on N
cross N board so that they do,they do not attack each other,so and the return type
is an array of position which tells us the positions of all this n queens.
First we initialize this array for storing our intermediate and final result.Then
we call this function solveNQueenOne SolutionUtil to it,we pass n
positions and then 0.0 is the 0th row from which we're gonna start our
recursion.So looking at this function first thing we do is we check if n is
equal to equal to row.So row is 0,n is 4 so it's not true
so then we iterate through every column so column goes from zero till n and see
which column on this row is safe.To do that we check all the previous queens
and see if,if the square is safe from the previous queens or not.
So initially there are no queens,so we can place our 1st,
0th Queen on the 0th row and 0th column so position is (0,0) and
then we put this into position array so (0,0) and going to the recursion.
So this time we're going to pass row+1. So our new row value will be 1.
And now again
1 is not same as n so we again,for loop for our column from zero till n
looking for a safe square for the 1st queen on the 1st row so to do that we
start,we look at all the previous queens so we for loop through all the previous queens
and see that they do not attack the square.
So the,so the square (1,0) will be attacked from the 0th queen,square (1,1) will also
be under attack from 0th queen,square (1,2) is the first safe square.
So we find,we find the safe square,we put it into our positions array and then
we again go into the recursion with value row+1.So now row is 2.Again
row is not same as n so again we look for a first safe square for queen 2 on
row 2 by checking with all previous queens.
So initially column is 0 so we cannot place,place queen on this (2,0),next
column is 1,we cannot place
queen at this square either because it's under attack from the 1st queen,we cannot
place at (2,2) and we cannot place at (2,3)
so we have to,so we did not find a safe place
so our for loop went from zero till n and then we did not find a safe square for
the 2nd Queen on the 2nd row so we break out of this for loop and return
false.
So when we return false we tell the queen before this,or the queen 1 that
you got to find another safe place.So we come back from the recursion in the 1st
in the 1st queen and since this is,this if condition is not true
so we again go back and increment our column value and look for the next
available safe position.So we are going to move our queen 1 to the next safe
position which is square (1,3). Again and we're going to add that,we're
going to update that in the position and then we're going to again call
recursion.
So this time again the value of row will be 2,again row is not same as n,again
we're going to look for a safe square for the queen 2 so (2,0) is not safe,
(2,1) is a safe square.So we found a safe square for queen 2 so again we're going
to put that into position array so (2,1) and we are going to go into the
recursion with row+1 value.So our row value will now be
3.3 is also not same as n,so again we're going to for loop from zero till n
looking for a safe square on the row 3
So
(3,0) is not safe,(3,1) is not safe,
(3,2) is not safe and (3,3) is also not safe.
So none of the squares on the 3rd row is safe.
So we're going to, so we're going to return false from this level of recursion to
the calling function.So at the row 2 this is going to get a false so it
will not go into this if condition and we're going to look for a next
available column for the queen 2 and there is no safe column for queen 2 so
we're going to backtrack a little bit more and now we're going to look for
next available safe column for Queen 1 and queen 1 has already reached
the end so it's going to return false itself.
So then we're going to reach row 0 and try to find another safe column for queen 0.
So the next available column is this,
(0,1) and that's where we're going to place the queen 0 and then we're going to
again go into the recursion.So value will be row+1.So this,this square is
not safe,this square is not safe,this square is not safe but this square is
safe.
So we found a safe square,we're gonna place our queen one at (1,3) and again
go into the recursion with row+1 value.So row is 2,this square is safe
so we're gonna place our queen 2 at position (2,0) and add that into
this array and then we're gonna go into the recursion with row value 3.So
(3,0) is not safe,
(3,1) is not safe,(3,2) is safe.
So then since we found a safe square
what we're going to do is ,we, then we're going to again go into the recursion
with value row plus 1 so ultimately we're gonna reach this point where n which
is 4 is going to become equal to row which is also 4,so we're going to
return true.
So what this means is,it returns true here,at the third level,at the row
3 level recursion.So that guy will return true to row,row 2 and row 2 will
return true to row 1 and row 1 will return true to row 0 and row 0 will return true
ultimately to this function,so allN QueenOneSolution function and then
since the solution exists then we're going to just return the contents of the
array which is positions
(0,1),(1,3),(2,0) and (3,2).
So this is the entire recursive algorithm for N queen solution.If you
want to see all possible solutions,not just 1 solution
I also have this code here,SolveNQueens and if you're interested you can
look at this code as well and this code is not very different from the
previous code.
So this is all I have to talk about N queen problem
Please like this video,share this video, comment on this video,check out my
facebook page and check out my github link.The link to this code is in the
description section of the video.Thanks again for watching this video.