1
00:00:00,470 --> 00:00:02,540
Hey there and welcome back.

2
00:00:02,840 --> 00:00:09,890
In this section, let's get started with another algorithmic approach called backtracking.

3
00:00:09,920 --> 00:00:13,790
These are the six topics that we will discuss about this.

4
00:00:13,790 --> 00:00:19,820
And after we are done with this, let's go ahead and take a look at some interesting coding interview

5
00:00:19,820 --> 00:00:20,600
questions.

6
00:00:20,600 --> 00:00:27,230
We'll prepare this topic so thoroughly that you will be able to solve any coding interview question

7
00:00:27,230 --> 00:00:29,060
that deals with backtracking.

8
00:00:29,060 --> 00:00:30,740
So let's get started.

9
00:00:30,740 --> 00:00:36,350
The first question which we have over here is what is backtracking for this?

10
00:00:36,350 --> 00:00:40,580
Let's take an example to first develop an intuition about this.

11
00:00:40,580 --> 00:00:46,040
And after that we'll take a more theoretical view about what backtracking actually is.

12
00:00:46,040 --> 00:00:48,830
So over here this is a Sudoku board.

13
00:00:48,830 --> 00:00:52,400
And this I'm sure is a puzzle that you are well aware of.

14
00:00:52,400 --> 00:00:59,150
But quickly talking about the rules that are involved in a Sudoku board, you have to fill the empty

15
00:00:59,180 --> 00:01:01,760
spaces with numbers from 1 to 9.

16
00:01:01,760 --> 00:01:07,700
So you have one, two, three, four, five, six, seven, eight and nine.

17
00:01:07,700 --> 00:01:12,140
And the rules are that firstly in one box.

18
00:01:12,140 --> 00:01:17,030
So you can see that you have one box over here, one box over here, one box over here.

19
00:01:17,030 --> 00:01:21,590
So in this manner there are a total of nine boxes in this Sudoku board.

20
00:01:21,590 --> 00:01:26,360
And in each board you need to fill all these nine numbers.

21
00:01:26,360 --> 00:01:29,210
And you can fill each number only once.

22
00:01:29,210 --> 00:01:31,490
So for example you have a one over here.

23
00:01:31,490 --> 00:01:35,180
So you cannot fill one in these three empty spaces.

24
00:01:35,180 --> 00:01:36,800
So that is rule number one.

25
00:01:36,800 --> 00:01:42,200
The second rule is that this is also applicable for every row.

26
00:01:42,200 --> 00:01:46,820
So that means that in one row notice that you have nine spaces.

27
00:01:46,820 --> 00:01:51,080
And you can fill only these nine numbers once in a row.

28
00:01:51,080 --> 00:01:52,850
So again you have one over here.

29
00:01:52,850 --> 00:01:57,440
So you cannot fill one in any of these other empty spaces.

30
00:01:57,440 --> 00:01:59,060
So that is rule number two.

31
00:01:59,060 --> 00:02:03,860
And rule number three is that the same is true for every column as well.

32
00:02:03,860 --> 00:02:08,540
So for example in this column notice that you have nine spaces.

33
00:02:08,540 --> 00:02:14,090
And you can fill each of these nine numbers only once over here.

34
00:02:14,090 --> 00:02:17,300
So for example you have nine already filled over here.

35
00:02:17,300 --> 00:02:22,040
So none of these empty spaces can be filled with nine.

36
00:02:22,040 --> 00:02:27,530
So these are the rules about the Sudoku board or the Sudoku puzzle.

37
00:02:27,530 --> 00:02:33,710
Now let's use this and try to think about what backtracking is now over here.

38
00:02:33,710 --> 00:02:37,040
Let's go ahead and try to solve this Sudoku board.

39
00:02:37,040 --> 00:02:39,560
So over here we have an empty space.

40
00:02:40,310 --> 00:02:48,620
And again as we have discussed, the possibilities are one, 234567, eight nine.

41
00:02:48,620 --> 00:02:54,530
And among these let's eliminate whatever is not allowed based on the three rules that we discussed.

42
00:02:54,530 --> 00:02:57,560
So first let's take a look at this box over here.

43
00:02:57,560 --> 00:03:00,890
So we already have a nine and hence we can eliminate it.

44
00:03:00,920 --> 00:03:02,930
We cannot fill nine again over here.

45
00:03:02,930 --> 00:03:05,480
Similarly we have seven and four.

46
00:03:05,480 --> 00:03:07,370
So let's eliminate that as well.

47
00:03:07,370 --> 00:03:10,430
And I have six one and two.

48
00:03:10,430 --> 00:03:12,500
So let's eliminate that as well.

49
00:03:12,500 --> 00:03:15,380
And I'm left with three five and eight.

50
00:03:15,380 --> 00:03:21,530
Now let's take a look at this row over here I have nine which I've already eliminated I have six I have

51
00:03:21,530 --> 00:03:22,790
already eliminated six.

52
00:03:22,790 --> 00:03:24,620
And I have one and four.

53
00:03:24,620 --> 00:03:27,230
And I've already eliminated one and four as well.

54
00:03:27,230 --> 00:03:30,800
So there is nothing more to be eliminated over here based on the row.

55
00:03:30,800 --> 00:03:33,560
And then let's take a look at the column over here.

56
00:03:33,860 --> 00:03:37,850
So in this column notice that I have nine four and six.

57
00:03:37,850 --> 00:03:40,670
So these are also already eliminated.

58
00:03:40,670 --> 00:03:42,650
So there's nothing more to eliminate.

59
00:03:42,650 --> 00:03:50,210
And you can see that I am left with three values which can be filled over here.

60
00:03:50,210 --> 00:03:54,170
And the values are three five and eight.

61
00:03:54,800 --> 00:03:55,430
All right.

62
00:03:55,430 --> 00:04:01,520
So I've identified that over here I can fill either three 5 or 8.

63
00:04:01,520 --> 00:04:04,730
Now let's go ahead and fill three over here.

64
00:04:05,400 --> 00:04:13,110
So I filled three over here and after I'm done with that, I proceed and try to fill the next position,

65
00:04:13,110 --> 00:04:14,010
which is empty.

66
00:04:14,010 --> 00:04:23,190
But again, as I go on in this manner, notice that for this particular box over here, the second box,

67
00:04:23,190 --> 00:04:30,510
I cannot fill three over here because this empty space cannot be filled with three, because three is

68
00:04:30,510 --> 00:04:32,250
already there in this row.

69
00:04:32,250 --> 00:04:38,970
Similarly, I cannot fill three in this empty space over here, which is again in box number two, because

70
00:04:38,970 --> 00:04:41,700
three is already there in this column.

71
00:04:41,850 --> 00:04:50,250
Therefore, three has to be filled in one of these two positions when it comes to box number two.

72
00:04:50,760 --> 00:04:51,210
All right.

73
00:04:51,210 --> 00:04:54,750
So one of these two positions has to be three.

74
00:04:54,750 --> 00:04:57,780
But again over here we did fill three.

75
00:04:57,780 --> 00:05:04,770
So if we fill three over here we cannot fill three in these two places because it's the same row.

76
00:05:04,770 --> 00:05:13,110
Now because of this we can understand that after filling in three over here, there is no point in continuing

77
00:05:13,110 --> 00:05:19,260
with solving this particular board where three is already filled over here, because we will not be

78
00:05:19,260 --> 00:05:21,450
able to arrive at the solution.

79
00:05:21,450 --> 00:05:22,320
And why is that?

80
00:05:22,320 --> 00:05:24,300
So again, quickly revising.

81
00:05:24,300 --> 00:05:28,170
We need to fill all the numbers from 1 to 9 in every box.

82
00:05:28,170 --> 00:05:30,570
And three is one of these numbers.

83
00:05:30,570 --> 00:05:30,900
Right.

84
00:05:30,900 --> 00:05:36,090
And we have seen that three cannot be filled in this box over here or over here.

85
00:05:36,090 --> 00:05:42,060
And then only these two spaces are empty and three will not be able will not be able to fill three over

86
00:05:42,060 --> 00:05:44,610
here as well because we have filled three over here.

87
00:05:45,030 --> 00:05:53,670
So there's no point in continuing to solve this board over here with having three at this place.

88
00:05:53,670 --> 00:05:58,200
So what do we do now to solve this board?

89
00:05:58,230 --> 00:06:03,630
The way we think about this is that what if I did not fill three over here.

90
00:06:04,050 --> 00:06:10,710
So if I did not fill three over here, I would be able to fill something else over here and go ahead

91
00:06:10,710 --> 00:06:12,240
and solve the problem.

92
00:06:12,240 --> 00:06:15,990
Now this is what we call backtracking.

93
00:06:16,810 --> 00:06:21,580
So as part of backtracking, we come back over here.

94
00:06:22,390 --> 00:06:25,300
And we remove this three.

95
00:06:25,420 --> 00:06:26,110
Okay.

96
00:06:26,110 --> 00:06:28,870
Now there are two things that I've written over here.

97
00:06:28,870 --> 00:06:35,170
One is that coming back to this position from maybe over here or over here, wherever we were, and

98
00:06:35,170 --> 00:06:37,840
we identified that will not be able to proceed.

99
00:06:37,840 --> 00:06:42,040
So from that position coming back to this position over here.

100
00:06:42,040 --> 00:06:44,290
So that's the first thing written over here.

101
00:06:44,290 --> 00:06:48,430
And then the second thing which is written over here is remove three.

102
00:06:48,610 --> 00:06:54,910
Now this part over here, which is the coming back, is taken care of by recursion.

103
00:06:54,910 --> 00:07:01,150
Because in a recursive function, when we can't go deeper, it returns and we can come back.

104
00:07:01,150 --> 00:07:03,370
So that is handled by simple recursion.

105
00:07:03,370 --> 00:07:07,930
But then backtracking is this part over here which is remove three.

106
00:07:09,300 --> 00:07:09,750
All right.

107
00:07:09,750 --> 00:07:16,410
So backtracking is is again, as we have discussed, backtracking is a recursive, uh, algorithmic

108
00:07:16,410 --> 00:07:17,010
approach.

109
00:07:17,010 --> 00:07:23,610
And as part of backtracking, what happens is once we come back over here, we remove this tree and

110
00:07:23,610 --> 00:07:25,470
we try to fill something else over here.

111
00:07:25,470 --> 00:07:27,630
So let's go ahead and proceed.

112
00:07:27,630 --> 00:07:33,330
So we remove the three, and we know that we can fill this place with three, five and eight.

113
00:07:33,330 --> 00:07:34,860
And three did not work out.

114
00:07:34,860 --> 00:07:37,710
So we go ahead and try the same with five.

115
00:07:37,710 --> 00:07:39,510
And we proceed in this manner.

116
00:07:39,510 --> 00:07:42,960
So this over here is what backtracking is.

117
00:07:42,960 --> 00:07:49,230
And we have just used an example to demonstrate and to develop an intuition of what backtracking is.

118
00:07:49,830 --> 00:07:59,310
So basically backtracking is an algorithmic approach to find solutions to problems that involve many

119
00:07:59,310 --> 00:08:00,510
possible paths.

120
00:08:00,510 --> 00:08:04,440
So for example, over here we had the path of filling with three.

121
00:08:04,440 --> 00:08:07,140
And there was another path of filling five over here.

122
00:08:07,140 --> 00:08:09,840
And there's another path of filling eight over here, etc..

123
00:08:09,840 --> 00:08:10,200
Right.

124
00:08:10,200 --> 00:08:14,850
In fact, you could also think of that there are nine paths over here one, two, three, four, five,

125
00:08:14,850 --> 00:08:16,230
six, seven, eight and nine.

126
00:08:16,230 --> 00:08:20,700
And then whatever is not working, we don't proceed in that manner.

127
00:08:20,700 --> 00:08:21,270
All right.

128
00:08:21,270 --> 00:08:28,710
So backtracking is this algorithmic approach to find solutions to problems that involve many possible

129
00:08:28,710 --> 00:08:29,400
paths.

130
00:08:29,400 --> 00:08:34,230
And notice that solutions are built step by step.

131
00:08:34,230 --> 00:08:36,930
And this is handled through recursion.

132
00:08:37,400 --> 00:08:38,870
So what does that mean?

133
00:08:38,870 --> 00:08:43,280
We fill this empty space and then we proceed to the next empty space.

134
00:08:43,280 --> 00:08:47,540
So we are building the solution step by step using recursion.

135
00:08:47,540 --> 00:08:55,730
And if a path does not lead to a solution because it violates some constraints, as we have seen over

136
00:08:55,730 --> 00:08:55,940
here.

137
00:08:55,940 --> 00:08:56,150
Right.

138
00:08:56,150 --> 00:09:03,140
So it was violating a constraint in if that occurs then that particular path is abandoned.

139
00:09:03,140 --> 00:09:04,340
So that's what we did over here.

140
00:09:04,340 --> 00:09:04,580
Right.

141
00:09:04,580 --> 00:09:10,670
So we came back and we removed the three which indicates that we removed that particular path.

142
00:09:10,940 --> 00:09:14,390
So this is what backtracking entails.

143
00:09:14,390 --> 00:09:18,590
So basically backtracking is controlled recursion.

144
00:09:18,740 --> 00:09:24,950
And in backtracking we make changes in place using pass by reference.

145
00:09:24,950 --> 00:09:32,510
Or in other words we can say that changes or modifications to the state of the problem are made in place.

146
00:09:32,510 --> 00:09:34,970
Now again let's try to think about this.

147
00:09:35,120 --> 00:09:38,180
So why is backtracking controlled recursion?

148
00:09:38,180 --> 00:09:44,930
Notice over here, when we came to this place, we identified that there was no point in continuing

149
00:09:44,930 --> 00:09:47,120
that path of filling three over here.

150
00:09:47,120 --> 00:09:50,030
So we pruned or abandoned that path.

151
00:09:50,030 --> 00:09:53,450
That's why we can call backtracking controlled recursion.

152
00:09:53,450 --> 00:09:57,950
And we are also making changes in place.

153
00:09:57,950 --> 00:10:00,710
Or we are modifying the state of the problem in place.

154
00:10:00,710 --> 00:10:03,170
So that's why we came back over here.

155
00:10:03,170 --> 00:10:07,580
We removed the three and then we went ahead and tried to fill five over here.

156
00:10:07,580 --> 00:10:11,540
Notice that we are making changes to the state of the problem in place.

157
00:10:11,540 --> 00:10:18,320
Or in other words, we are not making a copy of this to solve the Sudoku board.

158
00:10:18,350 --> 00:10:24,260
Now again, for example, think that this over here, the board over here was given to us in the form

159
00:10:24,260 --> 00:10:24,950
of an array.

160
00:10:25,190 --> 00:10:28,100
Maybe it could be a two dimensional array.

161
00:10:28,610 --> 00:10:35,180
And you have every row probably over here you have nine and then you have an empty space.

162
00:10:35,180 --> 00:10:36,980
So let's say it's given as a dot.

163
00:10:36,980 --> 00:10:38,810
And then you have a six.

164
00:10:38,810 --> 00:10:41,870
And then you have ..1.4..

165
00:10:41,870 --> 00:10:44,180
So that could be one row.

166
00:10:44,180 --> 00:10:45,860
And then you have the next row etc..

167
00:10:45,860 --> 00:10:48,440
So an array of arrays or a 2D array.

168
00:10:48,710 --> 00:10:52,820
So imagine that the input was given in this manner.

169
00:10:52,820 --> 00:10:59,540
Now over here when we say that we are making changes to the state of the problem in place, what we

170
00:10:59,540 --> 00:11:06,260
mean is that when we try to solve this question, we are not going to make a copy of the array and try

171
00:11:06,260 --> 00:11:11,750
to fill values and check whether it's working out or not, but rather we are going to use the input

172
00:11:11,750 --> 00:11:16,730
array itself, and we're just going to over here instead of the dot, we will replace it with three.

173
00:11:16,730 --> 00:11:20,690
And when we see that it does not work we come back, we remove the three.

174
00:11:20,690 --> 00:11:26,420
And then again we place a dot over here and we try the next combination, which is probably a five.

175
00:11:26,420 --> 00:11:29,360
So in backtracking remember two things.

176
00:11:29,360 --> 00:11:33,140
One, we abandoned paths that don't lead to the solution.

177
00:11:33,140 --> 00:11:35,990
So that's why backtracking is controlled recursion.

178
00:11:35,990 --> 00:11:39,680
And secondly we modify the state of the problem in place.

179
00:11:40,160 --> 00:11:45,380
We don't create new copies but rather we make changes in place.

180
00:11:45,380 --> 00:11:50,600
And that's also good for the space complexity when it comes to solving questions.

181
00:11:50,600 --> 00:11:57,470
So again, when we say that we abandon or prune paths that don't work out, what we mean is that we

182
00:11:57,470 --> 00:11:58,580
revert the changes.

183
00:11:58,580 --> 00:12:01,970
So over here notice that we reverted the change.

184
00:12:01,970 --> 00:12:07,250
The change was that we filled three over here and we came back and we reverted that change.

185
00:12:07,250 --> 00:12:08,750
We again made it empty.

186
00:12:08,750 --> 00:12:11,420
And we proceed and try another combination.

187
00:12:11,420 --> 00:12:13,760
So we have understood what backtracking is.

188
00:12:13,760 --> 00:12:19,400
In simple terms, it's just controlled recursion where changes are made in place.