Let's now get into the code for solving the N-queens question.
Now over here, notice that we are given n and n could be 4 or 3 a number, right.
So we are not given the board.
So we have to go ahead and create the board.
So that's what we're doing over here.
And then before we get into the details of the code, let me quickly walk you through the skeleton of
the approach that we have over here.
So notice that we have the position next queen function, which is the function that we will be recursively
calling to position the different queens in different rows of the board that we create.
Okay.
So notice that we do call it recursively over here.
But again we'll come to the detail soon.
And this is where we call this function for the first time.
And again we are passing the first row which is the row with index zero when we call it for the first
time okay.
So that's the position next queen function over here.
And we also have a few more other functions.
Let's take a look at them.
So notice that over here we have the is valid function.
Now we will be using this function to check whether we can place a queen at a particular cell in the
board.
And we also have a convert board function over here.
So let's get started with the details and we'll get to understand why we need this function over here.
So again as we've discussed initially we are given n and we are not given the board.
So we go ahead and create the board over here.
So notice that the board over here is an array of arrays okay.
And as per the requirement of the question, whenever we add a board to the results array, which is
what we have declared over here.
And finally we would be returning this when we fill every board to the results array that fits the requirement
okay.
So when we do that we'll have to fill to the results array an array of strings okay.
So to convert an array of array into an array of strings we will be using the convert board function
over here.
So we are just passing the board to it which at this point would be an array of arrays.
And then we will join the elements in a particular row together to form a string.
And in this way we will convert the board into an array of strings.
So that's what we're doing over here okay.
So this much over here should be pretty straightforward.
So let's now get into the details of the code which is pretty much analyzing the position.
Next queen function and the is valid function.
So first let's get started with the position next queen function.
So over here notice that this is a function that we will be calling recursively okay.
And over here first we have the base case.
And again we are given n.
Let's say n is equal to four.
Then the board would look like this right.
We'll have four rows and we will have four columns okay.
And the indices for example for the rows go from zero up to three where this three over here is n minus
one okay.
Now we will make use of this information to write the base case.
Notice that the base case over here is if the value of the row which is passed to the position x queen
function is equal to n.
Now if row is equal to n, we would have hit the first invalid input okay.
And you have discussed that you can write the base case.
Or you can think of the base case as the first invalid input or the last valid input.
So over here we have the first invalid input.
So when row is equal to n the value of row is out of bounds okay.
And at that point it would indicate that we have actually identified a board where we were able to place
a queen in every row.
And therefore we will just pass that particular board to the convert board function so that we get an
array of strings.
And then we will push it to the results array.
And the results array is what we finally return.
Okay.
So that's the base case of the position x queen function.
And again notice that to this function we have to pass the board and the row that we are dealing with.
So initially when we call this the row is equal to zero.
So after we fill a queen in this row we would be calling this function recursively.
And we will pass the next row which is the row with index one.
And it goes on in this manner.
Now let's take a look at the recursive case for the position x queen function, which is what we're
doing over here okay.
So basically what we're trying to do over here is for the row at hand, we will be trying to place a
queen at every column in the row okay.
So column goes from zero up to n minus one.
Because again notice over here if n is equal to four then the valid columns go from zero up to three
and three is n minus one okay.
So for the values from zero up to n minus one, we will check whether we can place a queen at each of
these positions using the is valid function.
So to the is valid function we will be passing the row, the column and the board, and this function
will either return true or false.
So if it returns true, we will fill a queen.
Over there at that particular column and row, which is done over here.
Board row column is equal to Q.
And then we recursively call the position x queen function with the next row okay.
And then this goes deeper and deeper.
And if we were able to place a queen in every row in this particular way of building the board, finally
we would be hitting the base case and we would make a new array, which is an array of strings, and
we would push it to the results array, which ensures that the value being pushed to the results array
is a snapshot of the existing board at that particular instance.
Now also do notice that over here we have the backtracking step which is about reversing the value or
the decision taken over here.
Okay.
So Q was entered at a particular cell over here.
And that's being reversed over here, which is the backtracking step okay.
And the reason for this or why we need this is because the question asks us to find all the possible
ways of filling n queens in an N into n board.
Okay.
And that's why even though probably over here, we may have arrived at a solution where we were able
to fill n queens in n rows, but still over here, after we return from this function, we would have
to backtrack and then we have to try other possible combinations.
Okay, so that's why the backtracking step is very important over here.
So the position x queen function is pretty straightforward.
So we have the base case over here which is checking whether row is equal to n.
And in which case we would form a new array which is an array of strings using the convert board function.
And in this way we would be pushing a snapshot of how the board at that particular instance looks like
into the results array.
And the results array is what we finally return over here.
Okay.
And the recursive case is we try to fill a queen at every column in the row at hand at this particular
instance, and to check whether we can place a queen in that particular cell or not.
We make use of the is valid function.
And we've also discussed why the backtracking step is important, because we need all the possible solutions,
or all the possible ways of placing n queens on an n into n board.
Now let's also take a look at the is valid function.
Now in the is valid function, there are basically three things that we need to check and to discuss
this, let's quickly draw this out so that it becomes visual and easy to relate to.
So let's say n is equal to four okay.
So that would mean we have four rows and we have four columns.
Now if we are trying to place a queen let's say over here, what would be the different checks that
we have to ensure.
First of all we are filling the rows from top to bottom in this solution.
So we do not need to check anything associated with this particular row.
Okay.
And we are also filling one queen only in one row because once we fill a queen in a row, we increment
the value of row and we recursively call the position next queen function.
Okay.
So this would mean that there is nothing to check regarding other cells in this particular row.
So there is nothing to check with respect to this row as well.
Now what are the other things that we would need to check.
Let's try to think about that.
So if we want to place a queen over here, then we should not have a queen anywhere in these two cells,
which is the same column where we are trying to place this queen over here, because otherwise they
would fight against each other, right?
It would violate the condition required.
So we would have to check that there is no queen over here.
And we will also have to ensure that there is no queen over here in any of these two cells.
And there should be no queen over here as well.
Okay.
So this over here is what we call the top left diagonal.
And this over here is the top right diagonal.
Again, we don't need to check anything below because we are filling from the top.
And we would not have filled anything over here.
So that's why we only need to check the top, left and right diagonals.
And we also need to check the columns from the beginning till the cell which is above this particular
cell over here, or the previous row of the row that we are trying to currently fill.
Okay, so these are the three checks that we need to have in the is valid function.
So to the is valid function we will be passing the row, the column and the board.
And to check whether there is any queen in these cells which are the cells above this particular cell
on the same column.
We have this for loop over here.
So for x is equal to zero x less than row okay.
So this would be the row value which for example in this case is equal to two.
So in this case x would take the values from zero up to one which is these two values okay.
And then we are just checking whether board at x at column is equal to q okay.
So board at x would give us the row and column gives us the column.
So we are checking whether these two cells over here have a Q or not.
And if they do have a.
It would mean that we cannot fill a queen over here, and in that case, we would just return false.
Okay, now proceeding to check the top left diagonal.
That's these two cells over here.
Notice that to get from here to here, we just need to decrement the row value and the column value
by one.
And then to get from here to here we would just need to again decrement the row and column values respectively.
So that's what we're doing over here.
So we start with r being equal to row and c being equal to column.
That's the values of this particular cell.
And notice that this loop will go till r and c are equal to zero.
Because zero is the last valid input for the index of the row and column.
Okay.
Then we keep decrementing the row and column.
And if we find that board at R and C at any of these points are equal to q, we would just return false.
Similarly, we also have checks for the top right diagonal.
And notice that to go this way we would have to decrement the value of row which is what we're doing
over here.
But we would have to increment the value of columns okay.
So that's what we're doing over here.
And again it's the same thing.
We are checking whether board at R and C is equal to q.
And if we see that it's equal to q we would just return false which would indicate that we cannot fill
a queen over here.
And after we are done with these three checks, if we did not return false, we would just return true,
because it would indicate that yes, we can go ahead and fill a queen at this particular cell.
Okay.
So that's how we have implemented the is valid function so quickly to review the solution that we have
written over here we have the position x queen function over here.
And this function takes care of filling a queen in each row.
And to evaluate whether we can fill a queen at a particular cell, we have the is valid function, which
has the three checks that we have discussed in detail.
Okay.
And again, remember initially we had to form the board because we are just given n we are not given
the board.
So board at this point is an array of arrays.
And then we have to convert board function to create a new array which is an array of strings.
And that would be pushed to the results array.
And again that happens over here.
If row is equal to n we would have hit the base case and we would make a new array which is an array
of strings.
And we would push it to the results array.
So this ensures that we are pushing a snapshot of the current instance of how the board looks like to
the results array.
And finally, when we get all the possible ways of filling in queens on a board which is of size n into
n, we will just return the results array.
So this is how we can solve this question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's passing all the test cases.
Now in case you're stuck somewhere do make use of the user logs.
So that will help you debug your code.