In the previous video, we discussed the approach, the backtracking approach that we can take to solve
the Sudoku solver coding interview question.
In this video, let's proceed and write the pseudo code of the approach that we discussed.
So when we are presented with the board, the first thing that we need to do is we need to identify
the next empty cell.
And this is what we will do in every recursive call.
Now once we identify an empty cell, we will try the numbers from 1 to 9, and we will see which number
would be valid to be filled in that particular empty cell, keeping in mind the three rules which have
to be satisfied.
Now, let's say there are two outcomes or two possible outcomes from trying these numbers.
The first outcome is that we get a valid number.
And it could also so happen that none of the numbers fit in in that empty cell.
Now, if we do get a valid number we proceed and fill that number in the board.
And once we have filled that number in that empty space, we again recursively call the same function
to fill the next empty cell.
Now, if we are not getting any valid number for the empty cell at hand, it means that whatever we
have filled so far is not correct and therefore we can stop.
There's no more point in proceeding down this path.
Therefore, we would just return and prune this path.
Now, once we return over here, we would come back to the recursive call to the previous call, which
actually called the next empty cell.
Like again, for example, we are trying to fill this empty cell.
We filled something and we recursively called the same function to fill the next empty cell.
Now let's say in this case we are not getting any valid number.
Therefore we will return and we will come to this part over here, which is this line of code where
we had called the function recursively to fill the next empty cell.
Now at this point, because what we filled over here is wrong, because that's why we were not able
to get anything valid over here.
What we do is we backtrack, which means that we change the number that we had filled over here and
we try another possible combination.
So again, the backtracking step is reverting the change that we had done over here.
Now, if we are not able to identify any empty cell, what would that mean.
That would mean that the board is already full or the board has been solved.
And in that case we can just return true.
Because again, remember we are just trying to find one solution as per the problem statement given
to us.
Now, if it returns true, then again it would be in this call.
Because let's say we just have two empty spaces.
So we fill the first empty space.
We recursively call the same function to fill the second empty space.
And when we again recursively call the function, let's say in our hypothetical scenario, if there
are no other empty cells, it would return true from here, and we would come back to this place where
we had recursively call the same function.
And we are getting back true over here.
Right?
So when it returns true, we can just stop because again the question just asks us to find one solution.
Now if it's not returning true, that would be this scenario over here.
Because we will come back over here only when either it returns true or it does not return true, because
otherwise we would just go deeper and deeper till we are done with filling the board.
And then we would start coming back with either true or false, and if it's full, we would be coming
back with true.
So the other possibility of coming back over here is when we are not able to fill any of the values.
And in that case, we would have to return false.
And this would be an indication that we can proceed to the next line, which is the backtracking step.
So we remove whatever we filled over here and we try a different number.
And again when we get true, we can just stop because it indicates that we have found the solution.
So this is the pseudo code that we can use to implement the backtracking approach for the Sudoku solver
problem.
Now let's compare this pseudo code with the backtracking blueprint that we had previously discussed.
So we have the blueprint over here.
Notice that in the blueprint, the first thing that we had over here was the base condition.
So if it was solved we could return.
So that's what we have over here.
If we see that there is no empty cell, we can return.
Now, the other part over here is that we were exploring all the choices.
And in the Sudoku solver problem, the choices that we have are the values from 1 to 9.
And then over here we were checking whether is valid, whether a particular number is valid to be filled
in an identified empty cell.
And that's the check over here is valid choice.
And again the choice is the number that we have chosen.
And then over here in the blueprint we have the three steps.
Choose recursively call the function again and then the backtracking step.
So notice that is what we have over here as well.
Fill is the choice step.
Then we have the recursive call over here.
And then over here we have the backtracking step.
So this is the pseudo code.
And it matches with the backtracking blueprint that we had previously discussed.
So let's go ahead and implement this and solve the Sudoku solver question.