1
00:00:00,140 --> 00:00:07,040
In the previous video, we discussed the approach, the backtracking approach that we can take to solve

2
00:00:07,040 --> 00:00:10,280
the Sudoku solver coding interview question.

3
00:00:10,280 --> 00:00:16,550
In this video, let's proceed and write the pseudo code of the approach that we discussed.

4
00:00:16,550 --> 00:00:22,520
So when we are presented with the board, the first thing that we need to do is we need to identify

5
00:00:22,520 --> 00:00:24,110
the next empty cell.

6
00:00:24,110 --> 00:00:27,200
And this is what we will do in every recursive call.

7
00:00:27,200 --> 00:00:35,750
Now once we identify an empty cell, we will try the numbers from 1 to 9, and we will see which number

8
00:00:35,750 --> 00:00:42,770
would be valid to be filled in that particular empty cell, keeping in mind the three rules which have

9
00:00:42,770 --> 00:00:44,120
to be satisfied.

10
00:00:44,120 --> 00:00:50,330
Now, let's say there are two outcomes or two possible outcomes from trying these numbers.

11
00:00:50,330 --> 00:00:53,600
The first outcome is that we get a valid number.

12
00:00:53,600 --> 00:00:59,660
And it could also so happen that none of the numbers fit in in that empty cell.

13
00:00:59,660 --> 00:01:05,750
Now, if we do get a valid number we proceed and fill that number in the board.

14
00:01:06,410 --> 00:01:13,520
And once we have filled that number in that empty space, we again recursively call the same function

15
00:01:13,520 --> 00:01:16,130
to fill the next empty cell.

16
00:01:16,160 --> 00:01:23,690
Now, if we are not getting any valid number for the empty cell at hand, it means that whatever we

17
00:01:23,690 --> 00:01:28,190
have filled so far is not correct and therefore we can stop.

18
00:01:28,190 --> 00:01:31,040
There's no more point in proceeding down this path.

19
00:01:31,040 --> 00:01:34,730
Therefore, we would just return and prune this path.

20
00:01:34,760 --> 00:01:41,660
Now, once we return over here, we would come back to the recursive call to the previous call, which

21
00:01:41,660 --> 00:01:43,970
actually called the next empty cell.

22
00:01:43,970 --> 00:01:47,390
Like again, for example, we are trying to fill this empty cell.

23
00:01:47,390 --> 00:01:53,060
We filled something and we recursively called the same function to fill the next empty cell.

24
00:01:53,090 --> 00:01:57,710
Now let's say in this case we are not getting any valid number.

25
00:01:57,710 --> 00:02:04,400
Therefore we will return and we will come to this part over here, which is this line of code where

26
00:02:04,400 --> 00:02:08,090
we had called the function recursively to fill the next empty cell.

27
00:02:08,120 --> 00:02:13,580
Now at this point, because what we filled over here is wrong, because that's why we were not able

28
00:02:13,580 --> 00:02:15,380
to get anything valid over here.

29
00:02:15,380 --> 00:02:22,460
What we do is we backtrack, which means that we change the number that we had filled over here and

30
00:02:22,460 --> 00:02:24,920
we try another possible combination.

31
00:02:24,920 --> 00:02:30,260
So again, the backtracking step is reverting the change that we had done over here.

32
00:02:30,980 --> 00:02:37,970
Now, if we are not able to identify any empty cell, what would that mean.

33
00:02:37,970 --> 00:02:43,970
That would mean that the board is already full or the board has been solved.

34
00:02:43,970 --> 00:02:47,420
And in that case we can just return true.

35
00:02:47,420 --> 00:02:53,150
Because again, remember we are just trying to find one solution as per the problem statement given

36
00:02:53,150 --> 00:02:53,750
to us.

37
00:02:53,780 --> 00:02:58,490
Now, if it returns true, then again it would be in this call.

38
00:02:58,490 --> 00:03:01,430
Because let's say we just have two empty spaces.

39
00:03:01,430 --> 00:03:03,590
So we fill the first empty space.

40
00:03:03,590 --> 00:03:07,610
We recursively call the same function to fill the second empty space.

41
00:03:07,610 --> 00:03:14,780
And when we again recursively call the function, let's say in our hypothetical scenario, if there

42
00:03:14,780 --> 00:03:21,650
are no other empty cells, it would return true from here, and we would come back to this place where

43
00:03:21,650 --> 00:03:23,930
we had recursively call the same function.

44
00:03:23,930 --> 00:03:25,940
And we are getting back true over here.

45
00:03:25,940 --> 00:03:26,510
Right?

46
00:03:26,510 --> 00:03:35,090
So when it returns true, we can just stop because again the question just asks us to find one solution.

47
00:03:35,090 --> 00:03:40,430
Now if it's not returning true, that would be this scenario over here.

48
00:03:40,430 --> 00:03:46,790
Because we will come back over here only when either it returns true or it does not return true, because

49
00:03:46,790 --> 00:03:51,560
otherwise we would just go deeper and deeper till we are done with filling the board.

50
00:03:51,560 --> 00:03:57,560
And then we would start coming back with either true or false, and if it's full, we would be coming

51
00:03:57,560 --> 00:03:58,490
back with true.

52
00:03:58,490 --> 00:04:04,310
So the other possibility of coming back over here is when we are not able to fill any of the values.

53
00:04:04,310 --> 00:04:08,240
And in that case, we would have to return false.

54
00:04:08,990 --> 00:04:15,050
And this would be an indication that we can proceed to the next line, which is the backtracking step.

55
00:04:15,050 --> 00:04:19,640
So we remove whatever we filled over here and we try a different number.

56
00:04:19,640 --> 00:04:25,940
And again when we get true, we can just stop because it indicates that we have found the solution.

57
00:04:25,940 --> 00:04:33,020
So this is the pseudo code that we can use to implement the backtracking approach for the Sudoku solver

58
00:04:33,020 --> 00:04:33,650
problem.

59
00:04:33,650 --> 00:04:40,760
Now let's compare this pseudo code with the backtracking blueprint that we had previously discussed.

60
00:04:40,760 --> 00:04:42,830
So we have the blueprint over here.

61
00:04:42,830 --> 00:04:48,440
Notice that in the blueprint, the first thing that we had over here was the base condition.

62
00:04:48,440 --> 00:04:50,780
So if it was solved we could return.

63
00:04:50,780 --> 00:04:52,550
So that's what we have over here.

64
00:04:52,550 --> 00:04:55,940
If we see that there is no empty cell, we can return.

65
00:04:55,940 --> 00:05:00,200
Now, the other part over here is that we were exploring all the choices.

66
00:05:00,200 --> 00:05:06,710
And in the Sudoku solver problem, the choices that we have are the values from 1 to 9.

67
00:05:06,710 --> 00:05:12,440
And then over here we were checking whether is valid, whether a particular number is valid to be filled

68
00:05:12,440 --> 00:05:14,570
in an identified empty cell.

69
00:05:14,570 --> 00:05:17,810
And that's the check over here is valid choice.

70
00:05:17,810 --> 00:05:20,960
And again the choice is the number that we have chosen.

71
00:05:20,960 --> 00:05:24,080
And then over here in the blueprint we have the three steps.

72
00:05:24,080 --> 00:05:28,310
Choose recursively call the function again and then the backtracking step.

73
00:05:28,310 --> 00:05:31,460
So notice that is what we have over here as well.

74
00:05:31,460 --> 00:05:33,260
Fill is the choice step.

75
00:05:33,260 --> 00:05:35,360
Then we have the recursive call over here.

76
00:05:35,360 --> 00:05:38,030
And then over here we have the backtracking step.

77
00:05:38,030 --> 00:05:39,890
So this is the pseudo code.

78
00:05:39,890 --> 00:05:45,110
And it matches with the backtracking blueprint that we had previously discussed.

79
00:05:45,110 --> 00:05:50,720
So let's go ahead and implement this and solve the Sudoku solver question.