In the previous video, we have discussed the approach that we can take to solve the N-queens problem.
We have also discussed what are the various criterias to be checked when placing a queen at a particular
position.
For example, to check whether we can place a queen over here, we would have to do the column, check
the top left diagonal check and the top right diagonal check.
Now in this video, let's proceed and write the pseudocode of the approach that we have discussed.
And over here I've also placed the backtracking blueprint that we had previously discussed.
So let's get started.
Let's say we will have to write a recursive function.
And let's just call that recursive function backtrack.
And to that function we will be passing how the board looks at that particular point.
And we will also be passing the row.
So initially we pass the board and we pass row0 to it.
And once we are inside the function let's first write the base case.
The base case would be if row is equal to four let's say n is equal to four.
So notice that the valid row values are zero, one, two and three.
So the first invalid value would be four right.
So when we encounter the first invalid case we would have hit the base case.
So we can say if row is equal to n or in this example if row is equal to four, we will just append
that particular board to the results array and return.
So this is our base case.
Now let's proceed and write the for loop for the various choices that we can make over here.
Now in this case, for a particular row, the choices that we have are column zero, column one, column
two, and column three, because we know that we will fill only one queen in one row.
But then we can do it either here or here or here or here.
So the choices are for column in zero, one, two and three.
So these are the choices that we have.
And before making the choice we need to check whether that particular choice is valid or not.
And that's where we will use the is valid function that we are discussed where we will do the column
check top left diagonal check, and top right diagonal check.
So let's write that over here.
So if is valid.
So if it's valid to place a queen at that particular position then we will go ahead with the choose
help and the recursive call and the revert choice.
So these three steps.
So let's proceed with that.
So first we will fill the Queen in that particular position which is the choose step.
And then we will recursively call the same function again.
So over here we have named the function itself backtrack.
So we will recursively call the function again.
And we will pass the board.
And we will pass rho plus one to it.
Right.
So the board and rho plus one will be passed to it.
And then we have the revert choice step which is removing this queen and placing a dot at that position.
Because in the question it's given that an empty place is indicated by a dot.
So this is the pseudo code of the approach that we have discussed.
And notice that it is in line with the backtracking blueprint that we had previously discussed.
Now do remember the backtracking step is this step over here where we revert the choice that we had
previously made.
And this is especially important because we want all the possible solutions.
So once we get a solution, we backtrack to identify other possible solutions.