1
00:00:00,170 --> 00:00:07,040
In the previous video, we have understood the problem statement of the Sudoku solver question.

2
00:00:07,040 --> 00:00:10,700
Now let's try to think how we can solve this question.

3
00:00:10,700 --> 00:00:13,940
Now for this, let's take a sample board.

4
00:00:13,940 --> 00:00:16,700
Let's say this is the board that is given to us.

5
00:00:16,700 --> 00:00:21,170
And on this board notice there are various empty cells.

6
00:00:21,170 --> 00:00:24,680
So we need to identify what we can fill over here.

7
00:00:24,680 --> 00:00:29,060
And we have to do that in a way that the rules are satisfied.

8
00:00:29,060 --> 00:00:36,590
Now we can solve this recursively because we just need to fill one empty cell and then recursively go

9
00:00:36,590 --> 00:00:43,610
to the next empty cell and fill it and keep repeating this again and again till the whole board is filled.

10
00:00:43,610 --> 00:00:50,480
Now, the brute force way of solving this, or the most simple way of approaching this, would be to

11
00:00:50,480 --> 00:00:58,400
try all the numbers from 1 to 9 for every empty cell, and then from all of these boats that we come

12
00:00:58,400 --> 00:01:01,790
up, we would just need to identify the solution from them.

13
00:01:01,790 --> 00:01:09,830
Now, if we were to approach it in this manner, there would be nine to the power empty cells solutions.

14
00:01:09,830 --> 00:01:10,730
Now why is that?

15
00:01:10,730 --> 00:01:13,400
So let's say we just had two empty cells.

16
00:01:13,400 --> 00:01:16,220
So the first empty cell could be filled in nine ways.

17
00:01:16,220 --> 00:01:20,180
And the second empty cell can also be filled in nine ways.

18
00:01:20,180 --> 00:01:25,700
So there would be a total of nine into nine, which is nine square solutions.

19
00:01:25,700 --> 00:01:31,520
And then we would have to identify which is the correct solution from these 81 solutions.

20
00:01:31,520 --> 00:01:36,680
Now if there are x number of empty cells this would be nine to the power x.

21
00:01:36,680 --> 00:01:42,290
But then this obviously is not an efficient way of solving this.

22
00:01:42,290 --> 00:01:44,690
So can we do better.

23
00:01:44,690 --> 00:01:51,680
So let's think about this now a good way of solving this would be let's say we first fill this empty

24
00:01:51,680 --> 00:01:52,220
cell.

25
00:01:52,730 --> 00:01:57,020
Then let's say we proceed and fill this empty cell over here.

26
00:01:57,020 --> 00:02:05,240
And let's say in one of the scenarios, when we try to fill the next empty cell, we are not able to

27
00:02:05,240 --> 00:02:10,100
fill anything over here in a way that the three rules are satisfied.

28
00:02:10,100 --> 00:02:17,840
Now, this is because probably what we filled over here and over here are not the right values.

29
00:02:17,840 --> 00:02:26,300
So what we can do at this point is notice there is no point in going further down this branch or this

30
00:02:26,300 --> 00:02:31,490
path, because this will definitely not lead to a solution.

31
00:02:31,490 --> 00:02:34,370
So what we can do is we can backtrack.

32
00:02:35,270 --> 00:02:40,310
That means we can come back over here to the previous cell.

33
00:02:41,690 --> 00:02:43,280
Which is handled by recursion.

34
00:02:43,280 --> 00:02:49,100
And then whatever we filled over here will be removed, which is the backtracking step.

35
00:02:49,100 --> 00:02:54,380
And then we go ahead and try to fill this empty space with another value.

36
00:02:54,380 --> 00:02:56,480
So this is the backtracking approach.

37
00:02:56,480 --> 00:03:02,810
Now notice that this is much better than the previous approach that we've discussed, because any path

38
00:03:02,810 --> 00:03:05,990
that does not lead to a solution is pruned.

39
00:03:05,990 --> 00:03:12,980
And we keep working only with paths that can lead to a solution, which is what we ultimately need.

40
00:03:13,610 --> 00:03:15,410
So let's make some space over here.

41
00:03:15,410 --> 00:03:21,260
So again, one more interesting thing that you should remember over here is that backtracking is in

42
00:03:21,260 --> 00:03:23,810
fact a brute force algorithm.

43
00:03:23,810 --> 00:03:30,650
But the only thing is that it's better than just plain brute force, because any path that does not

44
00:03:30,650 --> 00:03:35,990
lead to a solution or any useless branch is immediately pruned.

45
00:03:36,750 --> 00:03:43,200
Now let's just walk through how the backtracking approach would solve this problem.

46
00:03:43,200 --> 00:03:43,800
Again.

47
00:03:43,800 --> 00:03:50,910
We have a board over here and we first identify the first empty cell, which is this cell over here.

48
00:03:50,910 --> 00:03:56,070
Now the choices that we have are one, two, three, etc. up to nine.

49
00:03:56,190 --> 00:03:58,890
So we start with the choice one.

50
00:03:58,890 --> 00:04:02,520
Can we fill one over here without violating the rules?

51
00:04:02,520 --> 00:04:05,700
Now notice over here one is there in this column.

52
00:04:05,700 --> 00:04:08,010
So we cannot fill one over here.

53
00:04:08,010 --> 00:04:09,600
So one is eliminated.

54
00:04:09,630 --> 00:04:11,550
Now what about two.

55
00:04:11,820 --> 00:04:14,520
Two is not there in this row.

56
00:04:14,820 --> 00:04:19,860
Two is not there in this column and two is not there in this box.

57
00:04:19,860 --> 00:04:24,360
So yes, two is a valid value that can be filled over here.

58
00:04:24,360 --> 00:04:27,300
So let's say we go ahead and fill two over here.

59
00:04:27,390 --> 00:04:32,520
And we proceed to the next empty cell which is this cell over here.

60
00:04:32,970 --> 00:04:38,610
Now again the choices that we have are one, two, three etc. up to nine.

61
00:04:38,610 --> 00:04:45,450
Now can we fill the value one notice over here we have one in this column, so we cannot fill the value

62
00:04:45,450 --> 00:04:45,960
one.

63
00:04:45,960 --> 00:04:47,280
What about two.

64
00:04:47,310 --> 00:04:49,800
Two is already there in this row.

65
00:04:49,800 --> 00:04:51,780
So two also cannot be filled.

66
00:04:51,780 --> 00:04:52,920
What about three.

67
00:04:52,920 --> 00:04:55,890
Notice three is there over here which is the same row.

68
00:04:55,890 --> 00:04:59,250
Hence three also is not valid to be filled over here.

69
00:04:59,250 --> 00:05:00,390
What about four?

70
00:05:00,390 --> 00:05:02,460
Four is there in this box.

71
00:05:02,460 --> 00:05:04,200
Notice that we have four over here.

72
00:05:04,200 --> 00:05:05,490
So four is out.

73
00:05:05,490 --> 00:05:06,600
What about five.

74
00:05:06,600 --> 00:05:09,210
Five is there over here which is the same column.

75
00:05:09,210 --> 00:05:10,470
So five is out.

76
00:05:10,470 --> 00:05:11,520
What about six.

77
00:05:11,520 --> 00:05:13,050
Six is there in this row.

78
00:05:13,050 --> 00:05:14,610
So six is also out.

79
00:05:14,610 --> 00:05:17,760
Seven is also out because seven is there in the same row.

80
00:05:17,760 --> 00:05:19,560
And what about eight.

81
00:05:20,040 --> 00:05:23,130
Notice that eight is not there in this column.

82
00:05:23,130 --> 00:05:27,600
Eight is not there in this row and eight is not there in this box.

83
00:05:27,600 --> 00:05:30,120
So yes, eight is a valid solution.

84
00:05:30,120 --> 00:05:32,940
So let's go ahead and fill eight over here.

85
00:05:32,940 --> 00:05:37,440
Now we proceed to the next empty cell which is this cell over here.

86
00:05:37,440 --> 00:05:41,730
Again the choices that we have are one, two, three etc. up to nine.

87
00:05:41,730 --> 00:05:44,730
Now can we fill one over here.

88
00:05:44,910 --> 00:05:51,210
Notice that one is not there in this row, nor is it there in this column, nor is it there in this

89
00:05:51,210 --> 00:05:51,720
box.

90
00:05:51,720 --> 00:05:54,330
So yes, one is a valid number.

91
00:05:54,330 --> 00:06:00,630
And we go ahead and fill one over here and we proceed to the next empty cell, which is this cell over

92
00:06:00,630 --> 00:06:01,050
here.

93
00:06:01,660 --> 00:06:05,740
Now again, the choices that we have are one up to nine.

94
00:06:05,740 --> 00:06:10,150
Now, we can't fill one over here because one is there in this row.

95
00:06:10,720 --> 00:06:16,240
Similarly, we can't fill two over here because notice two is there in this row.

96
00:06:16,240 --> 00:06:18,160
Three is also there in this row.

97
00:06:18,160 --> 00:06:20,980
And so one, two and three are out.

98
00:06:20,980 --> 00:06:23,860
What about four four is there in this column.

99
00:06:23,860 --> 00:06:27,400
Five is there in this column and six is there in this column.

100
00:06:27,400 --> 00:06:28,960
So four, five, six are out.

101
00:06:28,960 --> 00:06:30,100
What about seven.

102
00:06:30,100 --> 00:06:30,940
You have seven.

103
00:06:30,940 --> 00:06:33,940
Also in this column you have eight also in this column.

104
00:06:33,940 --> 00:06:35,890
So seven and eight are also out.

105
00:06:35,890 --> 00:06:37,480
And what about nine.

106
00:06:37,480 --> 00:06:39,070
Nine is there in this row.

107
00:06:39,070 --> 00:06:41,140
So again nine is also out.

108
00:06:41,140 --> 00:06:47,710
So notice over here we are not able to fill any valid number in this empty space.

109
00:06:47,710 --> 00:06:54,460
Now this has happened because one of these things that we previously filled is not correct.

110
00:06:54,460 --> 00:06:59,440
So at this point there is no point in proceeding down this path.

111
00:06:59,440 --> 00:07:00,760
And what is this path?

112
00:07:00,760 --> 00:07:05,110
This path means having these numbers filled over here.

113
00:07:05,110 --> 00:07:08,020
So there is no point in proceeding in this path.

114
00:07:08,020 --> 00:07:13,930
So what we do is because we can't feel anything over here, what we do is we backtrack.

115
00:07:14,630 --> 00:07:18,170
So we come back to this place over here.

116
00:07:19,000 --> 00:07:21,490
Which is what we do as part of backtracking.

117
00:07:21,490 --> 00:07:26,950
So we come back over here and again, the coming back is handled by recursion, but the backtracking

118
00:07:26,950 --> 00:07:30,730
step is that we remove the value that we filled over here.

119
00:07:30,730 --> 00:07:32,560
So we remove the one.

120
00:07:34,200 --> 00:07:34,740
All right.

121
00:07:34,740 --> 00:07:42,240
So we remove the one and then we proceed and try to identify the next possible value that could be filled

122
00:07:42,240 --> 00:07:42,870
over here.

123
00:07:42,900 --> 00:07:44,160
Now what about two.

124
00:07:44,190 --> 00:07:45,870
Can we fill two over here.

125
00:07:45,900 --> 00:07:48,870
No because two is there in the same row.

126
00:07:48,900 --> 00:07:49,980
What about three?

127
00:07:50,010 --> 00:07:51,390
Three is also there over here.

128
00:07:51,390 --> 00:07:52,710
So we can't fill three.

129
00:07:52,740 --> 00:07:53,880
What about four?

130
00:07:53,910 --> 00:07:56,100
Four is over here, which is the same column.

131
00:07:56,100 --> 00:07:57,300
So four is out.

132
00:07:57,330 --> 00:07:58,650
What about five?

133
00:07:58,680 --> 00:08:01,620
Notice five is there over here, which is the same row.

134
00:08:01,620 --> 00:08:03,150
So five is also out.

135
00:08:03,180 --> 00:08:04,290
What about six.

136
00:08:04,320 --> 00:08:06,060
Six is there in the same column.

137
00:08:06,060 --> 00:08:07,620
So six is also out.

138
00:08:07,650 --> 00:08:10,860
What about seven now seven, eight and nine.

139
00:08:10,860 --> 00:08:13,470
Notice all of these three are there in the same row.

140
00:08:13,470 --> 00:08:15,960
So all of these numbers are out.

141
00:08:15,960 --> 00:08:21,900
So notice that we are not able to fill any other value in this empty space.

142
00:08:21,900 --> 00:08:23,430
Now why did this happen.

143
00:08:23,430 --> 00:08:28,110
That's because one of these numbers that we previously filled is wrong.

144
00:08:28,110 --> 00:08:28,620
All right.

145
00:08:28,620 --> 00:08:35,010
So we cannot proceed further in this path because there's nothing valid that can be filled over here.

146
00:08:35,010 --> 00:08:39,810
And therefore we prune this path, we come back and we backtrack.

147
00:08:39,810 --> 00:08:40,320
All right.

148
00:08:40,320 --> 00:08:47,040
So we come back over here and we change the eight that we had previously filled over here.

149
00:08:47,040 --> 00:08:51,090
So we remove this eight and we try another value.

150
00:08:51,090 --> 00:08:58,260
And in this manner the algorithm keeps working till it finds a valid solution.

151
00:08:58,770 --> 00:09:05,520
So this is the backtracking approach that we will employ to solve the Sudoku solver problem.