1
00:00:06,110 --> 00:00:10,010
In this video, I'm going to show you 
really the only new design technique 

2
00:00:10,010 --> 00:00:12,210
we're going to need for the Sudoku 
solver. 

3
00:00:12,210 --> 00:00:15,600
It's a technique called template 
blending. 

4
00:00:17,220 --> 00:00:21,010
Now once we have this, a whole lot's 
going to happen in this video, and it's 

5
00:00:21,010 --> 00:00:24,850
going to happen fast, because what we're 
going to see is we're going to take the 

6
00:00:24,850 --> 00:00:30,020
idea from the last video, where we saw 
that there were three things going on in 

7
00:00:30,020 --> 00:00:34,182
the Sudoku solver. 
There was generative recursion, an 

8
00:00:34,182 --> 00:00:37,920
arbitrary arity tree, and backtracking 
search. 

9
00:00:37,920 --> 00:00:40,800
And we're going to take those 3 templates 
and combine them together. 

10
00:00:42,180 --> 00:00:47,370
Things are going to go pretty quick. 
Now as we do this, we're going to step 

11
00:00:47,370 --> 00:00:50,510
back a little bit from the way we've 
talked about templates before. 

12
00:00:50,510 --> 00:00:55,355
We're going to relax them a little bit. 
But the fundamental idea underlying 

13
00:00:55,355 --> 00:01:00,220
templates isn't going to change at all. 
because what templates have always been 

14
00:01:00,220 --> 00:01:06,630
from day one is they were the answer to a 
very simple question, which is, given 

15
00:01:06,630 --> 00:01:10,650
what I know about what this function 
consumes and what it produces and 

16
00:01:10,650 --> 00:01:17,470
basically what it does, how much do I 
know about the form of a function before 

17
00:01:17,470 --> 00:01:21,540
I start on the details? 
Templates have always been that, they've 

18
00:01:21,540 --> 00:01:24,790
been the outline or the backbone or the 
sketch of the function. 

19
00:01:26,030 --> 00:01:29,390
And they're going to be that here too, 
but in order to put three of them 

20
00:01:29,390 --> 00:01:34,328
together, we have to relax just a little 
bit to make that work Here we go. 

21
00:01:34,328 --> 00:01:38,336
Now I'm in Sudoku starter. 
You've seen this before. 

22
00:01:38,336 --> 00:01:43,980
You've seen all the data definitions. 
If that was perhaps a little while ago, I 

23
00:01:43,980 --> 00:01:47,530
encourage you to pause this video, and 
just take a quick look over the data 

24
00:01:47,530 --> 00:01:51,490
definitions in the starter. 
But here we go. 

25
00:01:51,490 --> 00:01:56,340
I'm going to go down to Functions. 
And we want to design a function here to 

26
00:01:56,340 --> 00:02:01,110
take a given sudoku board and either 
solve it or say that it can't be solved. 

27
00:02:01,110 --> 00:02:05,929
It's a backtracking search function. 
So the signature is that it's going to 

28
00:02:05,929 --> 00:02:08,213
consume a board. 
And remember. 

29
00:02:09,330 --> 00:02:14,660
Remember what the method does. 
Oh, this solving a sudoku board seems big 

30
00:02:14,660 --> 00:02:19,151
and hard. 
But by focusing on the first step of the 

31
00:02:19,151 --> 00:02:22,070
HTDF recipe, I know what to type right 
now. 

32
00:02:22,070 --> 00:02:24,140
I need the signature of the function that 
does it. 

33
00:02:24,140 --> 00:02:33,140
And it consumes a board and it produces 
either a board, if it Finds a solution or 

34
00:02:33,140 --> 00:02:36,440
false if it fails. 
That's the standard signature of a 

35
00:02:36,440 --> 00:02:45,077
backtracking function. 
And we say that it produces a solution 

36
00:02:45,077 --> 00:02:55,180
for board or false if board is 
unsolvable. 

37
00:02:55,180 --> 00:02:58,440
And we're going to add one more thing 
because the sudoku problems that you get 

38
00:02:58,440 --> 00:03:02,610
in the paper always start out at least 
being reasonable. 

39
00:03:02,610 --> 00:03:05,540
They, they always have no contradictions 
in them. 

40
00:03:05,540 --> 00:03:11,050
So we'll say that the board we start with 
is valid. 

41
00:03:11,050 --> 00:03:19,726
It has no invalid entries in it. 
Alright, well let's do a stub. 

42
00:03:19,726 --> 00:03:24,425
Solve boards, and we'll just say false 
because it's the easiest thing to say. 

43
00:03:24,425 --> 00:03:31,850
And now let's do some check expects. 
Well, there's not a simple base case here 

44
00:03:31,850 --> 00:03:35,630
unless maybe we give an already solved 
board as a base case. 

45
00:03:36,900 --> 00:03:40,610
Here it's a little bit tougher to sort of 
think about what to do first. 

46
00:03:40,610 --> 00:03:44,116
But I've got some example boards above so 
I'm just going to use them. 

47
00:03:44,116 --> 00:03:53,735
Check expect solve board four while the 
solution of board four is board four 

48
00:03:53,735 --> 00:03:59,490
solution. 
In the solution for board five is board 

49
00:03:59,490 --> 00:04:11,490
five solution And board 7 is unsolvable, 
so do some check expects. 

50
00:04:11,490 --> 00:04:17,853
Now, let's template. 
Now, what's going on here? 

51
00:04:17,853 --> 00:04:23,730
Remember what we learned in the last 
video. 

52
00:04:23,730 --> 00:04:27,560
We're going to generate an 
arbitrary-arity tree and as we generate 

53
00:04:27,560 --> 00:04:29,700
it we're going to do a backtracking 
search over it. 

54
00:04:29,700 --> 00:04:35,493
There's 3 things involved. 
So the answer to the question, hey, what 

55
00:04:35,493 --> 00:04:39,730
do I know about the basic shape of this 
function before I get down to the 

56
00:04:39,730 --> 00:04:43,676
details? 
Is I know three things, I know that it's 

57
00:04:43,676 --> 00:04:48,312
going to include elements of the template 
for generative recursion, elements of the 

58
00:04:48,312 --> 00:04:52,410
template for an arbitrary-arity tree, and 
elements of the template for backtracking 

59
00:04:52,410 --> 00:04:56,774
search. 
Let me start with arbitrary-arity tree In 

60
00:04:56,774 --> 00:05:02,470
an arbitrary-arity tree, you got nodes in 
the tree, and then lists of nodes. 

61
00:05:02,470 --> 00:05:06,255
Because there's nodes and their children. 
So that's going to be two mutually 

62
00:05:06,255 --> 00:05:11,640
recursive functions. 
I'm going to wrap them in a local. 

63
00:05:11,640 --> 00:05:14,330
So local. 
They'll be two functions in here, and 

64
00:05:14,330 --> 00:05:17,300
then there be a tree /g. 
Trampoline that calls the first function. 

65
00:05:17,300 --> 00:05:20,450
So let's template the first function. 
This is going to be the function that 

66
00:05:20,450 --> 00:05:27,800
operates on a single board, so, let's 
see, we'll call it solve dash dash board. 

67
00:05:27,800 --> 00:05:29,840
It operates on a single board. 
Now, look. 

68
00:05:29,840 --> 00:05:34,563
I'm working a bit from memory here. 
I don't have typed comments for an 

69
00:05:34,563 --> 00:05:37,350
arbitrary-arity tree. 
Okay? 

70
00:05:37,350 --> 00:05:42,380
But I'm remembering that the way an 
arbitrar-arity tree works is it's node, 

71
00:05:42,380 --> 00:05:47,480
in this case board, and list of board. 
So I'm templating that from memory. 

72
00:05:47,480 --> 00:05:52,626
So now, what happens here, well, what 
happens here is it's something like dot, 

73
00:05:52,626 --> 00:05:55,863
dot, dot. 
And then I'm going to do something with 

74
00:05:55,863 --> 00:06:03,340
the subs of the board. 
Okay so that'll be solved dash dash list 

75
00:06:03,340 --> 00:06:14,030
of board of board subs of board. 
Now that little selector I pretended 

76
00:06:14,030 --> 00:06:16,460
there to call board sub doesn't really 
exist. 

77
00:06:16,460 --> 00:06:21,645
I know that. 
Just hang on and then the other function 

78
00:06:21,645 --> 00:06:27,319
is going to be something like I'm 
templating still. 

79
00:06:27,319 --> 00:06:33,550
Solve-list of board, list of board. 
Cond, while the list is either empty. 

80
00:06:37,060 --> 00:06:41,290
In which case, dot dot dot. 
Or it's not empty in which case what? 

81
00:06:41,290 --> 00:06:48,720
Well, it's just the usual template for 
operating on a list of X. 

82
00:06:48,720 --> 00:07:01,730
Dot, dot, dot first lobd except that's a 
board and then rest lobd except that's a 

83
00:07:01,730 --> 00:07:09,210
list of board so this first lobd is the 
reference rule that's going to make be 

84
00:07:09,210 --> 00:07:22,090
call back to solve dash board [NOISE]. 
And rest lobd is list of board, so that's 

85
00:07:22,090 --> 00:07:28,190
a self reference. 
Solve dash dash lobd, and I didn't quite 

86
00:07:28,190 --> 00:07:32,241
name this function right. 
Let me just get my friends first. 

87
00:07:32,241 --> 00:07:42,270
And this should be dash dash lobd. 
I need the trampoline to start the whole 

88
00:07:42,270 --> 00:07:45,110
thing out. 
We originally call it with a board. 

89
00:07:45,110 --> 00:07:49,484
So the trampoline is going to say solve 
dash dash board of the board. 

90
00:07:49,484 --> 00:07:55,070
So again that's templated according to 
the arbitrary-arity tree but that's not 

91
00:07:55,070 --> 00:07:58,488
the only thing that's going on. 
There's also genetive recursion going on. 

92
00:07:59,830 --> 00:08:05,930
And where the generative recursion comes 
in is, there is no structure selector for 

93
00:08:05,930 --> 00:08:12,288
going from a board to a its children. 
Those have to be generated. 

94
00:08:13,680 --> 00:08:17,482
So just to accentuate in my mind the fact 
that these are generated rather than a 

95
00:08:17,482 --> 00:08:22,510
structure selector, I'm going to use a 
different name for this. 

96
00:08:22,510 --> 00:08:28,790
I'm going to called it next boards. 
To me that reminds me of the fact that 

97
00:08:28,790 --> 00:08:33,660
I'm using the generate recursion template 
also involves something else. 

98
00:08:33,660 --> 00:08:35,679
This is where it generates the next 
boards. 

99
00:08:37,770 --> 00:08:42,980
But if I go over to the generative 
recursion recipe page, you'll see that 

100
00:08:42,980 --> 00:08:46,850
I've gotta do something else here. 
And here's the next problem. 

101
00:08:46,850 --> 00:08:52,200
That's why I named that function next 
boards, but I've got to test, am I done? 

102
00:08:52,200 --> 00:08:55,720
I've gotta do the trivial test. 
So that's what this if is and this is 

103
00:08:55,720 --> 00:09:04,090
going to be the trivial test. 
In going, jumping back again, if the 

104
00:09:04,090 --> 00:09:06,302
trivial test is true, I do the trivial 
answer. 

105
00:09:06,302 --> 00:09:16,110
But just as I picked a better name for 
next boards, let me pick better names for 

106
00:09:16,110 --> 00:09:19,120
these two. 
What is the trivial test. 

107
00:09:19,120 --> 00:09:24,140
How do I know I'm done? 
Now remember we're only putting valid 

108
00:09:24,140 --> 00:09:27,210
boards in the tree. 
Right, because we talked about we're 

109
00:09:27,210 --> 00:09:32,160
going to throw out the invalid boards. 
So we're done if we ever get to a board 

110
00:09:32,160 --> 00:09:35,110
that's full. 
Because every board we leave in the tree 

111
00:09:35,110 --> 00:09:38,385
is valid, so if it's full it's actually a 
solution. 

112
00:09:38,385 --> 00:09:47,731
So this really is a predicate like, it 
could be called solved or it could be 

113
00:09:47,731 --> 00:09:48,460
called full. 
Okay. 

114
00:09:48,460 --> 00:09:53,445
I'll call it solved, somehow that's a 
better name. 

115
00:09:53,445 --> 00:09:59,490
If a board is solved, then what do I do? 
Well then the trivial answer is even more 

116
00:09:59,490 --> 00:10:03,330
trivial than this. 
The trivial answer is just to produce the 

117
00:10:03,330 --> 00:10:05,696
board. 
I'm still templating, I'm still 

118
00:10:05,696 --> 00:10:10,390
templating, but I'm doing a little bit 
more than templating, because I 

119
00:10:10,390 --> 00:10:14,798
simplified that call to trivial answer 
and I picked a better name for solved. 

120
00:10:14,798 --> 00:10:18,085
So, I'm a little bit more than 
templating. 

121
00:10:19,100 --> 00:10:24,420
So now, look at what I've got. 
I've got arbitrary-arity tree traversal, 

122
00:10:24,420 --> 00:10:30,449
here I'm kind of underlining that part in 
blue, and I've also got the generative 

123
00:10:30,449 --> 00:10:34,820
incursion template. 
I'm underlining that in red. 

124
00:10:34,820 --> 00:10:39,690
I still have to do the back tracking 
search Well what do we have to do for the 

125
00:10:39,690 --> 00:10:43,630
backtracking search part of it? 
Well I'll jump back over to the design 

126
00:10:43,630 --> 00:10:49,180
recipes page. 
And lets see I'll go to Design Recipes 

127
00:10:49,180 --> 00:10:56,090
and I'll go to backtracking search. 
And lets see the second version of it is 

128
00:10:56,090 --> 00:11:04,578
the one we use when we've got Local. 
And basically what backtracking means is 

129
00:11:04,578 --> 00:11:10,590
when we fail we produce false, and we 
first try the first child. 

130
00:11:12,580 --> 00:11:14,840
And if the first child succeeds we 
produce that. 

131
00:11:14,840 --> 00:11:19,000
Otherwise, we try the next child. 
So I'll go put that behavior into the 

132
00:11:19,000 --> 00:11:24,224
template we've been building up. 
If we run out of choices, we're going to 

133
00:11:24,224 --> 00:11:29,116
produce false. 
Otherwise, what are we going to do? 

134
00:11:29,116 --> 00:11:36,870
Well, this thing. 
Here, I'll pick that up. 

135
00:11:36,870 --> 00:11:42,267
We're going to say, local define try, 
that thing. 

136
00:11:42,267 --> 00:11:57,880
So that means go try the first child. 
And if that's not false, produce it, 

137
00:11:57,880 --> 00:12:05,730
otherwise, try the next child. 
And I have to add one more paren here. 

138
00:12:07,950 --> 00:12:13,350
So there we go. 
What I've done is to take the idea that 

139
00:12:13,350 --> 00:12:20,950
the way we're going to solve Sudoku is to 
generate an arbitrary arity tree by for 

140
00:12:20,950 --> 00:12:23,860
each board, finding the valid next 
boards. 

141
00:12:26,450 --> 00:12:28,720
And throwing out immediately the invalid 
ones. 

142
00:12:30,670 --> 00:12:33,905
And we'll just do a backtracking tree as 
we go. 

143
00:12:33,905 --> 00:12:42,380
And if we ever come to a full board, a 
board that is solved, we're done. 

144
00:12:42,380 --> 00:12:46,290
And every time we fail, every time we run 
out of choices, we produce false. 

145
00:12:48,240 --> 00:12:54,490
That's the core of the Sudoku solver, and 
the key thing that I did here, the one 

146
00:12:54,490 --> 00:12:57,430
thing that we have never quiet done 
before, but we have been building up to. 

147
00:12:57,430 --> 00:13:04,720
Is I relaxed the notional template just a 
little bit to really what its always been 

148
00:13:04,720 --> 00:13:09,640
all along, which is the template is the 
answer to the question. 

149
00:13:09,640 --> 00:13:17,030
What do I know about the core of this 
function before I get to the details? 

150
00:13:19,620 --> 00:13:24,020
And in this case, that took me almost all 
the way. 

151
00:13:24,020 --> 00:13:27,740
Now, we're not quite done here. 
I did wish for two things. 

152
00:13:27,740 --> 00:13:31,546
I wished for this function solved 
question mark, which was what the 

153
00:13:31,546 --> 00:13:36,616
generative recursion template called 
Trival question mark. 

154
00:13:36,616 --> 00:13:42,210
And I wished, for next boards, which was 
what the generative recursion template 

155
00:13:42,210 --> 00:13:47,620
called Next Problem. 
So this really is just the template. 

156
00:13:47,620 --> 00:13:51,240
I just gave things a slightly better 
name, and I'm going to need wish list 

157
00:13:51,240 --> 00:13:53,790
entries for these. 
And we're going to do that in the next 

158
00:13:53,790 --> 00:13:54,160
video. 
[BLANK_AUDIO]