In this video, I want to lay out the 
search intuition. 
The basic idea that's going to underlie 
our Sudoku board solver. 
As I said before, the basic idea is we're 
going to take an initial Sudoku board And 
we're going to generate a tree of all the 
possible boards that follow from it, 
looking for a solution. 
Now, that may seem surprising, when you 
look at a Sudoku board on paper, it 
doesn't look like a tree. 
And as we saw, our representation of the 
board is just a single, flat list, so 
there's no tree there. 
So where's the tree? 
Well we're going to generate the tree. 
It's going to be a generative recursion. 
Here we go. 
Imagine that you start with a board, and 
here I'm just kind of showing the upper 
left part of the board. 
So imagine that you start with a board 
that has some squares filled in. 
Kind of like a Sudoku puzzle you might 
see in the newspaper. 
You may remember newspapers are things 
printed on paper that come to your 
doorstep in the morning. 
So you might see it on your phone or 
something. 
But here is the upper left part of a 
Sudoku puzzle. 
So you want to find a solution to that 
problem. 
Or maybe find out that the board's not 
solvable. 
What could you do? 
Well, the idea behind root for search is, 
here's the first empty square. 
That's the first place where there's not 
a number. 
What if I take that square and I fill it 
in with all possible values? 
That gives me nine possible next boards, 
because I basically fill the empty square 
with 1, 2, 3, 4, 5, 6, 7, 8, 9. 
Now of course some of those boards are 
immediately invalid. 
Right? 
The second board is invalid because that 
gives you two 2's in the same row. 
So we can cross that one out right away. 
And the third board is invalid because it 
gives you two 4's in the same row. 
And the fifth board is invalid because it 
gives you two 5's in the same box. 
So we can kind of immediately rule out 
the invalid boards. 
And in this case, that leaves us with 
just six next boards. 
So now what do we do? 
Well, none of those boards is a complete 
solution, right, because none of those 
boards has no empty spaces. 
Then we just do the same thing again. 
We find the next empty square, we fill it 
in with the nine possible values and we 
prune. 
Now we've got some more empty boards. 
Now, what's going on here? 
What are we doing? 
What I want to say to you is that there's 
three crucial aspects to what's going on 
here. 
We are generating an arbitrary-arity tree 
and we're doing a backtracking search 
over it. 
Those are the three things. 
Let me explain them in turn. 
First, the generation. 
Well, the generation is straightforward. 
This second row of boards here, this 
second row of boards, those are new 
boards. 
Those boards aren't some subpart of the 
first board. 
We didn't take the rest of the first 
board to get those boards. 
The rest of the first board is just a 
list 80 elements long. 
We need to generate these new boards, so 
that's why this is generation. 
And because it's generation, we can start 
to think generative recursion. 
Generative recursion template probably 
plays along in here. 
Now arbitrary-arity, the reason I'm 
saying it's an arbitary-arity tree is 
that each board has 0 to 9 valid 
children, 0 to 9 valid next boards. 
Okay? 
Because for each board, we take the first 
empty square. 
We fill it in with the nine possible 
values, 1 to 9, and then we prune the 
invalid ones. 
So there could be up to nine valid 
children, that's why it's an 
arbitrary-arity tree. 
And we're doing a backtracking search 
over it. 
Well, the reason we're doing a 
backtracking search is just we're 
going to keep exploring this tree until 
we come to a board that has no valid next 
board. 
That's a board with no children. 
And what do we usually do when we're 
searching for something and we wind up no 
where. 
And we produce false. 
That's the idea of backtracking. 
When you get to looking for something in 
nothing, you're in trouble. 
So you produce false. 
Or we're going to come to a board that's 
full. 
And because of the way that we're 
producing the tree, because of the way 
we're generating the tree where we 
immediately throw out invalid boards, if 
we come to a board that's full, then it's 
a solution. 
because we only add valid boards to the 
tree, we immediately throw out invalid 
boards. 
So if we come to a full board, we know 
it's valid, that's the solution. 
Yay, we produced that. 
So we're going to generate the tree and 
keep walking down the branches. 
Sometimes backtracking by producing false 
and, hopefully, at some point finding the 
answer we want. 
So the key thing to take away from this 
idea of the search intuition is, in our 
terminology and what we understand from 
systematic program design, if somebody 
says, hey, this is the thing I want you 
to do. 
We say, oh, yeah, that has three crucial 
aspects. 
It's a generative recursion. 
It's a recursion over an arbitrary-arity 
tree. 
And actually we're doing backtracking 
search over it. 
Now what I'll say to you is you know how 
to do those three things already. 
In the next video, I'm going to show you 
how to combine them and then the hard 
part of Sudoku is done.