1
00:00:00,110 --> 00:00:03,890
Let's now get into the code for solving the Sudoku solver question.

2
00:00:03,890 --> 00:00:08,660
Now over here we are given this function solve Sudoku and we are given a board.

3
00:00:08,660 --> 00:00:09,020
Okay.

4
00:00:09,020 --> 00:00:15,410
Now notice that it's mentioned over here that the function modifies the board in place to present the

5
00:00:15,410 --> 00:00:16,100
solution.

6
00:00:16,100 --> 00:00:18,170
Hence there is no need to return the board.

7
00:00:18,170 --> 00:00:21,590
Okay, so this means that you don't need to return anything from this function.

8
00:00:21,590 --> 00:00:23,930
You just need to complete filling the board.

9
00:00:23,930 --> 00:00:25,340
So that is the task at hand.

10
00:00:25,340 --> 00:00:25,790
All right.

11
00:00:25,790 --> 00:00:30,080
Now first let's take a look at the skeleton of the solution which we have over here.

12
00:00:30,080 --> 00:00:32,060
And then we'll go into the details.

13
00:00:32,060 --> 00:00:36,650
So as we've discussed in the previous video this is a recursive way of solving this question.

14
00:00:36,650 --> 00:00:41,810
And for this we are using a helper function which I've just named helper itself over here.

15
00:00:41,810 --> 00:00:42,440
Okay.

16
00:00:42,440 --> 00:00:45,830
And notice that we also have an is valid function over here.

17
00:00:45,830 --> 00:00:51,680
We will be using this function to check whether we can place a particular number at a particular cell

18
00:00:51,680 --> 00:00:52,220
in the board.

19
00:00:52,220 --> 00:00:52,670
Okay.

20
00:00:52,670 --> 00:00:58,070
And this helper function will keep calling itself recursively to complete filling the board.

21
00:00:58,070 --> 00:01:02,000
And also notice that we have called the helper function for the first time over here.

22
00:01:02,000 --> 00:01:04,940
So this is the skeleton of the solution that we have over here.

23
00:01:04,940 --> 00:01:10,430
So again we just have two functions over here which is the is valid function and the helper function

24
00:01:10,430 --> 00:01:10,850
over here.

25
00:01:10,850 --> 00:01:14,480
Now first let's take a look at the helper function in detail.

26
00:01:14,480 --> 00:01:17,120
And then we'll come back to the is valid function.

27
00:01:17,120 --> 00:01:22,490
Now in the helper function the first thing that we are trying to do over here is we are trying to identify

28
00:01:22,490 --> 00:01:24,710
the next empty cell okay.

29
00:01:24,710 --> 00:01:26,630
And for that we have two for loops.

30
00:01:26,630 --> 00:01:32,150
So in the first for loop we go from the row number zero up to row number eight okay.

31
00:01:32,150 --> 00:01:35,810
And in the second for loop we go from column zero up to column eight.

32
00:01:35,810 --> 00:01:40,040
So we are actually going systematically through each cell in the board.

33
00:01:40,040 --> 00:01:43,910
And our aim is to identify the next empty cell.

34
00:01:51,580 --> 00:01:55,870
And in the question, it's mentioned that an empty cell would have just a dot.

35
00:01:55,870 --> 00:02:02,740
So if the row column combination at a particular instance is equal to this particular dot, it would

36
00:02:02,740 --> 00:02:04,990
mean that we have identified an empty cell.

37
00:02:04,990 --> 00:02:10,870
And then our next task is to identify what number we can fill in that particular empty cell.

38
00:02:10,870 --> 00:02:13,660
And again for this we have another for loop over here.

39
00:02:13,660 --> 00:02:15,610
Let me again change the color of my pen.

40
00:02:15,610 --> 00:02:17,650
So we have another for loop over here.

41
00:02:17,650 --> 00:02:24,040
And using this for loop num takes the values from one up to nine okay.

42
00:02:24,040 --> 00:02:27,880
And we are going to convert the number to a string.

43
00:02:27,880 --> 00:02:33,460
And then over here we are going to use the is valid function to check whether we can actually place

44
00:02:33,460 --> 00:02:37,540
this particular number at the particular position in the board okay.

45
00:02:37,540 --> 00:02:40,150
At the row column combination in the board.

46
00:02:40,150 --> 00:02:42,280
And again we'll come to the details of this.

47
00:02:42,280 --> 00:02:44,680
But let's say this returns true.

48
00:02:44,680 --> 00:02:50,890
So if this returns true then we will just go ahead and fill that particular number in the board at that

49
00:02:50,890 --> 00:02:53,140
particular row column combination okay.

50
00:02:53,140 --> 00:02:59,470
And once we have done that we again recursively call the helper function to go ahead and fill the next

51
00:02:59,470 --> 00:03:00,160
empty cell.

52
00:03:00,160 --> 00:03:00,580
All right.

53
00:03:00,610 --> 00:03:03,430
Now let's make a few interesting observations over here.

54
00:03:03,430 --> 00:03:06,520
Notice that you have a return true over here okay.

55
00:03:06,520 --> 00:03:08,230
Now when would this be triggered.

56
00:03:08,230 --> 00:03:13,810
Notice that this over here you would reach this line of code if you come out of these two for loops

57
00:03:13,810 --> 00:03:14,110
okay.

58
00:03:14,110 --> 00:03:16,660
So again typically if you come out of this for loop.

59
00:03:16,660 --> 00:03:22,990
So if you come out of this for loop and you reach over here, it would mean that you were not able to

60
00:03:22,990 --> 00:03:25,180
identify any empty cell.

61
00:03:25,180 --> 00:03:25,510
Okay.

62
00:03:25,510 --> 00:03:30,040
So this over here would return true if the board is completely filled.

63
00:03:34,320 --> 00:03:34,950
Okay.

64
00:03:34,950 --> 00:03:38,520
And notice over here also you have a return.

65
00:03:38,520 --> 00:03:38,940
True.

66
00:03:38,970 --> 00:03:44,850
Now we have discussed that once you fill the particular number which returned true from the is valid

67
00:03:44,850 --> 00:03:50,100
function in the particular row column combination which happens in this line of code.

68
00:03:50,100 --> 00:03:55,320
So once you have done that we recursively call the helper function to fill the next empty cell.

69
00:03:55,320 --> 00:03:58,140
But then why do we have a return true over here.

70
00:03:58,140 --> 00:03:59,520
Let's try to understand that.

71
00:03:59,520 --> 00:04:05,160
Now for this let's take the example where let's say we just have three cells to be filled in the board.

72
00:04:05,160 --> 00:04:05,490
Okay.

73
00:04:05,490 --> 00:04:09,930
So there are just three empty cells and everything else is already filled in the board.

74
00:04:09,930 --> 00:04:15,390
So the way that this algorithm would go ahead and fill these cells is that first it would go ahead and

75
00:04:15,390 --> 00:04:16,260
fill this cell.

76
00:04:16,260 --> 00:04:19,200
Then it would make a recursive call to fill this cell.

77
00:04:19,200 --> 00:04:22,350
And then another recursive call would be made to fill this cell.

78
00:04:22,350 --> 00:04:28,200
And then again we would make one more recursive call, at which point this over here would be reached,

79
00:04:28,200 --> 00:04:31,500
because we see that there is nothing empty and we would return true.

80
00:04:31,500 --> 00:04:31,860
Okay.

81
00:04:31,860 --> 00:04:34,050
So we would get back true over here.

82
00:04:34,050 --> 00:04:36,660
So this over here would return true over here.

83
00:04:36,660 --> 00:04:43,290
And again, notice this happened over here because after we filled this particular value over here,

84
00:04:43,290 --> 00:04:46,740
which is at this line of code, we made a recursive call, okay.

85
00:04:46,740 --> 00:04:49,530
And we come back over here and we get true.

86
00:04:49,530 --> 00:04:49,830
Okay.

87
00:04:49,830 --> 00:04:53,580
Now because at this point the board is already filled.

88
00:04:53,580 --> 00:04:56,160
We don't need to go any further deeper.

89
00:04:56,160 --> 00:04:59,370
And we can just return from here to this place as well.

90
00:04:59,370 --> 00:04:59,760
Okay.

91
00:04:59,760 --> 00:05:01,830
And for that we need this return.

92
00:05:01,830 --> 00:05:02,100
True.

93
00:05:02,100 --> 00:05:08,820
So this over here, if helper board, this over here would be true when the board is full and then we

94
00:05:08,820 --> 00:05:11,820
propagate it back or upwards through returning.

95
00:05:11,820 --> 00:05:12,450
True over here.

96
00:05:12,450 --> 00:05:14,520
So this over here would return true.

97
00:05:14,520 --> 00:05:19,860
And we come over here and again remember this over here got filled through a recursive call which was

98
00:05:19,860 --> 00:05:21,480
triggered at this instance.

99
00:05:21,480 --> 00:05:24,960
And at that point the code reached over here right where this call happened.

100
00:05:24,960 --> 00:05:27,600
So therefore when we return true we come over here.

101
00:05:27,600 --> 00:05:30,510
And because again we see we got true over here.

102
00:05:30,510 --> 00:05:32,400
This also returns true.

103
00:05:32,400 --> 00:05:36,660
And we come over here and finally this also returns true okay.

104
00:05:36,660 --> 00:05:40,200
So that's why over here also we need to return true.

105
00:05:40,200 --> 00:05:45,000
And then the final interesting thing to notice over here is we have returned false over here.

106
00:05:45,000 --> 00:05:46,860
Now when would this be triggered.

107
00:05:46,860 --> 00:05:48,570
Let's try to think about that.

108
00:05:48,570 --> 00:05:56,160
So notice that this return false would happen if you come out of this for loop, which means that there

109
00:05:56,160 --> 00:06:01,140
is no number which can be filled at that particular row column combination.

110
00:06:01,140 --> 00:06:01,440
Okay.

111
00:06:01,440 --> 00:06:07,740
So is valid returns false for all the possible numbers at that particular cell in the board.

112
00:06:07,740 --> 00:06:11,250
And in that case we would come over here and we would return false.

113
00:06:11,250 --> 00:06:17,400
Now what is the significance of this again remember we would be returning false to a recursive call.

114
00:06:17,400 --> 00:06:20,460
So this false would come over here okay.

115
00:06:20,460 --> 00:06:27,570
And when we get false over here it means that the way that we have filled the board so far is not correct.

116
00:06:27,570 --> 00:06:31,470
And we have to backtrack and we have to try a different combination.

117
00:06:31,470 --> 00:06:38,820
So when we get false over here, we don't return true, but rather we come over here and we backtrack.

118
00:06:38,820 --> 00:06:40,470
So this is the backtracking step.

119
00:06:41,730 --> 00:06:49,020
So what we are doing over here is whatever got filled in this line of code is being changed or reverted

120
00:06:49,020 --> 00:06:50,430
back to an empty cell.

121
00:06:50,430 --> 00:06:56,790
And then we again come over here and we try a different number to fill at that particular cell in the

122
00:06:56,790 --> 00:06:57,150
board.

123
00:06:57,150 --> 00:06:57,450
Okay.

124
00:06:57,450 --> 00:06:59,820
So that's how this solution works.

125
00:06:59,820 --> 00:07:01,830
Now let's quickly review what we have discussed.

126
00:07:01,830 --> 00:07:03,510
Let me clean this up a little bit.

127
00:07:03,900 --> 00:07:10,170
So what we have discussed is in the helper function over here first we try to identify the next empty

128
00:07:10,170 --> 00:07:10,650
cell.

129
00:07:10,650 --> 00:07:16,410
And then once we have identified an empty cell we go through the numbers from 1 to 9.

130
00:07:16,410 --> 00:07:22,290
And we are going to check whether we can fill that particular number at the particular cell in the board.

131
00:07:22,290 --> 00:07:23,550
So that's what we're doing over here.

132
00:07:23,550 --> 00:07:25,260
Using the is valid function.

133
00:07:25,260 --> 00:07:26,640
And to the is valid function.

134
00:07:26,640 --> 00:07:30,240
We are passing the board the row the column and the particular car okay.

135
00:07:30,240 --> 00:07:32,130
Car at this point is the number.

136
00:07:32,130 --> 00:07:34,440
And we just converted it into a character.

137
00:07:34,440 --> 00:07:40,620
Now if this returns true then we go ahead and fill that particular number at that particular cell in

138
00:07:40,620 --> 00:07:41,070
the board.

139
00:07:41,070 --> 00:07:45,480
And we recursively call the helper function to fill the next empty cell.

140
00:07:45,480 --> 00:07:50,010
Now this call over here can either return true or it can return false.

141
00:07:50,010 --> 00:07:55,380
Now, the first time that we could get true over here is when this is triggered.

142
00:07:55,380 --> 00:07:58,320
Which means that the board has been completely filled.

143
00:07:58,320 --> 00:08:03,480
The reason for that is that this over here would be triggered when we are not able to identify any empty

144
00:08:03,480 --> 00:08:06,600
cell and we come out of the for loop and we come over here.

145
00:08:06,600 --> 00:08:12,390
So that's the first time we could get true over here at this place in a particular instance of a recursive

146
00:08:12,390 --> 00:08:12,840
call.

147
00:08:12,840 --> 00:08:16,170
And we can also get true when it is propagated back.

148
00:08:16,170 --> 00:08:16,380
Right.

149
00:08:16,380 --> 00:08:19,770
We have seen this is the case where it was returned for the first time.

150
00:08:19,770 --> 00:08:20,070
True.

151
00:08:20,070 --> 00:08:22,710
And then it gets propagated back in this manner.

152
00:08:22,710 --> 00:08:25,710
And in that case also this over here returns true.

153
00:08:25,710 --> 00:08:26,160
Okay.

154
00:08:26,160 --> 00:08:32,010
And we've also seen that this over here would return false if this over here is triggered, if this

155
00:08:32,010 --> 00:08:32,640
line of code is.

156
00:08:32,740 --> 00:08:38,740
Triggered, and this would be triggered when we have tried all the numbers from 1 to 9 to be filled

157
00:08:38,740 --> 00:08:41,470
at a particular cell, but nothing returned.

158
00:08:41,470 --> 00:08:47,920
True or the is valid function did not return true for all the numbers from 1 to 9 for that particular

159
00:08:47,920 --> 00:08:53,380
row and column combination, which means that the way that we have filled the board so far is not correct,

160
00:08:53,380 --> 00:08:54,850
and we have to backtrack.

161
00:08:54,850 --> 00:08:58,690
So at this point we come over here and we return false.

162
00:08:58,690 --> 00:09:04,780
And when we get false over here, we don't get to this line of code, but rather we come over here and

163
00:09:04,780 --> 00:09:05,530
we backtrack.

164
00:09:05,530 --> 00:09:10,960
And this is the backtracking step in which we are reverting the change that we have made in this line

165
00:09:10,990 --> 00:09:11,440
of code.

166
00:09:11,440 --> 00:09:16,570
We have filled a particular number at that particular row column combination in the board over here.

167
00:09:16,570 --> 00:09:18,280
And that's being reverted over here.

168
00:09:18,280 --> 00:09:24,520
And we again come over here and we try another number to be filled at that particular cell in the board.

169
00:09:24,520 --> 00:09:27,340
So this is how the helper function works.

170
00:09:27,340 --> 00:09:30,670
Now all that remains for us to be discussed is the is valid function.

171
00:09:30,670 --> 00:09:32,770
So let's just quickly discuss that as well.

172
00:09:34,640 --> 00:09:41,720
Now, as we've discussed in the method video, the is valid function just has to check whether the particular

173
00:09:41,720 --> 00:09:47,660
number at hand can be filled at the particular cell that we are considering on the board, and for that

174
00:09:47,660 --> 00:09:49,100
we have to do three checks.

175
00:09:49,100 --> 00:09:54,350
We have to do the row check, we have to do the column check, and we have to do the box check.

176
00:09:54,350 --> 00:09:57,290
Now the row and column check is pretty straightforward.

177
00:09:57,290 --> 00:10:02,900
So you just need to keep one constant and then change the other value from zero up to eight.

178
00:10:02,900 --> 00:10:05,690
So over here we have board x and call.

179
00:10:05,690 --> 00:10:10,430
In which case you're keeping the column constant and you're changing the row value.

180
00:10:10,430 --> 00:10:15,290
So when you're keeping the column constant and you're changing the row value you're actually checking

181
00:10:15,290 --> 00:10:16,370
the column okay.

182
00:10:16,370 --> 00:10:17,870
So this is the column check.

183
00:10:18,320 --> 00:10:20,870
And this over here keeps the row constant.

184
00:10:20,870 --> 00:10:22,370
And you're changing the column.

185
00:10:22,370 --> 00:10:24,590
So this is the row check okay.

186
00:10:24,590 --> 00:10:29,060
So over here you are checking whether the particular number that we are considering has already been

187
00:10:29,060 --> 00:10:30,290
filled in the column.

188
00:10:30,290 --> 00:10:35,480
And over here you're checking whether the number that we are considering has already been filled in

189
00:10:35,480 --> 00:10:35,900
the row.

190
00:10:35,900 --> 00:10:42,320
Now, if either of these is true, then we can return false, which means that the number has already

191
00:10:42,320 --> 00:10:45,230
been used in that particular column or row.

192
00:10:45,230 --> 00:10:50,450
And because of that, we cannot fill the number that we are considering at the particular position in

193
00:10:50,450 --> 00:10:51,020
the board.

194
00:10:51,020 --> 00:10:57,200
But if none of these return false, then we go ahead and do the box check, which is what we're doing

195
00:10:57,200 --> 00:10:57,710
over here.

196
00:10:57,710 --> 00:11:02,900
Now, we have discussed the logic for this in detail in the previous video, but over here let's just

197
00:11:02,900 --> 00:11:04,340
discuss the implementation.

198
00:11:04,340 --> 00:11:06,920
So we have two variables r and c.

199
00:11:06,920 --> 00:11:10,940
And r is equal to three into math dot floor row by three.

200
00:11:10,940 --> 00:11:13,760
So when you do that you are just taking the integer value.

201
00:11:13,760 --> 00:11:19,040
When you are dividing row by three and you're avoiding the decimals and you multiply that with three.

202
00:11:19,040 --> 00:11:22,850
And to that you add math dot floor x by three okay.

203
00:11:22,850 --> 00:11:27,950
And remember x is this value over here which iterates from 0 to 8.

204
00:11:27,950 --> 00:11:34,430
And in a similar manner c is equal to three into math dot floor called by three plus x percentage three.

205
00:11:34,430 --> 00:11:39,380
So again I'm not going into the details of this logic, which has already been discussed in detail in

206
00:11:39,380 --> 00:11:40,280
the previous video.

207
00:11:40,280 --> 00:11:48,020
But once we get R and C, we have seen that by using this formula, we can get all the row column combinations

208
00:11:48,020 --> 00:11:53,240
in the particular box that we are considering, and we are just checking whether the number at hand

209
00:11:53,270 --> 00:11:55,340
is already present in the box.

210
00:11:55,340 --> 00:12:00,410
Now, if we see that the number is there in the box, then we return false, which means that the number

211
00:12:00,410 --> 00:12:03,080
cannot be filled in the position that we are considering.

212
00:12:03,080 --> 00:12:06,560
But if we don't get false, then we would come over here.

213
00:12:06,560 --> 00:12:12,590
And if we reach this line of code, it means that the column check, the row check, and the box check

214
00:12:12,590 --> 00:12:13,370
has passed.

215
00:12:13,370 --> 00:12:18,890
And because of that, we can fill the number that we are considering at the particular position in the

216
00:12:18,890 --> 00:12:20,180
board that we are considering.

217
00:12:20,180 --> 00:12:23,270
So this is how we can write the is valid function.

218
00:12:23,270 --> 00:12:28,310
And we have discussed that we will be calling the is valid function over here whenever we are considering

219
00:12:28,310 --> 00:12:33,860
a particular number, and whenever we try to see whether we can fill that number at the particular row

220
00:12:33,860 --> 00:12:39,680
column combination, we call the is valid function and we pass to it the board, the row, the column,

221
00:12:39,680 --> 00:12:41,420
and the number that we are considering.

222
00:12:41,420 --> 00:12:47,750
And if we get true over here only, then we go ahead and fill that particular number at that particular

223
00:12:47,750 --> 00:12:49,850
row column combination in the board.

224
00:12:49,850 --> 00:12:53,120
So this is how we can solve the Sudoku solver question.

225
00:12:53,120 --> 00:12:57,530
Now let's go ahead and run this code and see if it's passing all the test cases.

226
00:12:59,030 --> 00:13:00,830
And you can see that it's working.

227
00:13:00,830 --> 00:13:05,810
And again you could make use of the user logs in case you are stuck somewhere and you need some help

228
00:13:05,810 --> 00:13:06,980
for debugging your code.

229
00:13:06,980 --> 00:13:12,470
Now again, because over here the input is a board, you could copy this and paste it on a notepad to

230
00:13:12,470 --> 00:13:14,750
visualize this in a better manner if required.