Let's now get into the code for solving the Sudoku solver question.
Now over here we are given this function solve Sudoku and we are given a board.
Okay.
Now notice that it's mentioned over here that the function modifies the board in place to present the
solution.
Hence there is no need to return the board.
Okay, so this means that you don't need to return anything from this function.
You just need to complete filling the board.
So that is the task at hand.
All right.
Now first let's take a look at the skeleton of the solution which we have over here.
And then we'll go into the details.
So as we've discussed in the previous video this is a recursive way of solving this question.
And for this we are using a helper function which I've just named helper itself over here.
Okay.
And notice that we also have an is valid function over here.
We will be using this function to check whether we can place a particular number at a particular cell
in the board.
Okay.
And this helper function will keep calling itself recursively to complete filling the board.
And also notice that we have called the helper function for the first time over here.
So this is the skeleton of the solution that we have over here.
So again we just have two functions over here which is the is valid function and the helper function
over here.
Now first let's take a look at the helper function in detail.
And then we'll come back to the is valid function.
Now in the helper function the first thing that we are trying to do over here is we are trying to identify
the next empty cell okay.
And for that we have two for loops.
So in the first for loop we go from the row number zero up to row number eight okay.
And in the second for loop we go from column zero up to column eight.
So we are actually going systematically through each cell in the board.
And our aim is to identify the next empty cell.
And in the question, it's mentioned that an empty cell would have just a dot.
So if the row column combination at a particular instance is equal to this particular dot, it would
mean that we have identified an empty cell.
And then our next task is to identify what number we can fill in that particular empty cell.
And again for this we have another for loop over here.
Let me again change the color of my pen.
So we have another for loop over here.
And using this for loop num takes the values from one up to nine okay.
And we are going to convert the number to a string.
And then over here we are going to use the is valid function to check whether we can actually place
this particular number at the particular position in the board okay.
At the row column combination in the board.
And again we'll come to the details of this.
But let's say this returns true.
So if this returns true then we will just go ahead and fill that particular number in the board at that
particular row column combination okay.
And once we have done that we again recursively call the helper function to go ahead and fill the next
empty cell.
All right.
Now let's make a few interesting observations over here.
Notice that you have a return true over here okay.
Now when would this be triggered.
Notice that this over here you would reach this line of code if you come out of these two for loops
okay.
So again typically if you come out of this for loop.
So if you come out of this for loop and you reach over here, it would mean that you were not able to
identify any empty cell.
Okay.
So this over here would return true if the board is completely filled.
Okay.
And notice over here also you have a return.
True.
Now we have discussed that once you fill the particular number which returned true from the is valid
function in the particular row column combination which happens in this line of code.
So once you have done that we recursively call the helper function to fill the next empty cell.
But then why do we have a return true over here.
Let's try to understand that.
Now for this let's take the example where let's say we just have three cells to be filled in the board.
Okay.
So there are just three empty cells and everything else is already filled in the board.
So the way that this algorithm would go ahead and fill these cells is that first it would go ahead and
fill this cell.
Then it would make a recursive call to fill this cell.
And then another recursive call would be made to fill this cell.
And then again we would make one more recursive call, at which point this over here would be reached,
because we see that there is nothing empty and we would return true.
Okay.
So we would get back true over here.
So this over here would return true over here.
And again, notice this happened over here because after we filled this particular value over here,
which is at this line of code, we made a recursive call, okay.
And we come back over here and we get true.
Okay.
Now because at this point the board is already filled.
We don't need to go any further deeper.
And we can just return from here to this place as well.
Okay.
And for that we need this return.
True.
So this over here, if helper board, this over here would be true when the board is full and then we
propagate it back or upwards through returning.
True over here.
So this over here would return true.
And we come over here and again remember this over here got filled through a recursive call which was
triggered at this instance.
And at that point the code reached over here right where this call happened.
So therefore when we return true we come over here.
And because again we see we got true over here.
This also returns true.
And we come over here and finally this also returns true okay.
So that's why over here also we need to return true.
And then the final interesting thing to notice over here is we have returned false over here.
Now when would this be triggered.
Let's try to think about that.
So notice that this return false would happen if you come out of this for loop, which means that there
is no number which can be filled at that particular row column combination.
Okay.
So is valid returns false for all the possible numbers at that particular cell in the board.
And in that case we would come over here and we would return false.
Now what is the significance of this again remember we would be returning false to a recursive call.
So this false would come over here okay.
And when we get false over here it means that the way that we have filled the board so far is not correct.
And we have to backtrack and we have to try a different combination.
So when we get false over here, we don't return true, but rather we come over here and we backtrack.
So this is the backtracking step.
So what we are doing over here is whatever got filled in this line of code is being changed or reverted
back to an empty cell.
And then we again come over here and we try a different number to fill at that particular cell in the
board.
Okay.
So that's how this solution works.
Now let's quickly review what we have discussed.
Let me clean this up a little bit.
So what we have discussed is in the helper function over here first we try to identify the next empty
cell.
And then once we have identified an empty cell we go through the numbers from 1 to 9.
And we are going to check whether we can fill that particular number at the particular cell in the board.
So that's what we're doing over here.
Using the is valid function.
And to the is valid function.
We are passing the board the row the column and the particular car okay.
Car at this point is the number.
And we just converted it into a character.
Now if this returns true then we go ahead and fill that particular number at that particular cell in
the board.
And we recursively call the helper function to fill the next empty cell.
Now this call over here can either return true or it can return false.
Now, the first time that we could get true over here is when this is triggered.
Which means that the board has been completely filled.
The reason for that is that this over here would be triggered when we are not able to identify any empty
cell and we come out of the for loop and we come over here.
So that's the first time we could get true over here at this place in a particular instance of a recursive
call.
And we can also get true when it is propagated back.
Right.
We have seen this is the case where it was returned for the first time.
True.
And then it gets propagated back in this manner.
And in that case also this over here returns true.
Okay.
And we've also seen that this over here would return false if this over here is triggered, if this
line of code is.
Triggered, and this would be triggered when we have tried all the numbers from 1 to 9 to be filled
at a particular cell, but nothing returned.
True or the is valid function did not return true for all the numbers from 1 to 9 for that particular
row and column combination, which means that the way that we have filled the board so far is not correct,
and we have to backtrack.
So at this point we come over here and we return false.
And when we get false over here, we don't get to this line of code, but rather we come over here and
we backtrack.
And this is the backtracking step in which we are reverting the change that we have made in this line
of code.
We have filled a particular number at that particular row column combination in the board over here.
And that's being reverted over here.
And we again come over here and we try another number to be filled at that particular cell in the board.
So this is how the helper function works.
Now all that remains for us to be discussed is the is valid function.
So let's just quickly discuss that as well.
Now, as we've discussed in the method video, the is valid function just has to check whether the particular
number at hand can be filled at the particular cell that we are considering on the board, and for that
we have to do three checks.
We have to do the row check, we have to do the column check, and we have to do the box check.
Now the row and column check is pretty straightforward.
So you just need to keep one constant and then change the other value from zero up to eight.
So over here we have board x and call.
In which case you're keeping the column constant and you're changing the row value.
So when you're keeping the column constant and you're changing the row value you're actually checking
the column okay.
So this is the column check.
And this over here keeps the row constant.
And you're changing the column.
So this is the row check okay.
So over here you are checking whether the particular number that we are considering has already been
filled in the column.
And over here you're checking whether the number that we are considering has already been filled in
the row.
Now, if either of these is true, then we can return false, which means that the number has already
been used in that particular column or row.
And because of that, we cannot fill the number that we are considering at the particular position in
the board.
But if none of these return false, then we go ahead and do the box check, which is what we're doing
over here.
Now, we have discussed the logic for this in detail in the previous video, but over here let's just
discuss the implementation.
So we have two variables r and c.
And r is equal to three into math dot floor row by three.
So when you do that you are just taking the integer value.
When you are dividing row by three and you're avoiding the decimals and you multiply that with three.
And to that you add math dot floor x by three okay.
And remember x is this value over here which iterates from 0 to 8.
And in a similar manner c is equal to three into math dot floor called by three plus x percentage three.
So again I'm not going into the details of this logic, which has already been discussed in detail in
the previous video.
But once we get R and C, we have seen that by using this formula, we can get all the row column combinations
in the particular box that we are considering, and we are just checking whether the number at hand
is already present in the box.
Now, if we see that the number is there in the box, then we return false, which means that the number
cannot be filled in the position that we are considering.
But if we don't get false, then we would come over here.
And if we reach this line of code, it means that the column check, the row check, and the box check
has passed.
And because of that, we can fill the number that we are considering at the particular position in the
board that we are considering.
So this is how we can write the is valid function.
And we have discussed that we will be calling the is valid function over here whenever we are considering
a particular number, and whenever we try to see whether we can fill that number at the particular row
column combination, we call the is valid function and we pass to it the board, the row, the column,
and the number that we are considering.
And if we get true over here only, then we go ahead and fill that particular number at that particular
row column combination in the board.
So this is how we can solve the Sudoku solver 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 working.
And again you could make use of the user logs in case you are stuck somewhere and you need some help
for debugging your code.
Now again, because over here the input is a board, you could copy this and paste it on a notepad to
visualize this in a better manner if required.