1
00:00:00,390 --> 00:00:01,410
Welcome back, everyone.

2
00:00:02,130 --> 00:00:08,550
So we just figured out how we're going to store the values that we've put inside of each Griselle according

3
00:00:08,550 --> 00:00:13,380
to what's in the row, what's in the column and what's in the individual, three by three squares.

4
00:00:13,800 --> 00:00:15,930
Now we want to cut out the actual solution.

5
00:00:16,380 --> 00:00:19,160
So to start, you'll see that I just reorganize things a little bit.

6
00:00:19,170 --> 00:00:21,930
I've moved our get box ID function down here.

7
00:00:22,170 --> 00:00:24,860
I still have that template that we were looking at.

8
00:00:25,140 --> 00:00:28,940
And over here I've initialized our actual function where we receive the board.

9
00:00:29,460 --> 00:00:35,460
So to begin, we need to actually now initialize the data structures that are going to store the values

10
00:00:35,460 --> 00:00:37,100
that we need to begin.

11
00:00:37,110 --> 00:00:41,880
I'm just going to initialize something called rows, columns and boxes.

12
00:00:41,880 --> 00:00:47,790
And this is going to contain the arrays that will end up holding the hash maps that tell us how many

13
00:00:47,790 --> 00:00:52,080
values have been added to each respective data structure of that type.

14
00:00:52,620 --> 00:00:58,580
So here I'm just going to say first, let's get the end value, which is going to be our board size.

15
00:00:58,770 --> 00:01:01,050
So it's going to be nine, which we know for sure.

16
00:01:01,380 --> 00:01:04,950
But just in case, we'll just initialize it separately.

17
00:01:06,700 --> 00:01:13,030
Next, what we want to do is initialize our three different variables, so, one, I want boxes to be

18
00:01:13,030 --> 00:01:15,550
equal to a new array of size and.

19
00:01:19,740 --> 00:01:23,880
Then I also want Rose to be the same thing, so a new array.

20
00:01:24,900 --> 00:01:32,820
Of Size N and columns is also a new array of size and.

21
00:01:34,370 --> 00:01:39,770
Now we need to fill them with any different hash maps, we could have done the dot fill map method we've

22
00:01:39,770 --> 00:01:44,000
done before, but because we need to do it for all three, it's easier in my mind just to do a follow

23
00:01:44,000 --> 00:01:44,210
up.

24
00:01:44,720 --> 00:01:53,840
So I'm just going do for let I equals zero I less than an hour plus plus I'm just going to go boxes.

25
00:01:54,910 --> 00:02:05,470
I equals a new empty object rose at I, a new empty object, and then columns I.

26
00:02:06,460 --> 00:02:12,400
A new empty object, so now that we have the data structures that will help us keep track of whether

27
00:02:12,400 --> 00:02:18,220
or not we're violating any of our constraints, what we need to do is fill them with the initial values

28
00:02:18,220 --> 00:02:19,450
inside of the array.

29
00:02:20,320 --> 00:02:25,390
So what we want to do is we want to scan through this entire 2D array, so entire board.

30
00:02:25,630 --> 00:02:29,160
And if we see a value, these are values that come by default with the board.

31
00:02:29,200 --> 00:02:30,570
So we cannot change them.

32
00:02:30,850 --> 00:02:36,940
We need to add them automatically to either our boxes are rows or columns, depending on where they

33
00:02:36,940 --> 00:02:37,630
actually fit.

34
00:02:38,140 --> 00:02:41,380
So this is where we're just going to loop through the entire board.

35
00:02:43,330 --> 00:02:49,210
So I'm going to say four letters are equal, zero are less than an.

36
00:02:50,190 --> 00:02:51,660
Ah, plus, plus.

37
00:02:53,650 --> 00:03:02,020
Then I'm going to say again for let's see, equals zero C less than an C plus plus.

38
00:03:03,730 --> 00:03:10,120
So at this point, what we need to check is whether or not the board presence there has a value, the

39
00:03:10,120 --> 00:03:16,340
easiest way to do this is to ask what the empty cell is going to contain.

40
00:03:16,360 --> 00:03:20,050
Is it just going to be undefined or is there some kind of stipulation here?

41
00:03:20,770 --> 00:03:23,020
Generally speaking, there's a couple of ways you can do this.

42
00:03:23,290 --> 00:03:28,930
You can assume that if, for example, in the grid cell, if it's empty, then the value that's there

43
00:03:28,930 --> 00:03:35,590
is not going to be greater than zero because we can only hold the values one to nine, which means that

44
00:03:35,590 --> 00:03:40,780
if it's empty, it's going to be undefined or they're going to use zero or they're going to use any

45
00:03:40,780 --> 00:03:42,870
kind of character to hold an empty space.

46
00:03:43,390 --> 00:03:49,120
In this particular case, with this question, it's going to be a period which is a string.

47
00:03:49,690 --> 00:03:52,330
So we're just going to say that if board.

48
00:03:53,750 --> 00:04:00,620
At ah and at see, so at the current GRISELLE does not equal period, meaning that it already contains

49
00:04:00,620 --> 00:04:01,400
a value.

50
00:04:02,780 --> 00:04:10,280
Then we're going to add and fill it into our respective board rows and columns at the correspondingly

51
00:04:10,280 --> 00:04:13,490
correct placement and inside of their hash map.

52
00:04:14,300 --> 00:04:17,120
So first of all, we need to do is we need to get the value.

53
00:04:17,720 --> 00:04:23,030
So here we're just going to initialize it as Val is equal to board at our.

54
00:04:26,390 --> 00:04:32,840
Then what we want to do is we want to get the box ID, which we already can easily do using our get

55
00:04:32,840 --> 00:04:36,190
box ID function that we wrote in our last lesson.

56
00:04:36,950 --> 00:04:39,080
So here I'm going to say const box ID.

57
00:04:41,150 --> 00:04:43,970
Is equal to get Bogside.

58
00:04:46,140 --> 00:04:51,530
And we just passing the R and the C value, and we'll get back the correct backside where this current

59
00:04:51,540 --> 00:04:54,090
GRISELLE lives, and then it's very simple.

60
00:04:54,090 --> 00:04:55,500
We just do boxes.

61
00:04:57,260 --> 00:04:58,090
Bogside.

62
00:04:59,780 --> 00:05:02,990
At this value is equal to true because we're using a Hashmat.

63
00:05:04,340 --> 00:05:08,420
I do want to mention that you could use a set if you wanted to, which is a special data structure that

64
00:05:08,420 --> 00:05:12,650
holds unique values, but I'm just going to continue using a hash map because that's what we've learned.

65
00:05:13,940 --> 00:05:19,370
We're going to do the same thing, Rose, at our value is now also equal to true.

66
00:05:21,300 --> 00:05:26,790
And then columns at sea at this value is also equal to true.

67
00:05:28,870 --> 00:05:35,110
And that's it that will set us up for all of those initialise values that we have inside of the board

68
00:05:35,320 --> 00:05:41,890
so that we now know what to do, if they are duplicated, then all we need to do is write out the actual

69
00:05:41,890 --> 00:05:49,360
recursive function that will drive the check and the filling of the pieces into the board and also the

70
00:05:49,360 --> 00:05:50,100
backtracking.

71
00:05:50,110 --> 00:05:54,280
This is all going to happen through one function so we can call it solved.

72
00:05:54,280 --> 00:05:54,940
Backtrack.

73
00:05:56,930 --> 00:06:01,460
And we just need to think about what's going to be added to this function as a capital B..

74
00:06:02,610 --> 00:06:04,290
So here, we're going to pass in the board.

75
00:06:04,440 --> 00:06:10,590
Of course, we're going to pass in all of our data structures that are storing what values get repeated

76
00:06:10,620 --> 00:06:12,890
so boxes, rows and columns.

77
00:06:13,350 --> 00:06:20,300
And we're also going to pass in the values that we're going to start from for our R and R, C, respectively.

78
00:06:20,310 --> 00:06:22,250
So, of course, we're going to start from the top left corner.

79
00:06:22,260 --> 00:06:24,540
So we're just going to initialize it at zero zero.

80
00:06:25,880 --> 00:06:30,800
So when we cut out this function, it is going to be pretty large and there's a lot of considerations

81
00:06:30,800 --> 00:06:37,190
we have to make as far as the constraints of the box that we're coding in itself, not necessarily just

82
00:06:37,190 --> 00:06:43,130
the actual constraints of the logic of whether or not a value in the Sudoku board is truly valid.

83
00:06:43,340 --> 00:06:44,680
We do have to consider that as well.

84
00:06:44,810 --> 00:06:48,730
But there are a bunch of these little edge cases that will occur that you want to think about.

85
00:06:49,280 --> 00:06:54,470
So before we move on to the next video where we'll code this out together, I do want you to try and

86
00:06:54,470 --> 00:06:57,920
think about what these different constraints will be.

87
00:06:58,370 --> 00:07:00,770
And then once you're ready, move on to the next video.

88
00:07:00,770 --> 00:07:04,190
I will cut out the last portion, which is our solve backtrack function.