Hey there and welcome back.
In this section, let's get started with another algorithmic approach called backtracking.
These are the six topics that we will discuss about this.
And after we are done with this, let's go ahead and take a look at some interesting coding interview
questions.
We'll prepare this topic so thoroughly that you will be able to solve any coding interview question
that deals with backtracking.
So let's get started.
The first question which we have over here is what is backtracking for this?
Let's take an example to first develop an intuition about this.
And after that we'll take a more theoretical view about what backtracking actually is.
So over here this is a Sudoku board.
And this I'm sure is a puzzle that you are well aware of.
But quickly talking about the rules that are involved in a Sudoku board, you have to fill the empty
spaces with numbers from 1 to 9.
So you have one, two, three, four, five, six, seven, eight and nine.
And the rules are that firstly in one box.
So you can see that you have one box over here, one box over here, one box over here.
So in this manner there are a total of nine boxes in this Sudoku board.
And in each board you need to fill all these nine numbers.
And you can fill each number only once.
So for example you have a one over here.
So you cannot fill one in these three empty spaces.
So that is rule number one.
The second rule is that this is also applicable for every row.
So that means that in one row notice that you have nine spaces.
And you can fill only these nine numbers once in a row.
So again you have one over here.
So you cannot fill one in any of these other empty spaces.
So that is rule number two.
And rule number three is that the same is true for every column as well.
So for example in this column notice that you have nine spaces.
And you can fill each of these nine numbers only once over here.
So for example you have nine already filled over here.
So none of these empty spaces can be filled with nine.
So these are the rules about the Sudoku board or the Sudoku puzzle.
Now let's use this and try to think about what backtracking is now over here.
Let's go ahead and try to solve this Sudoku board.
So over here we have an empty space.
And again as we have discussed, the possibilities are one, 234567, eight nine.
And among these let's eliminate whatever is not allowed based on the three rules that we discussed.
So first let's take a look at this box over here.
So we already have a nine and hence we can eliminate it.
We cannot fill nine again over here.
Similarly we have seven and four.
So let's eliminate that as well.
And I have six one and two.
So let's eliminate that as well.
And I'm left with three five and eight.
Now let's take a look at this row over here I have nine which I've already eliminated I have six I have
already eliminated six.
And I have one and four.
And I've already eliminated one and four as well.
So there is nothing more to be eliminated over here based on the row.
And then let's take a look at the column over here.
So in this column notice that I have nine four and six.
So these are also already eliminated.
So there's nothing more to eliminate.
And you can see that I am left with three values which can be filled over here.
And the values are three five and eight.
All right.
So I've identified that over here I can fill either three 5 or 8.
Now let's go ahead and fill three over here.
So I filled three over here and after I'm done with that, I proceed and try to fill the next position,
which is empty.
But again, as I go on in this manner, notice that for this particular box over here, the second box,
I cannot fill three over here because this empty space cannot be filled with three, because three is
already there in this row.
Similarly, I cannot fill three in this empty space over here, which is again in box number two, because
three is already there in this column.
Therefore, three has to be filled in one of these two positions when it comes to box number two.
All right.
So one of these two positions has to be three.
But again over here we did fill three.
So if we fill three over here we cannot fill three in these two places because it's the same row.
Now because of this we can understand that after filling in three over here, there is no point in continuing
with solving this particular board where three is already filled over here, because we will not be
able to arrive at the solution.
And why is that?
So again, quickly revising.
We need to fill all the numbers from 1 to 9 in every box.
And three is one of these numbers.
Right.
And we have seen that three cannot be filled in this box over here or over here.
And then only these two spaces are empty and three will not be able will not be able to fill three over
here as well because we have filled three over here.
So there's no point in continuing to solve this board over here with having three at this place.
So what do we do now to solve this board?
The way we think about this is that what if I did not fill three over here.
So if I did not fill three over here, I would be able to fill something else over here and go ahead
and solve the problem.
Now this is what we call backtracking.
So as part of backtracking, we come back over here.
And we remove this three.
Okay.
Now there are two things that I've written over here.
One is that coming back to this position from maybe over here or over here, wherever we were, and
we identified that will not be able to proceed.
So from that position coming back to this position over here.
So that's the first thing written over here.
And then the second thing which is written over here is remove three.
Now this part over here, which is the coming back, is taken care of by recursion.
Because in a recursive function, when we can't go deeper, it returns and we can come back.
So that is handled by simple recursion.
But then backtracking is this part over here which is remove three.
All right.
So backtracking is is again, as we have discussed, backtracking is a recursive, uh, algorithmic
approach.
And as part of backtracking, what happens is once we come back over here, we remove this tree and
we try to fill something else over here.
So let's go ahead and proceed.
So we remove the three, and we know that we can fill this place with three, five and eight.
And three did not work out.
So we go ahead and try the same with five.
And we proceed in this manner.
So this over here is what backtracking is.
And we have just used an example to demonstrate and to develop an intuition of what backtracking is.
So basically backtracking is an algorithmic approach to find solutions to problems that involve many
possible paths.
So for example, over here we had the path of filling with three.
And there was another path of filling five over here.
And there's another path of filling eight over here, etc..
Right.
In fact, you could also think of that there are nine paths over here one, two, three, four, five,
six, seven, eight and nine.
And then whatever is not working, we don't proceed in that manner.
All right.
So backtracking is this algorithmic approach to find solutions to problems that involve many possible
paths.
And notice that solutions are built step by step.
And this is handled through recursion.
So what does that mean?
We fill this empty space and then we proceed to the next empty space.
So we are building the solution step by step using recursion.
And if a path does not lead to a solution because it violates some constraints, as we have seen over
here.
Right.
So it was violating a constraint in if that occurs then that particular path is abandoned.
So that's what we did over here.
Right.
So we came back and we removed the three which indicates that we removed that particular path.
So this is what backtracking entails.
So basically backtracking is controlled recursion.
And in backtracking we make changes in place using pass by reference.
Or in other words we can say that changes or modifications to the state of the problem are made in place.
Now again let's try to think about this.
So why is backtracking controlled recursion?
Notice over here, when we came to this place, we identified that there was no point in continuing
that path of filling three over here.
So we pruned or abandoned that path.
That's why we can call backtracking controlled recursion.
And we are also making changes in place.
Or we are modifying the state of the problem in place.
So that's why we came back over here.
We removed the three and then we went ahead and tried to fill five over here.
Notice that we are making changes to the state of the problem in place.
Or in other words, we are not making a copy of this to solve the Sudoku board.
Now again, for example, think that this over here, the board over here was given to us in the form
of an array.
Maybe it could be a two dimensional array.
And you have every row probably over here you have nine and then you have an empty space.
So let's say it's given as a dot.
And then you have a six.
And then you have ..1.4..
So that could be one row.
And then you have the next row etc..
So an array of arrays or a 2D array.
So imagine that the input was given in this manner.
Now over here when we say that we are making changes to the state of the problem in place, what we
mean is that when we try to solve this question, we are not going to make a copy of the array and try
to fill values and check whether it's working out or not, but rather we are going to use the input
array itself, and we're just going to over here instead of the dot, we will replace it with three.
And when we see that it does not work we come back, we remove the three.
And then again we place a dot over here and we try the next combination, which is probably a five.
So in backtracking remember two things.
One, we abandoned paths that don't lead to the solution.
So that's why backtracking is controlled recursion.
And secondly we modify the state of the problem in place.
We don't create new copies but rather we make changes in place.
And that's also good for the space complexity when it comes to solving questions.
So again, when we say that we abandon or prune paths that don't work out, what we mean is that we
revert the changes.
So over here notice that we reverted the change.
The change was that we filled three over here and we came back and we reverted that change.
We again made it empty.
And we proceed and try another combination.
So we have understood what backtracking is.
In simple terms, it's just controlled recursion where changes are made in place.