In this video, I'm going to show you really the only new design technique
we're going to need for the Sudoku solver.
It's a technique called template blending.
Now once we have this, a whole lot's going to happen in this video, and it's
going to happen fast, because what we're going to see is we're going to take the
idea from the last video, where we saw that there were three things going on in
the Sudoku solver. There was generative recursion, an
arbitrary arity tree, and backtracking search.
And we're going to take those 3 templates and combine them together.
Things are going to go pretty quick. Now as we do this, we're going to step
back a little bit from the way we've talked about templates before.
We're going to relax them a little bit. But the fundamental idea underlying
templates isn't going to change at all. because what templates have always been
from day one is they were the answer to a very simple question, which is, given
what I know about what this function consumes and what it produces and
basically what it does, how much do I know about the form of a function before
I start on the details? Templates have always been that, they've
been the outline or the backbone or the sketch of the function.
And they're going to be that here too, but in order to put three of them
together, we have to relax just a little bit to make that work Here we go.
Now I'm in Sudoku starter. You've seen this before.
You've seen all the data definitions. If that was perhaps a little while ago, I
encourage you to pause this video, and just take a quick look over the data
definitions in the starter. But here we go.
I'm going to go down to Functions. And we want to design a function here to
take a given sudoku board and either solve it or say that it can't be solved.
It's a backtracking search function. So the signature is that it's going to
consume a board. And remember.
Remember what the method does. Oh, this solving a sudoku board seems big
and hard. But by focusing on the first step of the
HTDF recipe, I know what to type right now.
I need the signature of the function that does it.
And it consumes a board and it produces either a board, if it Finds a solution or
false if it fails. That's the standard signature of a
backtracking function. And we say that it produces a solution
for board or false if board is unsolvable.
And we're going to add one more thing because the sudoku problems that you get
in the paper always start out at least being reasonable.
They, they always have no contradictions in them.
So we'll say that the board we start with is valid.
It has no invalid entries in it. Alright, well let's do a stub.
Solve boards, and we'll just say false because it's the easiest thing to say.
And now let's do some check expects. Well, there's not a simple base case here
unless maybe we give an already solved board as a base case.
Here it's a little bit tougher to sort of think about what to do first.
But I've got some example boards above so I'm just going to use them.
Check expect solve board four while the solution of board four is board four
solution. In the solution for board five is board
five solution And board 7 is unsolvable, so do some check expects.
Now, let's template. Now, what's going on here?
Remember what we learned in the last video.
We're going to generate an arbitrary-arity tree and as we generate
it we're going to do a backtracking search over it.
There's 3 things involved. So the answer to the question, hey, what
do I know about the basic shape of this function before I get down to the
details? Is I know three things, I know that it's
going to include elements of the template for generative recursion, elements of the
template for an arbitrary-arity tree, and elements of the template for backtracking
search. Let me start with arbitrary-arity tree In
an arbitrary-arity tree, you got nodes in the tree, and then lists of nodes.
Because there's nodes and their children. So that's going to be two mutually
recursive functions. I'm going to wrap them in a local.
So local. They'll be two functions in here, and
then there be a tree /g. Trampoline that calls the first function.
So let's template the first function. This is going to be the function that
operates on a single board, so, let's see, we'll call it solve dash dash board.
It operates on a single board. Now, look.
I'm working a bit from memory here. I don't have typed comments for an
arbitrary-arity tree. Okay?
But I'm remembering that the way an arbitrar-arity tree works is it's node,
in this case board, and list of board. So I'm templating that from memory.
So now, what happens here, well, what happens here is it's something like dot,
dot, dot. And then I'm going to do something with
the subs of the board. Okay so that'll be solved dash dash list
of board of board subs of board. Now that little selector I pretended
there to call board sub doesn't really exist.
I know that. Just hang on and then the other function
is going to be something like I'm templating still.
Solve-list of board, list of board. Cond, while the list is either empty.
In which case, dot dot dot. Or it's not empty in which case what?
Well, it's just the usual template for operating on a list of X.
Dot, dot, dot first lobd except that's a board and then rest lobd except that's a
list of board so this first lobd is the reference rule that's going to make be
call back to solve dash board [NOISE]. And rest lobd is list of board, so that's
a self reference. Solve dash dash lobd, and I didn't quite
name this function right. Let me just get my friends first.
And this should be dash dash lobd. I need the trampoline to start the whole
thing out. We originally call it with a board.
So the trampoline is going to say solve dash dash board of the board.
So again that's templated according to the arbitrary-arity tree but that's not
the only thing that's going on. There's also genetive recursion going on.
And where the generative recursion comes in is, there is no structure selector for
going from a board to a its children. Those have to be generated.
So just to accentuate in my mind the fact that these are generated rather than a
structure selector, I'm going to use a different name for this.
I'm going to called it next boards. To me that reminds me of the fact that
I'm using the generate recursion template also involves something else.
This is where it generates the next boards.
But if I go over to the generative recursion recipe page, you'll see that
I've gotta do something else here. And here's the next problem.
That's why I named that function next boards, but I've got to test, am I done?
I've gotta do the trivial test. So that's what this if is and this is
going to be the trivial test. In going, jumping back again, if the
trivial test is true, I do the trivial answer.
But just as I picked a better name for next boards, let me pick better names for
these two. What is the trivial test.
How do I know I'm done? Now remember we're only putting valid
boards in the tree. Right, because we talked about we're
going to throw out the invalid boards. So we're done if we ever get to a board
that's full. Because every board we leave in the tree
is valid, so if it's full it's actually a solution.
So this really is a predicate like, it could be called solved or it could be
called full. Okay.
I'll call it solved, somehow that's a better name.
If a board is solved, then what do I do? Well then the trivial answer is even more
trivial than this. The trivial answer is just to produce the
board. I'm still templating, I'm still
templating, but I'm doing a little bit more than templating, because I
simplified that call to trivial answer and I picked a better name for solved.
So, I'm a little bit more than templating.
So now, look at what I've got. I've got arbitrary-arity tree traversal,
here I'm kind of underlining that part in blue, and I've also got the generative
incursion template. I'm underlining that in red.
I still have to do the back tracking search Well what do we have to do for the
backtracking search part of it? Well I'll jump back over to the design
recipes page. And lets see I'll go to Design Recipes
and I'll go to backtracking search. And lets see the second version of it is
the one we use when we've got Local. And basically what backtracking means is
when we fail we produce false, and we first try the first child.
And if the first child succeeds we produce that.
Otherwise, we try the next child. So I'll go put that behavior into the
template we've been building up. If we run out of choices, we're going to
produce false. Otherwise, what are we going to do?
Well, this thing. Here, I'll pick that up.
We're going to say, local define try, that thing.
So that means go try the first child. And if that's not false, produce it,
otherwise, try the next child. And I have to add one more paren here.
So there we go. What I've done is to take the idea that
the way we're going to solve Sudoku is to generate an arbitrary arity tree by for
each board, finding the valid next boards.
And throwing out immediately the invalid ones.
And we'll just do a backtracking tree as we go.
And if we ever come to a full board, a board that is solved, we're done.
And every time we fail, every time we run out of choices, we produce false.
That's the core of the Sudoku solver, and the key thing that I did here, the one
thing that we have never quiet done before, but we have been building up to.
Is I relaxed the notional template just a little bit to really what its always been
all along, which is the template is the answer to the question.
What do I know about the core of this function before I get to the details?
And in this case, that took me almost all the way.
Now, we're not quite done here. I did wish for two things.
I wished for this function solved question mark, which was what the
generative recursion template called Trival question mark.
And I wished, for next boards, which was what the generative recursion template
called Next Problem. So this really is just the template.
I just gave things a slightly better name, and I'm going to need wish list
entries for these. And we're going to do that in the next
video. [BLANK_AUDIO]