1 00:00:06,220 --> 00:00:09,100 In this video, I want to lay out the search intuition. 2 00:00:09,100 --> 00:00:15,230 The basic idea that's going to underlie our Sudoku board solver. 3 00:00:15,230 --> 00:00:20,370 As I said before, the basic idea is we're going to take an initial Sudoku board And 4 00:00:20,370 --> 00:00:23,920 we're going to generate a tree of all the possible boards that follow from it, 5 00:00:23,920 --> 00:00:30,310 looking for a solution. Now, that may seem surprising, when you 6 00:00:30,310 --> 00:00:33,910 look at a Sudoku board on paper, it doesn't look like a tree. 7 00:00:33,910 --> 00:00:38,830 And as we saw, our representation of the board is just a single, flat list, so 8 00:00:38,830 --> 00:00:42,150 there's no tree there. So where's the tree? 9 00:00:43,200 --> 00:00:47,503 Well we're going to generate the tree. It's going to be a generative recursion. 10 00:00:47,503 --> 00:00:52,670 Here we go. Imagine that you start with a board, and 11 00:00:52,670 --> 00:00:55,522 here I'm just kind of showing the upper left part of the board. 12 00:00:55,522 --> 00:00:59,080 So imagine that you start with a board that has some squares filled in. 13 00:00:59,080 --> 00:01:02,160 Kind of like a Sudoku puzzle you might see in the newspaper. 14 00:01:02,160 --> 00:01:05,930 You may remember newspapers are things printed on paper that come to your 15 00:01:05,930 --> 00:01:09,600 doorstep in the morning. So you might see it on your phone or 16 00:01:09,600 --> 00:01:11,695 something. But here is the upper left part of a 17 00:01:11,695 --> 00:01:17,490 Sudoku puzzle. So you want to find a solution to that 18 00:01:17,490 --> 00:01:20,360 problem. Or maybe find out that the board's not 19 00:01:20,360 --> 00:01:22,750 solvable. What could you do? 20 00:01:25,190 --> 00:01:29,710 Well, the idea behind root for search is, here's the first empty square. 21 00:01:29,710 --> 00:01:32,325 That's the first place where there's not a number. 22 00:01:32,325 --> 00:01:38,920 What if I take that square and I fill it in with all possible values? 23 00:01:38,920 --> 00:01:43,250 That gives me nine possible next boards, because I basically fill the empty square 24 00:01:43,250 --> 00:01:48,740 with 1, 2, 3, 4, 5, 6, 7, 8, 9. Now of course some of those boards are 25 00:01:48,740 --> 00:01:52,020 immediately invalid. Right? 26 00:01:52,020 --> 00:01:56,540 The second board is invalid because that gives you two 2's in the same row. 27 00:01:56,540 --> 00:02:01,260 So we can cross that one out right away. And the third board is invalid because it 28 00:02:01,260 --> 00:02:05,870 gives you two 4's in the same row. And the fifth board is invalid because it 29 00:02:05,870 --> 00:02:11,957 gives you two 5's in the same box. So we can kind of immediately rule out 30 00:02:11,957 --> 00:02:18,031 the invalid boards. And in this case, that leaves us with 31 00:02:18,031 --> 00:02:24,120 just six next boards. So now what do we do? 32 00:02:24,120 --> 00:02:29,700 Well, none of those boards is a complete solution, right, because none of those 33 00:02:29,700 --> 00:02:35,743 boards has no empty spaces. Then we just do the same thing again. 34 00:02:35,743 --> 00:02:43,738 We find the next empty square, we fill it in with the nine possible values and we 35 00:02:43,738 --> 00:02:50,035 prune. Now we've got some more empty boards. 36 00:02:50,035 --> 00:02:52,000 Now, what's going on here? What are we doing? 37 00:02:52,000 --> 00:02:56,780 What I want to say to you is that there's three crucial aspects to what's going on 38 00:02:56,780 --> 00:03:01,520 here. We are generating an arbitrary-arity tree 39 00:03:01,520 --> 00:03:03,610 and we're doing a backtracking search over it. 40 00:03:03,610 --> 00:03:05,816 Those are the three things. Let me explain them in turn. 41 00:03:05,816 --> 00:03:12,356 First, the generation. Well, the generation is straightforward. 42 00:03:12,356 --> 00:03:17,130 This second row of boards here, this second row of boards, those are new 43 00:03:17,130 --> 00:03:20,020 boards. Those boards aren't some subpart of the 44 00:03:20,020 --> 00:03:22,400 first board. We didn't take the rest of the first 45 00:03:22,400 --> 00:03:26,140 board to get those boards. The rest of the first board is just a 46 00:03:26,140 --> 00:03:30,870 list 80 elements long. We need to generate these new boards, so 47 00:03:30,870 --> 00:03:36,260 that's why this is generation. And because it's generation, we can start 48 00:03:36,260 --> 00:03:41,610 to think generative recursion. Generative recursion template probably 49 00:03:41,610 --> 00:03:45,930 plays along in here. Now arbitrary-arity, the reason I'm 50 00:03:45,930 --> 00:03:50,609 saying it's an arbitary-arity tree is that each board has 0 to 9 valid 51 00:03:50,609 --> 00:03:55,790 children, 0 to 9 valid next boards. Okay? 52 00:03:55,790 --> 00:03:59,900 Because for each board, we take the first empty square. 53 00:03:59,900 --> 00:04:07,130 We fill it in with the nine possible values, 1 to 9, and then we prune the 54 00:04:07,130 --> 00:04:10,968 invalid ones. So there could be up to nine valid 55 00:04:10,968 --> 00:04:15,834 children, that's why it's an arbitrary-arity tree. 56 00:04:17,920 --> 00:04:20,620 And we're doing a backtracking search over it. 57 00:04:20,620 --> 00:04:23,190 Well, the reason we're doing a backtracking search is just we're 58 00:04:23,190 --> 00:04:28,300 going to keep exploring this tree until we come to a board that has no valid next 59 00:04:28,300 --> 00:04:31,062 board. That's a board with no children. 60 00:04:31,062 --> 00:04:35,820 And what do we usually do when we're searching for something and we wind up no 61 00:04:35,820 --> 00:04:37,640 where. And we produce false. 62 00:04:37,640 --> 00:04:43,268 That's the idea of backtracking. When you get to looking for something in 63 00:04:43,268 --> 00:04:48,480 nothing, you're in trouble. So you produce false. 64 00:04:48,480 --> 00:04:50,390 Or we're going to come to a board that's full. 65 00:04:50,390 --> 00:04:53,420 And because of the way that we're producing the tree, because of the way 66 00:04:53,420 --> 00:04:58,500 we're generating the tree where we immediately throw out invalid boards, if 67 00:04:58,500 --> 00:05:01,840 we come to a board that's full, then it's a solution. 68 00:05:01,840 --> 00:05:07,625 because we only add valid boards to the tree, we immediately throw out invalid 69 00:05:07,625 --> 00:05:10,200 boards. So if we come to a full board, we know 70 00:05:10,200 --> 00:05:13,555 it's valid, that's the solution. Yay, we produced that. 71 00:05:13,555 --> 00:05:18,505 So we're going to generate the tree and keep walking down the branches. 72 00:05:18,505 --> 00:05:24,100 Sometimes backtracking by producing false and, hopefully, at some point finding the 73 00:05:24,100 --> 00:05:27,570 answer we want. So the key thing to take away from this 74 00:05:27,570 --> 00:05:34,840 idea of the search intuition is, in our terminology and what we understand from 75 00:05:34,840 --> 00:05:39,310 systematic program design, if somebody says, hey, this is the thing I want you 76 00:05:39,310 --> 00:05:43,175 to do. We say, oh, yeah, that has three crucial 77 00:05:43,175 --> 00:05:46,234 aspects. It's a generative recursion. 78 00:05:46,234 --> 00:05:50,182 It's a recursion over an arbitrary-arity tree. 79 00:05:51,330 --> 00:05:55,160 And actually we're doing backtracking search over it. 80 00:05:55,160 --> 00:05:58,870 Now what I'll say to you is you know how to do those three things already. 81 00:05:58,870 --> 00:06:04,330 In the next video, I'm going to show you how to combine them and then the hard 82 00:06:04,330 --> 00:06:08,584 part of Sudoku is done.