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.
