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.