1 00:00:00,430 --> 00:00:06,550 Welcome back, everyone, let's tackle our Sudoku, solve our algorithm to begin with. 2 00:00:06,550 --> 00:00:10,930 How do we recognize that this question needs backtracking as a solution? 3 00:00:12,030 --> 00:00:17,270 This is where you need to think about the question, sometimes the question itself will give it away. 4 00:00:17,400 --> 00:00:23,190 Other times you need to start thinking about how you could solution and realize that backtracking is 5 00:00:23,190 --> 00:00:24,450 one of the possibilities. 6 00:00:24,600 --> 00:00:30,570 And the way it works is that if you need to solve all the solutions or if you need to solve all the 7 00:00:30,570 --> 00:00:37,200 valid solutions or even just solve for one valid solution, these are all different things that tell 8 00:00:37,200 --> 00:00:40,190 you that backtracking could be a possible option for you. 9 00:00:40,500 --> 00:00:46,740 The reason why this happens is when you need to generate all possible solutions, if all of the solutions 10 00:00:46,740 --> 00:00:54,270 are not correct, meaning that looking at this Sudoku board, we could fill in these values with any 11 00:00:54,270 --> 00:00:57,960 number we could fill them, even with the numbers, one to nine only. 12 00:00:58,110 --> 00:01:04,560 But as long as we're not obeying all of these rules, then automatically we know that that solution 13 00:01:04,560 --> 00:01:11,220 is absolutely incorrect and all the possible solutions involved with certain violations of rules should 14 00:01:11,220 --> 00:01:12,070 not be contained. 15 00:01:12,450 --> 00:01:19,440 So, for example, imagine that we placed a five here and from five on there are numerous other values 16 00:01:19,440 --> 00:01:19,910 to fill. 17 00:01:20,280 --> 00:01:28,380 However, whatever value you fill in for the rest of exploring, filling out this board, as long as 18 00:01:28,380 --> 00:01:34,950 five is here, you are violating this constraint of needing unique values in a row because there are 19 00:01:34,950 --> 00:01:35,850 two fives here. 20 00:01:36,150 --> 00:01:44,010 So we can say that no matter what value you fill in these squares, as long as five is placed here, 21 00:01:44,340 --> 00:01:46,780 this is going to be incorrect. 22 00:01:47,160 --> 00:01:52,740 So from here, what you'll notice is that this is exactly what backtracking tries to do. 23 00:01:52,980 --> 00:02:01,080 Backtracking says that if I place a value the moment that I realized that placing that value violates 24 00:02:01,080 --> 00:02:08,160 one of these rules, I know that any possible solution that I fill in for the rest of this board is 25 00:02:08,190 --> 00:02:09,860 automatically going to be incorrect. 26 00:02:10,020 --> 00:02:14,850 So why even waste the resources generating out those options? 27 00:02:15,090 --> 00:02:17,550 And that's exactly what backtracking helps us do. 28 00:02:18,090 --> 00:02:24,090 It realizes that in order to solve the problem, we need to generate all of the possible solutions that 29 00:02:24,090 --> 00:02:24,790 could exist. 30 00:02:25,200 --> 00:02:30,660 However, some of those solutions, if not most of them, are going to be invalid. 31 00:02:30,990 --> 00:02:35,040 If that's the case, I don't want to waste any resources generating those solutions. 32 00:02:35,130 --> 00:02:36,650 I want to throw them away instead. 33 00:02:37,200 --> 00:02:39,930 That's when you can tell that backtracking helps you out. 34 00:02:40,830 --> 00:02:45,340 So the other thing about backtracking is that backtracking is a brute force solution. 35 00:02:46,020 --> 00:02:51,360 What I mean by brute force solution is that a brute force solution is typically known as one that isn't 36 00:02:51,360 --> 00:02:52,570 really finished. 37 00:02:52,590 --> 00:02:55,590 There's no real algorithm here that makes it more efficient. 38 00:02:55,950 --> 00:03:01,340 We are literally going to compute every possible option until we've computed one. 39 00:03:01,350 --> 00:03:02,040 That's correct. 40 00:03:02,070 --> 00:03:03,420 It's a brute force. 41 00:03:03,750 --> 00:03:05,580 There's no optimizations here. 42 00:03:06,150 --> 00:03:11,060 Yes, the throwing away of certain paths, you can consider an optimization. 43 00:03:11,400 --> 00:03:17,970 But generally speaking, the main structure of the algorithm is that it wants to force all of the answers 44 00:03:18,090 --> 00:03:22,150 through what you would consider just what you would logically do to solve the problem. 45 00:03:22,710 --> 00:03:28,770 So by realizing it's a brute force algorithm, you can probably glean a lot of insights about how to 46 00:03:28,770 --> 00:03:33,750 write and set up the algorithm by just thinking about how you would do this problem logically. 47 00:03:34,770 --> 00:03:39,910 So to start Sudoku is a game that people have played for a really long time. 48 00:03:40,560 --> 00:03:45,110 This means that you can easily play this game without the context of using a computer. 49 00:03:45,810 --> 00:03:51,570 If we were to play this game, the way that you would start is you would pick a cell and you would fill 50 00:03:51,570 --> 00:03:51,900 it out. 51 00:03:52,500 --> 00:03:59,400 So you would say, OK, I know that I cannot repeat values in the row, in the column and in the square. 52 00:04:00,120 --> 00:04:04,770 So I'm going to look inside of the square and find values I can use here. 53 00:04:04,770 --> 00:04:10,890 The three, five, six, nine and eight are taken so I can use one, two, four and seven. 54 00:04:11,720 --> 00:04:17,960 I'm going to start with the lowest volume, so one, and then I am going to make sure that I'm not violating 55 00:04:17,960 --> 00:04:21,380 the row and that I'm not violating the column, I'm not. 56 00:04:21,410 --> 00:04:24,750 OK, so let's move on to the next square inside of this square. 57 00:04:24,800 --> 00:04:30,650 I see that I have one seven nine five, but I've already used one three, five and seven. 58 00:04:31,220 --> 00:04:34,380 The next value that I could use is four. 59 00:04:35,060 --> 00:04:38,780 So let me try and use four and put it inside of the square. 60 00:04:39,860 --> 00:04:41,060 Then let's move on. 61 00:04:42,030 --> 00:04:45,660 Here, I've already used one, three, five, four and seven. 62 00:04:46,630 --> 00:04:53,650 So what I could put here is another value that I haven't seen yet, maybe two, two is the smallest 63 00:04:53,650 --> 00:04:57,890 value, so I put two in because I'm not violating the ROE. 64 00:04:57,940 --> 00:04:59,340 I'm not buying the column. 65 00:04:59,530 --> 00:05:01,030 I'm also not violating the square. 66 00:05:02,120 --> 00:05:08,180 When we look at this value now, what you'll notice is that the next smallest value we can put in, 67 00:05:08,570 --> 00:05:13,790 that's not one, two, three, four, five is six. 68 00:05:14,850 --> 00:05:21,630 So we know that six is one of the remaining values we have to put in, but six can go into any of these 69 00:05:21,630 --> 00:05:22,370 three squares. 70 00:05:22,620 --> 00:05:29,430 But regardless of where it goes, it's going to violate the rule about this three by three grid because 71 00:05:29,430 --> 00:05:30,840 there's already a six here. 72 00:05:31,440 --> 00:05:37,890 So automatically what we need to do is we need to back track back somewhere where we can change the 73 00:05:37,890 --> 00:05:38,330 value. 74 00:05:38,850 --> 00:05:43,230 So what we can do is we can go back to this value and put a six here instead. 75 00:05:44,740 --> 00:05:49,840 From this point on, we can continue with filling out the rest of the values and what you'll notice 76 00:05:49,840 --> 00:05:54,370 is that let's say we keep filling out the values and going down to the next row, filling out values. 77 00:05:54,820 --> 00:06:02,940 If we get to this value and the only value we can put in here, we notice, is a one in order for it 78 00:06:02,950 --> 00:06:04,720 not to violate the rules. 79 00:06:05,650 --> 00:06:11,680 What you'll notice is that maybe we have to continue backtracking through more than just going back 80 00:06:11,710 --> 00:06:17,830 one last value, we might have to keep going all the way back until possibly the very front, because 81 00:06:17,830 --> 00:06:24,090 by the very nature of how the border state is currently, there's no possible way for one to be here. 82 00:06:24,550 --> 00:06:29,590 What this means is that you might have to explore every possible number of combinations that we could 83 00:06:29,590 --> 00:06:32,090 have had all the way back to this point. 84 00:06:32,440 --> 00:06:36,220 This is a possibility, but backtracking doesn't care. 85 00:06:36,220 --> 00:06:37,770 Backtracking says that's perfectly fine. 86 00:06:37,960 --> 00:06:39,730 That's the way that I solve problems. 87 00:06:39,880 --> 00:06:44,290 I am going to extensively try one value at a time. 88 00:06:44,590 --> 00:06:49,870 And if I reach a point where I have to go back to see and that doesn't work, just keep going back, 89 00:06:50,110 --> 00:06:55,720 keep going back and exploring options until we're able to proceed past this point. 90 00:06:56,230 --> 00:06:59,650 That's backtracking and that's why it's based out of brute force. 91 00:07:00,370 --> 00:07:05,530 So continuing from there, let's think about the next thing about backtracking, which is the fact that 92 00:07:05,530 --> 00:07:07,780 it's a recursive based solution. 93 00:07:08,230 --> 00:07:15,040 As we know with recursion, what we do is we want to recursively call the same function but proceed 94 00:07:15,040 --> 00:07:17,200 along the path of solving the problem. 95 00:07:17,470 --> 00:07:23,530 In our particular case, you can see solving the problem as if we're filling in these values according 96 00:07:23,530 --> 00:07:24,570 to a traversal pattern. 97 00:07:25,000 --> 00:07:29,320 Let's say the traversal pattern we pick goes left to right and then top down. 98 00:07:29,320 --> 00:07:34,440 So it goes left to right, constantly trying to fill in the values inside of the grid cells. 99 00:07:34,900 --> 00:07:37,660 So the first value we would fill in is the first one. 100 00:07:37,960 --> 00:07:41,970 And what we're going to do is we're going to attempt every value from one to nine. 101 00:07:42,460 --> 00:07:44,610 So the first thing we would do is try one. 102 00:07:44,860 --> 00:07:47,470 So this would be our first function, call F of one. 103 00:07:47,890 --> 00:07:50,950 I'm just going to keep the number here so you know what we're talking about. 104 00:07:52,070 --> 00:07:55,490 We put in the one we see, does it duplicate in the row, no. 105 00:07:55,490 --> 00:07:56,730 Does it duplicate in the column? 106 00:07:56,750 --> 00:07:57,170 No. 107 00:07:57,200 --> 00:07:58,850 Is it duplicated in the square? 108 00:07:59,000 --> 00:07:59,390 No. 109 00:07:59,520 --> 00:08:00,690 OK, so that's good. 110 00:08:00,950 --> 00:08:05,330 We then move on to the next value in our traversal pattern here. 111 00:08:05,340 --> 00:08:06,770 Once again, we want to try the one. 112 00:08:07,070 --> 00:08:12,620 So this is where you would recursively call from within this original function call where we place the 113 00:08:12,620 --> 00:08:17,600 one the next function call recursively for the value of of one. 114 00:08:17,840 --> 00:08:19,580 We're going to try the one right here. 115 00:08:20,120 --> 00:08:23,060 We place the one and then we check, OK, do we violate rules? 116 00:08:23,300 --> 00:08:23,930 We do. 117 00:08:24,080 --> 00:08:26,850 We have a one already in the row and we have a one in the square. 118 00:08:27,200 --> 00:08:31,010 So this means that we want to pop off this F of one. 119 00:08:31,160 --> 00:08:33,680 We want to finish hit a base case right here. 120 00:08:33,680 --> 00:08:34,790 We broke one of the rules. 121 00:08:34,940 --> 00:08:38,440 So we're going to exit and come back up to F of one. 122 00:08:38,960 --> 00:08:40,760 So we're going to remove that value. 123 00:08:41,330 --> 00:08:45,920 And then from F of one, we're going to try the next value, which is to say we're going to place the 124 00:08:45,920 --> 00:08:47,030 two at once again. 125 00:08:47,030 --> 00:08:47,840 We check our rules. 126 00:08:48,500 --> 00:08:50,030 Do we violate our row? 127 00:08:50,060 --> 00:08:50,450 No. 128 00:08:50,600 --> 00:08:52,000 Do we violate our column? 129 00:08:52,010 --> 00:08:52,430 No. 130 00:08:52,530 --> 00:08:53,660 Do we violate our square? 131 00:08:53,870 --> 00:08:54,260 No. 132 00:08:54,410 --> 00:08:57,980 OK, so F of two is perfectly fine. 133 00:08:58,610 --> 00:09:00,810 Then we keep on going to the next value. 134 00:09:00,950 --> 00:09:05,750 So at this place, once again, we call F of one for this square. 135 00:09:06,110 --> 00:09:07,970 We place the one and we check. 136 00:09:07,970 --> 00:09:09,100 Are we violating rules? 137 00:09:09,110 --> 00:09:10,640 Yes, we violate the row rule. 138 00:09:10,760 --> 00:09:17,810 So we're going to once again pop this off and backtrack back up to the last previous valid state, which 139 00:09:17,810 --> 00:09:19,040 was when we place the two. 140 00:09:20,060 --> 00:09:24,020 From here, we're going to try another value, so we're going to place a two. 141 00:09:24,440 --> 00:09:29,390 We're going to call off of two as the next recursive function call in this squares F of to call. 142 00:09:30,560 --> 00:09:34,700 What we're going to see is that, OK, we place the two, do we violate the rules? 143 00:09:35,180 --> 00:09:37,210 Yes, there's already a two in this row. 144 00:09:37,220 --> 00:09:40,820 So once again, we backtrack, we end this call stack. 145 00:09:41,820 --> 00:09:46,520 And we remove the value and then we try something else, we try three, so we call EVA three. 146 00:09:47,250 --> 00:09:50,610 Then once again inside of here we do our check for constraints. 147 00:09:51,090 --> 00:09:52,770 We see that we violate a rule. 148 00:09:53,040 --> 00:09:55,530 Once again, we backtrack again. 149 00:09:55,860 --> 00:09:59,250 We go back to the last valid state, which is evolve to. 150 00:10:00,190 --> 00:10:07,000 And we try the next value, so we try for a four for does for violate the rules, No. 151 00:10:07,360 --> 00:10:08,780 Four is perfectly valid. 152 00:10:09,340 --> 00:10:12,370 So here we notice that it's OK, we continue. 153 00:10:12,550 --> 00:10:14,560 And what you'll notice is that that's what we're going to do. 154 00:10:14,560 --> 00:10:20,590 We're just going to keep reiterating the step in this recursive manner, one to nine, one to nine, 155 00:10:20,590 --> 00:10:23,370 one to nine, one to nine going down this call stack. 156 00:10:23,500 --> 00:10:28,360 But the moment we realized that we've gone through the values or there's a value that doesn't work, 157 00:10:28,600 --> 00:10:33,130 then we go up the cost that if none of those values work, we go up the cost stack again. 158 00:10:33,220 --> 00:10:38,890 We keep going up the call stack until we try all of the values in the next level that work. 159 00:10:39,100 --> 00:10:41,530 And then from there, we can continue and continue. 160 00:10:41,740 --> 00:10:48,490 And you can see how we're mimicking this extensive, extensive brute force process while utilizing the 161 00:10:48,490 --> 00:10:53,230 recursion to keep track of where we can backtrack to. 162 00:10:53,740 --> 00:11:00,440 This is how we utilize recursion to mimic our brute force solution that's incorporated backtracking. 163 00:11:00,760 --> 00:11:04,810 So this is just the high level analysis of what backtracking is. 164 00:11:05,000 --> 00:11:07,240 It's a combination of brute force and recursion. 165 00:11:07,480 --> 00:11:09,590 In the next video, we're actually going to code it out. 166 00:11:09,700 --> 00:11:15,280 So if this is even still a little confusing, don't worry, we'll code it out together and it will make 167 00:11:15,280 --> 00:11:15,960 more sense. 168 00:11:16,600 --> 00:11:17,920 So let's move on to the next video.