In the previous video, we have discussed the problem statement and we have got a good understanding
of what is asked of us in this video.
Let's try to solve this question, and let's think about what approach to take to efficiently solve
it.
Now, first, let's take an example and make a few observations to develop the intuition required to
solve this question.
Let's say n is equal to four.
Now if n is equal to four we have a 4x4 chessboard.
Now over here let's make a few observations.
The first observation is that let's say we are filling the board row by row.
If we are doing that, notice that we will be filling a queen.
Only one queen in a row, because you can't place two queens in the same row because they would be attacking
each other.
So in one row there will be only one queen.
So this is an interesting observation.
Let's now say that we want to evaluate whether we can keep a queen at this position over here.
Now to know whether this is a valid way of placing a queen.
What all checks would be required.
The first check that would be required is the column check, or we would need to check the cells in
this particular column which comes before this.
Now let me just put indices over here.
So we have 0123.
These are the indices of the rows and 012 and three.
These are the indices of the columns.
Now we are trying to place a queen at column with index one.
And again the row is one.
So we would need to check every row before this.
And we would need to check the column at index one.
So basically if we were trying to fill something like this.
If you were trying to fill this position, we would have to check all of these places.
Because if there is a queen over here, it could move in this manner and it would attack this queen.
So that's why we would first need to do a column check.
What would be the next check that is required.
The next check that's required is to check the top left diagonal and the top right diagonal.
Now the top left diagonal is this part over here.
And the top right diagonal is this part over here.
Because a queen can move diagonally as well.
Now we are only checking the top part because we are filling from the top.
We would have filled this row before we come to this row, but we have not yet filled anything in these
rows, so that's why it's sufficient to check the top left diagonal and the top right diagonal.
Now let's take a look at how the algorithm would play out.
Now we have understood what checks are needed, and we have also made some interesting observations,
such as that we will be filling only one queen per row.
And let's say we are filling the queens row by row.
And let's say we are starting at row with index zero.
Now let's see how this plays out.
So initially we have row with index zero.
And we are trying to fill a queen in this row.
And we start with the first column.
And we see that yes it can be filled because there is no other queen on this board at this point.
Now we proceed and recursively we move to the second row.
Now, when we are trying to fill a queen in the second row, we notice that we can't place a queen over
here and over here because this queen would attack it, right?
Because it can move in this way and it can move diagonally as well.
So therefore the next position that we find is over here and we can place a queen over here.
And again we would recursively call the function to place a queen in the next row.
Now when we are trying to place a queen in this row, notice that you can't place a queen over here
because this queen would attack it.
You can't place a queen over here because this one would attack it.
Similarly, you can't place one over here again, this one would attack it, and you can't place a queen
over here as well, because this queen would attack it.
So we find that there is no place available for placing a queen over here, so we can't fill it.
And therefore this is actually not a valid solution.
And again, this scenario has occurred because of the way that we filled queens in these two rows.
So as this is not a valid solution, there is no point in proceeding with this branch.
Therefore we prune this branch and we backtrack, which means that we come back to the previous case
and we remove what we had filled over here.
And we tried to place a queen in a different position.
So let's say we try to put a queen over here and we see that that's valid.
And again, we make a recursive call to fill a queen in the next row.
Now over here we see that we can't place a queen over here because this one would attack it.
But we can place a queen over here.
And in this way it would again recursively call the same function to place a queen in the next row.
So this is how the backtracking algorithm would solve this.
And it would give us all the possible solutions.
Because once we get a solution again, it would come back to the previous call and we would see whether
we can place a queen in another position.
So in a similar manner, finally, we would again come back to this place which is at row index zero,
and we would remove this in the backtracking step, and we would place a queen in the next column.
And again it would recursively call the same function to try whether we can place a queen in the next
row.
So in this way we will be able to get all the possible valid ways of placing queens n queens on an n
by n chessboard.
And once we get a solution, we would just append that particular way of filling queens on the n by
n board to a results array, so that finally we can just return that results array.
When we trace the algorithm, we also saw how the backtracking step would work.
Now again, let's just quickly see what would happen in case we get a solution.
So let's say we have filled three rows and we are trying to fill a queen in the fourth row over here.
And we see that we can actually place it over here.
And we have got a valid solution.
So this solution over here would just be appended to the results array.
And finally when we have found all the solutions we will return this results array.
So this is the approach the backtracking approach that we can use to solve the n queens problem.