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]