In the previous video, we have understood the problem statement of the Sudoku solver question.
Now let's try to think how we can solve this question.
Now for this, let's take a sample board.
Let's say this is the board that is given to us.
And on this board notice there are various empty cells.
So we need to identify what we can fill over here.
And we have to do that in a way that the rules are satisfied.
Now we can solve this recursively because we just need to fill one empty cell and then recursively go
to the next empty cell and fill it and keep repeating this again and again till the whole board is filled.
Now, the brute force way of solving this, or the most simple way of approaching this, would be to
try all the numbers from 1 to 9 for every empty cell, and then from all of these boats that we come
up, we would just need to identify the solution from them.
Now, if we were to approach it in this manner, there would be nine to the power empty cells solutions.
Now why is that?
So let's say we just had two empty cells.
So the first empty cell could be filled in nine ways.
And the second empty cell can also be filled in nine ways.
So there would be a total of nine into nine, which is nine square solutions.
And then we would have to identify which is the correct solution from these 81 solutions.
Now if there are x number of empty cells this would be nine to the power x.
But then this obviously is not an efficient way of solving this.
So can we do better.
So let's think about this now a good way of solving this would be let's say we first fill this empty
cell.
Then let's say we proceed and fill this empty cell over here.
And let's say in one of the scenarios, when we try to fill the next empty cell, we are not able to
fill anything over here in a way that the three rules are satisfied.
Now, this is because probably what we filled over here and over here are not the right values.
So what we can do at this point is notice there is no point in going further down this branch or this
path, because this will definitely not lead to a solution.
So what we can do is we can backtrack.
That means we can come back over here to the previous cell.
Which is handled by recursion.
And then whatever we filled over here will be removed, which is the backtracking step.
And then we go ahead and try to fill this empty space with another value.
So this is the backtracking approach.
Now notice that this is much better than the previous approach that we've discussed, because any path
that does not lead to a solution is pruned.
And we keep working only with paths that can lead to a solution, which is what we ultimately need.
So let's make some space over here.
So again, one more interesting thing that you should remember over here is that backtracking is in
fact a brute force algorithm.
But the only thing is that it's better than just plain brute force, because any path that does not
lead to a solution or any useless branch is immediately pruned.
Now let's just walk through how the backtracking approach would solve this problem.
Again.
We have a board over here and we first identify the first empty cell, which is this cell over here.
Now the choices that we have are one, two, three, etc. up to nine.
So we start with the choice one.
Can we fill one over here without violating the rules?
Now notice over here one is there in this column.
So we cannot fill one over here.
So one is eliminated.
Now what about two.
Two is not there in this row.
Two is not there in this column and two is not there in this box.
So yes, two is a valid value that can be filled over here.
So let's say we go ahead and fill two over here.
And we proceed to the next empty cell which is this cell over here.
Now again the choices that we have are one, two, three etc. up to nine.
Now can we fill the value one notice over here we have one in this column, so we cannot fill the value
one.
What about two.
Two is already there in this row.
So two also cannot be filled.
What about three.
Notice three is there over here which is the same row.
Hence three also is not valid to be filled over here.
What about four?
Four is there in this box.
Notice that we have four over here.
So four is out.
What about five.
Five is there over here which is the same column.
So five is out.
What about six.
Six is there in this row.
So six is also out.
Seven is also out because seven is there in the same row.
And what about eight.
Notice that eight is not there in this column.
Eight is not there in this row and eight is not there in this box.
So yes, eight is a valid solution.
So let's go ahead and fill eight over here.
Now we proceed to the next empty cell which is this cell over here.
Again the choices that we have are one, two, three etc. up to nine.
Now can we fill one over here.
Notice that one is not there in this row, nor is it there in this column, nor is it there in this
box.
So yes, one is a valid number.
And we go ahead and fill one over here and we proceed to the next empty cell, which is this cell over
here.
Now again, the choices that we have are one up to nine.
Now, we can't fill one over here because one is there in this row.
Similarly, we can't fill two over here because notice two is there in this row.
Three is also there in this row.
And so one, two and three are out.
What about four four is there in this column.
Five is there in this column and six is there in this column.
So four, five, six are out.
What about seven.
You have seven.
Also in this column you have eight also in this column.
So seven and eight are also out.
And what about nine.
Nine is there in this row.
So again nine is also out.
So notice over here we are not able to fill any valid number in this empty space.
Now this has happened because one of these things that we previously filled is not correct.
So at this point there is no point in proceeding down this path.
And what is this path?
This path means having these numbers filled over here.
So there is no point in proceeding in this path.
So what we do is because we can't feel anything over here, what we do is we backtrack.
So we come back to this place over here.
Which is what we do as part of backtracking.
So we come back over here and again, the coming back is handled by recursion, but the backtracking
step is that we remove the value that we filled over here.
So we remove the one.
All right.
So we remove the one and then we proceed and try to identify the next possible value that could be filled
over here.
Now what about two.
Can we fill two over here.
No because two is there in the same row.
What about three?
Three is also there over here.
So we can't fill three.
What about four?
Four is over here, which is the same column.
So four is out.
What about five?
Notice five is there over here, which is the same row.
So five is also out.
What about six.
Six is there in the same column.
So six is also out.
What about seven now seven, eight and nine.
Notice all of these three are there in the same row.
So all of these numbers are out.
So notice that we are not able to fill any other value in this empty space.
Now why did this happen.
That's because one of these numbers that we previously filled is wrong.
All right.
So we cannot proceed further in this path because there's nothing valid that can be filled over here.
And therefore we prune this path, we come back and we backtrack.
All right.
So we come back over here and we change the eight that we had previously filled over here.
So we remove this eight and we try another value.
And in this manner the algorithm keeps working till it finds a valid solution.
So this is the backtracking approach that we will employ to solve the Sudoku solver problem.