1 00:00:00,420 --> 00:00:01,300 Welcome back, everyone. 2 00:00:01,890 --> 00:00:06,390 In the last video, we figured out what the recursive function signature looks like for backtracking 3 00:00:06,570 --> 00:00:07,360 in this video. 4 00:00:07,380 --> 00:00:10,690 Let's actually start to apply it to solving the Sudoku problem. 5 00:00:11,430 --> 00:00:16,470 The thing that we want to mention is that inside of our pseudocode, we know how to iterate through 6 00:00:16,470 --> 00:00:17,900 the different numbers we have. 7 00:00:18,240 --> 00:00:22,870 We know how to add a value to a 2D grid if we have the row in the column indexes. 8 00:00:23,340 --> 00:00:28,890 What gets more challenging is the decision making step because we need to make sure we are able to capture 9 00:00:28,890 --> 00:00:31,880 the constraints in a validity check here. 10 00:00:31,890 --> 00:00:38,220 Let's think about what we know when it comes to the constraints we add of value into the grid cell that 11 00:00:38,220 --> 00:00:38,740 we're looking at. 12 00:00:38,760 --> 00:00:40,830 So let's say it's this zero five grid. 13 00:00:40,830 --> 00:00:42,540 So we add a value here. 14 00:00:42,780 --> 00:00:44,580 How do we determine if it's valid or not? 15 00:00:44,940 --> 00:00:50,670 We need to check if there are any repeated values in the row and a repeated values in the column or 16 00:00:50,670 --> 00:00:53,550 any repeated values in this little square. 17 00:00:54,210 --> 00:00:56,190 So this means the three things we need to solve. 18 00:00:56,640 --> 00:01:02,380 How do we keep track of what values are already in the row if we have the R value? 19 00:01:02,430 --> 00:01:07,520 It's very easy for us to instantiate some type of rows data structure. 20 00:01:07,530 --> 00:01:13,590 Maybe it's an array that holds hash maps and inside of the hash map it tells us whether or not we've 21 00:01:13,590 --> 00:01:15,020 already seen that value. 22 00:01:15,420 --> 00:01:22,380 So let's say, for example, we add in a three, then we can say that the three is equal to true and 23 00:01:22,380 --> 00:01:26,670 all we would do is just check the rows for this corresponding index value. 24 00:01:26,790 --> 00:01:28,020 So let's say this is zero. 25 00:01:28,740 --> 00:01:33,600 Then we check the hash map and see if the actual value we just added already exists in it. 26 00:01:33,720 --> 00:01:36,210 If it does, then we know that we're repeating ourselves. 27 00:01:36,450 --> 00:01:40,610 If it doesn't, then we add it in and we can proceed on to the next one. 28 00:01:41,040 --> 00:01:47,430 And as you can see inside of this rows array, there would just be a hash map for every corresponding 29 00:01:47,430 --> 00:01:49,400 row inside of the board. 30 00:01:49,560 --> 00:01:54,710 One would map to one to what map to two, three would map to three, et cetera, et cetera. 31 00:01:55,700 --> 00:02:03,230 So we would do the exact same thing for columns, because we have a similar column index, so if we 32 00:02:03,230 --> 00:02:09,590 had the exact same situation and we added it here, then we would just check at column index five inside 33 00:02:09,590 --> 00:02:15,560 of our column data structure, we check out five, which would be down here, and we would see if the 34 00:02:15,560 --> 00:02:18,610 value we just added already exists in the Hashmat. 35 00:02:19,010 --> 00:02:24,230 If it doesn't, then we can proceed and we want to add it into this hash map and then do the next check, 36 00:02:24,410 --> 00:02:26,550 which is for the actual box. 37 00:02:27,320 --> 00:02:32,450 This is where it gets challenging because we still want to utilize this structure or something similar 38 00:02:32,660 --> 00:02:37,070 in order to keep track of what values we've added into one of these boxes. 39 00:02:37,670 --> 00:02:41,300 So here, what we want to do is we want to think about this structure. 40 00:02:42,420 --> 00:02:49,170 If we're able to keep track of all of the values in each box, we need to figure out how we can capture 41 00:02:49,200 --> 00:02:50,130 every box. 42 00:02:50,790 --> 00:02:56,880 So what if we assigned a similar index to every single box so the values could be zero? 43 00:02:56,910 --> 00:03:00,840 One, two, three, four, five, six, seven, eight. 44 00:03:01,830 --> 00:03:05,400 If we were to do that, how do we get the corresponding values? 45 00:03:05,760 --> 00:03:06,860 Well, let's break this down. 46 00:03:07,470 --> 00:03:13,800 If we were to segment these long rows together, then what we see is that the indexes of the boxes, 47 00:03:13,800 --> 00:03:16,860 zero to two, are in the first segment, zero one and two. 48 00:03:17,770 --> 00:03:22,030 Three to five would be the next segment, three, four and five. 49 00:03:22,890 --> 00:03:29,550 Six to eight would be the third segment six, seven, eight, so we need to figure out what values we 50 00:03:29,550 --> 00:03:30,360 have to begin with. 51 00:03:30,840 --> 00:03:33,710 We have a real value and we have a column value. 52 00:03:33,750 --> 00:03:35,130 These are the index values. 53 00:03:35,430 --> 00:03:40,290 We want to figure out how to combine them, to turn them into these corresponding indexes for these 54 00:03:40,290 --> 00:03:40,830 boxes. 55 00:03:41,490 --> 00:03:44,820 So let's logically break down what the row gives us and what the column gives us. 56 00:03:45,510 --> 00:03:53,250 The row can tell us which segment we're in, whereas the column will tell us which of the actual boxes 57 00:03:53,250 --> 00:03:54,370 in the segment we're in. 58 00:03:54,630 --> 00:03:56,140 So how do we capture that? 59 00:03:57,000 --> 00:03:58,470 Well, let's think about it like this. 60 00:03:59,770 --> 00:04:07,600 If we were to treat each box in each segment as some index on its own, so let's say we look at the 61 00:04:07,600 --> 00:04:14,680 indexes by themselves zero, one and two, regardless of what segment we're in, this left handed box 62 00:04:14,680 --> 00:04:15,940 is index zero. 63 00:04:16,060 --> 00:04:17,980 This middle box is index one. 64 00:04:18,190 --> 00:04:20,230 This third box is index to. 65 00:04:21,210 --> 00:04:27,810 Now, let's think mathematically, what do we need to add at every segment to zero one and two to give 66 00:04:27,810 --> 00:04:30,570 us the correct index of the box in that segment? 67 00:04:31,260 --> 00:04:37,530 When it comes to this first segment, it's going to be zero because these indexes already correspond 68 00:04:37,530 --> 00:04:39,000 to the correct placement. 69 00:04:39,690 --> 00:04:45,330 Zero plus zero gives us zero zero plus one, gives us one zero plus two, gives us two. 70 00:04:45,900 --> 00:04:47,130 What about the next segment? 71 00:04:47,460 --> 00:04:48,890 We want three to five. 72 00:04:49,380 --> 00:04:56,880 So this means that three plus zero gives us zero three plus one, gives us four, three plus two gives 73 00:04:56,880 --> 00:04:57,720 us five. 74 00:04:58,230 --> 00:05:03,690 So three is the value that we need to represent from the row values three, four, five in order to 75 00:05:03,690 --> 00:05:05,190 capture the correct segment. 76 00:05:05,670 --> 00:05:08,660 Similarly for the last segment, what do we need to add? 77 00:05:09,120 --> 00:05:16,290 We need six six plus zero gives us six six plus one, gives us seven six plus two gives us eight. 78 00:05:16,710 --> 00:05:22,830 So we need to figure out how to transform the corresponding row values to their corresponding correct 79 00:05:22,830 --> 00:05:30,270 base that we add similarly to the corresponding column index, transform to the column value that we 80 00:05:30,270 --> 00:05:33,810 want to add and together they form the correct index. 81 00:05:34,440 --> 00:05:36,420 So let's define this as a function. 82 00:05:36,900 --> 00:05:46,560 We'll say that const get baulks ID because that's what we're getting is equal to a function that receives 83 00:05:46,560 --> 00:05:48,810 the row and receives the column. 84 00:05:49,930 --> 00:05:55,690 Now, let's think about how we can do that with the most basic one, which is going to be the column, 85 00:05:56,470 --> 00:06:03,490 we can easily take whatever value we get and divide it by three and then round down even in our worst 86 00:06:03,490 --> 00:06:07,090 case, six, seven, eight, eight divided by three is two point sixty six. 87 00:06:07,090 --> 00:06:08,460 If we round down, then it's two. 88 00:06:08,710 --> 00:06:09,700 So this gives us two. 89 00:06:10,090 --> 00:06:13,930 Five divided by three is one point six seven. 90 00:06:14,080 --> 00:06:20,790 Round it down is one two divided by three is zero point six of it rounded down is zero. 91 00:06:21,340 --> 00:06:27,760 So then that means that the const column value that we need to add is equal to the column. 92 00:06:29,020 --> 00:06:31,270 Flawed, divided by three. 93 00:06:33,340 --> 00:06:34,820 And that gives us our column value. 94 00:06:35,530 --> 00:06:36,760 What about the row value? 95 00:06:37,450 --> 00:06:42,730 Well, here with the row value, what we notice is that each corresponding place is just triple the 96 00:06:42,730 --> 00:06:44,170 value that we derived here. 97 00:06:44,800 --> 00:06:48,540 So we're just going to do a very similar thing except multiply by three afterwards. 98 00:06:48,760 --> 00:06:52,570 So we're going to say the row value is equal to math floor. 99 00:06:53,810 --> 00:06:59,000 Of our row, divided by three, multiplied by three. 100 00:07:00,080 --> 00:07:07,610 And then all we need to return to get the correct box index is just the column value plus the row value. 101 00:07:11,420 --> 00:07:12,120 And that's it. 102 00:07:12,620 --> 00:07:20,180 Now we know how to store the Rowe values, the column values and the box values for the corresponding 103 00:07:20,570 --> 00:07:22,770 values that we add in every Griselle. 104 00:07:23,210 --> 00:07:27,650 So my challenge to you is actually to try and coat out the actual solution. 105 00:07:28,100 --> 00:07:34,580 You need to instantiate something that will keep track of the values in those rows and the columns and 106 00:07:34,580 --> 00:07:36,500 the grid cells that we get to. 107 00:07:37,010 --> 00:07:42,760 And you also need to figure out how to build out the board state following this general recursive pattern. 108 00:07:43,370 --> 00:07:48,500 So try it out yourself and then we'll do it all together completely in the next video.