1
00:00:00,000 --> 00:00:11,000


2
00:00:11,000 --> 00:00:14,000
This presentation is delivered by the Stanford Center for Professional Development.

3
00:00:23,000 --> 00:00:27,000
Today I'm gonna keep talking a little bit more about another procedural 
recursion example and 

4
00:00:27,000 --> 00:00:31,000
then go on to talk about, kind of, 
the approach for recursive backtracking, 


5
00:00:31,000 --> 00:00:36,000
which is taking those procedural recursion examples and kind of twisting them around and doing new things with them. Okay. 

6
00:00:36,000 --> 00:00:39,000
This is the last problem I did at the end of 

7
00:00:39,000 --> 00:00:42,000
Wednesday's lecture. It's a very, very important problem, so I don't actually 

8
00:00:42,000 --> 00:00:46,000
want to move away from it until I feel that I'm getting some signs from you 

9
00:00:46,000 --> 00:00:47,000
guys that we're 

10
00:00:47,000 --> 00:00:49,000


11
00:00:49,000 --> 00:00:51,000
getting some understanding of this because it turns out it forms the basis of a lot of 

12
00:00:51,000 --> 00:00:55,000
other solutions end up just becoming permutations, you know, at the core of it. 

13
00:00:55,000 --> 00:00:56,000
So it's 

14
00:00:56,000 --> 00:01:01,000
a pretty useful pattern to have [inaudible] 

15
00:01:01,000 --> 00:01:05,000
list the permutations of a string. So you've got the string, you know, A B C D, and it's 

16
00:01:05,000 --> 00:01:07,000
gonna print all the A C D A B C D 

17
00:01:07,000 --> 00:01:12,000
A variations that you can get by rearranging all the letters. 

18
00:01:12,000 --> 00:01:15,000
It's a deceptively short piece of 

19
00:01:15,000 --> 00:01:17,000
code that does what's being done here 

20
00:01:17,000 --> 00:01:20,000
-is that it breaks it down in terms of there being the permutation that's 

21
00:01:20,000 --> 00:01:24,000
assembled so far, and then the remaining characters that haven't yet been looked 

22
00:01:24,000 --> 00:01:25,000
at, and so 

23
00:01:25,000 --> 00:01:27,000
at each recursive call it's gonna 

24
00:01:27,000 --> 00:01:30,000
shuffle one character from the 

25
00:01:30,000 --> 00:01:33,000
remainder onto the thing that's been chosen so far. So chose the next 

26
00:01:33,000 --> 00:01:37,000
character in the permutation, and eventually, when the rest is empty, 

27
00:01:37,000 --> 00:01:41,000
then all of the characters have been moved over, and have been laid down in 

28
00:01:41,000 --> 00:01:44,000
permutation, then what I have is a full permutation of the length end. 

29
00:01:44,000 --> 00:01:48,000
In the case where rest is not empty, I've still got some choices to make. The number of 

30
00:01:48,000 --> 00:01:52,000
choices is exactly equal to the number of characters I have left in 

31
00:01:52,000 --> 00:01:53,000
rest, 

32
00:01:53,000 --> 00:01:55,000
and for each of the remaining characters at this point, maybe there's just C 

33
00:01:55,000 --> 00:01:56,000
and D left, 

34
00:01:56,000 --> 00:01:58,000
then I'm gonna try each of them 

35
00:01:58,000 --> 00:02:03,000
as the next character in the permutation, and then permute what remains after 

36
00:02:03,000 --> 00:02:04,000
having made that choice. 

37
00:02:04,000 --> 00:02:05,000
And so this is 

38
00:02:05,000 --> 00:02:07,000
[inaudible] operations here of 

39
00:02:07,000 --> 00:02:09,000
attaching that [inaudible] 

40
00:02:09,000 --> 00:02:13,000
into the existing so far, and then subtracting it 

41
00:02:13,000 --> 00:02:14,000
out of the rest 

42
00:02:14,000 --> 00:02:18,000
to set up the arguments for that recursive call. A 

43
00:02:18,000 --> 00:02:21,000
little bit at the end we talked about this idea of a wrapper function where 

44
00:02:21,000 --> 00:02:24,000
the interface to list permutations from a client point of view probably just wants to 

45
00:02:24,000 --> 00:02:26,000
be, here's a string to permute 

46
00:02:26,000 --> 00:02:27,000
the fact that [inaudible] 

47
00:02:27,000 --> 00:02:31,000
keep this housekeeping of what I've built so far is really any internal management 

48
00:02:31,000 --> 00:02:34,000
issue, and isn't what I want to expose as part of the interface, 

49
00:02:34,000 --> 00:02:37,000
so we in turn have just a really simple one line translation that the outer 

50
00:02:37,000 --> 00:02:40,000
call just sets up and makes the call to the real recursive function setting up 

51
00:02:40,000 --> 00:02:44,000
the right state for the housekeeping in this case, which is the 

52
00:02:44,000 --> 00:02:47,000
permutation we've assembled at this point. 

53
00:02:47,000 --> 00:02:50,000
So 

54
00:02:50,000 --> 00:02:53,000
I'd like to ask you a few questions about this 

55
00:02:53,000 --> 00:02:56,000
to see if we're kind of seeing the same things. Can 

56
00:02:56,000 --> 00:03:00,000
someone tell me what is the first permutation that's printed by this 

57
00:03:00,000 --> 00:03:14,000
if I put in the string A B C D? 

58
00:03:14,000 --> 00:03:17,000
Anyone want to help me? 

59
00:03:17,000 --> 00:03:21,000
A B C D. A B C D. So the exact string I gave it, right, is the one that it picks, right, 

60
00:03:21,000 --> 00:03:23,000
the very first time, and that's because, 

61
00:03:23,000 --> 00:03:26,000
if you look at the way the for loop is structured, the idea is that it's gonna make a 

62
00:03:26,000 --> 00:03:29,000
choice and it's gonna move through the recursion. Well, the choice it always makes is to take 

63
00:03:29,000 --> 00:03:32,000
the next character of rest and attach it to the permutation 

64
00:03:32,000 --> 00:03:36,000
as its first time through the for loop. So the first time through the very first 

65
00:03:36,000 --> 00:03:38,000
for loop it's got A B C D to chose, it chooses A, 

66
00:03:38,000 --> 00:03:43,000
and now it recurs on A in the permutation and B C D to go. Well, the 

67
00:03:43,000 --> 00:03:46,000
next call does exactly the same thing, chooses the first of what remains, which 

68
00:03:46,000 --> 00:03:49,000
is B, attaches it to the permutation and keeps going. 

69
00:03:49,000 --> 00:03:50,000
So the kind of 

70
00:03:50,000 --> 00:03:53,000
deep arm of the recursion making that first choice and working its way down to 

71
00:03:53,000 --> 00:03:57,000
the base case, right, right remember the recursion always goes deep. It goes down to the end of 

72
00:03:57,000 --> 00:03:57,000
the 

73
00:03:57,000 --> 00:04:01,000
-and bottoms on the recursion before it comes back and revisits any previous 

74
00:04:01,000 --> 00:04:03,000
decision, will go A B C D, 

75
00:04:03,000 --> 00:04:04,000
and then 

76
00:04:04,000 --> 00:04:08,000
eventually come back and start trying other things, but that very first one, 

77
00:04:08,000 --> 00:04:11,000
right, is all just the sequence there. 

78
00:04:11,000 --> 00:04:13,000
The next one that's after it, right, 

79
00:04:13,000 --> 00:04:14,000
is A B D C, 

80
00:04:14,000 --> 00:04:17,000
which involved unmaking those last couple decisions. 

81
00:04:17,000 --> 00:04:19,000
If I look at 

82
00:04:19,000 --> 00:04:22,000
the tree that I have here that may help to sort of identify it. 

83
00:04:22,000 --> 00:04:24,000
That permute of emptying A B C, 

84
00:04:24,000 --> 00:04:27,000
the first choice it makes is go with A, and then the 

85
00:04:27,000 --> 00:04:30,000
first choice it makes here is go with B, and so on, so that the first thing that we can see 

86
00:04:30,000 --> 00:04:34,000
printed our here will be A B C D, we get to the base case. 

87
00:04:34,000 --> 00:04:36,000
Once it's tried this, it'll come back to this one, and on this 

88
00:04:36,000 --> 00:04:39,000
one it'll say, well, try the other characters. Well, there's no other 

89
00:04:39,000 --> 00:04:41,000
characters. In fact, this one also finishes. 

90
00:04:41,000 --> 00:04:46,000
It'll get back to here as it unwinds the stack the way the stack 

91
00:04:46,000 --> 00:04:49,000
gets back to where it was previously in these recursive calls. And now it says, okay, 

92
00:04:49,000 --> 00:04:51,000
and now try the ones that have, 

93
00:04:51,000 --> 00:04:54,000
on the second iteration of that for loop, D in the front, 

94
00:04:54,000 --> 00:04:56,000
and so it ends up putting A B D together, 

95
00:04:56,000 --> 00:04:58,000
leaving C, and then getting A B D C. And 

96
00:04:58,000 --> 00:05:02,000
then, so on kind of over here, the other variations, it will print all of the ones that have A 

97
00:05:02,000 --> 00:05:03,000
in the front. 

98
00:05:03,000 --> 00:05:06,000
There are eight of them. 

99
00:05:06,000 --> 00:05:07,000
I believe three, two 

100
00:05:07,000 --> 00:05:10,000
-no, six. Six of them 

101
00:05:10,000 --> 00:05:14,000
that have A in the front, and we'll do all of those. And only after having done all of 

102
00:05:14,000 --> 00:05:18,000
working out that whole part, which involves kind of the [inaudible] of this whole arm, 

103
00:05:18,000 --> 00:05:21,000
will eventually unwind back to the initial permute call, 

104
00:05:21,000 --> 00:05:22,000


105
00:05:22,000 --> 00:05:26,000
and then say, okay, now try again. Go with B in the front and work your way 

106
00:05:26,000 --> 00:05:28,000
down from reading the A C D behind it. 

107
00:05:28,000 --> 00:05:30,000
So we'll see all the As 

108
00:05:30,000 --> 00:05:33,000
then the bunch that lead with B, then the bunch that leads with C, and then finally the 

109
00:05:33,000 --> 00:05:36,000
bunch that leads with D. 

110
00:05:36,000 --> 00:05:39,000
It doesn't turn out -matter, actually, what order it visits them in because, in fact, all we 

111
00:05:39,000 --> 00:05:42,000
cared about was seeing all of them. But part of what I'm trying to get with you 

112
00:05:42,000 --> 00:05:44,000
is the sense of being 

113
00:05:44,000 --> 00:05:46,000
able to look at that recursive code, 

114
00:05:46,000 --> 00:05:50,000
and use your mind to kind of trace its activity and think about the 

115
00:05:50,000 --> 00:05:54,000
progress that is made through those recursive calls. Just 

116
00:05:54,000 --> 00:05:57,000
let me look at that code just for a second more and see if there's any else that I want to 

117
00:05:57,000 --> 00:05:59,000
highlight for you. 

118
00:05:59,000 --> 00:06:05,000


119
00:06:05,000 --> 00:06:08,000
I think that's about what 

120
00:06:08,000 --> 00:06:08,000
it's gonna do. 

121
00:06:08,000 --> 00:06:11,000
So if you don't understand this cost, if there's something about it that confuses you, now 

122
00:06:11,000 --> 00:06:15,000
would be an excellent time for you to ask a question that I could help 

123
00:06:15,000 --> 00:06:17,000
kind of get your understanding 

124
00:06:17,000 --> 00:06:19,000
made more clear. So 

125
00:06:19,000 --> 00:06:24,000
when you look at this code, you feel like you believe it works? You understand it? [Inaudible]. I have a question. 

126
00:06:24,000 --> 00:06:29,000
Is there a simple change you can make to this 

127
00:06:29,000 --> 00:06:29,000
code 

128
00:06:29,000 --> 00:06:32,000
so that it does combinations [inaudible]? 

129
00:06:32,000 --> 00:06:36,000
Does combinations -you mean, like, will skip letters? 

130
00:06:36,000 --> 00:06:42,000
Right. Yes. It turns out we're gonna make that change in not five minutes. 

131
00:06:42,000 --> 00:06:45,000
In effect, what you would do -and there's a pretty simple change with 

132
00:06:45,000 --> 00:06:47,000
this form. I'm gonna show you a slightly different way of doing it, 

133
00:06:47,000 --> 00:06:48,000
but one way of doing it would be to say, 

134
00:06:48,000 --> 00:06:52,000
well, give me the letter, don't attach it to next right? So right now, the 

135
00:06:52,000 --> 00:06:56,000
choices are pick one of the letters that remain and then attach it to 

136
00:06:56,000 --> 00:07:00,000
the permutation. Another option you could do was pick a letter and just discard it, 

137
00:07:00,000 --> 00:07:03,000
right? And so, in which case, I wouldn't add it into so far. 

138
00:07:03,000 --> 00:07:06,000
I would still subtract it from here, and I'd make another recursive call 

139
00:07:06,000 --> 00:07:07,000
saying, now 

140
00:07:07,000 --> 00:07:10,000
how about the permutations that don't involve A at all? And 

141
00:07:10,000 --> 00:07:14,000
I would just drop it from the thing and I would recurs on just the B C D part. So 

142
00:07:14,000 --> 00:07:17,000
a pretty simple change right here. I'm gonna show you there's a slightly different way to 

143
00:07:17,000 --> 00:07:21,000
formulate the same thing in a little bit, but 

144
00:07:21,000 --> 00:07:27,000
-anybody want to own up to having something that confuses them? [Inaudible] ask how you, like, 

145
00:07:27,000 --> 00:07:29,000
what you would set up to test it? 

146
00:07:29,000 --> 00:07:30,000
So [inaudible] one of 

147
00:07:30,000 --> 00:07:33,000
the, you know, the easiest thing to do here, and I have the code kind of actually sitting over 

148
00:07:33,000 --> 00:07:35,000
here just in case, right, 

149
00:07:35,000 --> 00:07:38,000
hoping you would 

150
00:07:38,000 --> 00:07:41,000
ask because right now I just have the most barebones sort of testing. It's like, yeah, what if I just, 

151
00:07:41,000 --> 00:07:44,000
you know, throw some strings at it and see what happens, right? 

152
00:07:44,000 --> 00:07:45,000
And so 

153
00:07:45,000 --> 00:07:49,000
the easiest strings to throw at it would be things like, well what happens if I give it the empty 

154
00:07:49,000 --> 00:07:49,000
string, 

155
00:07:49,000 --> 00:07:52,000
right? You know, so it takes some really simple cases to start because you want to see, well what happens 

156
00:07:52,000 --> 00:07:55,000
when, you know, you give it an empty input. Is it gonna blow up? And it's, like, the empty input, 

157
00:07:55,000 --> 00:07:58,000
right, immediately realizes there's no choices and it says, well, look, there's nothing to 

158
00:07:58,000 --> 00:08:00,000
print other than that empty string. 

159
00:08:00,000 --> 00:08:02,000
What if I give it a single character string? 

160
00:08:02,000 --> 00:08:04,000
Right? I get that string back. I'm like, 

161
00:08:04,000 --> 00:08:07,000
okay, gives me a little bit of inspiration that it made one recursive call, right, and then hit 

162
00:08:07,000 --> 00:08:09,000
the base case on the subsequent one. 

163
00:08:09,000 --> 00:08:12,000
Now I start doing better ones. A and B, 

164
00:08:12,000 --> 00:08:16,000
and I'm seeing A B B A. Okay, so I feel like, you know, I got this, so if I put a C in 

165
00:08:16,000 --> 00:08:17,000
the front, 

166
00:08:17,000 --> 00:08:20,000
and I put the B A behind, 

167
00:08:20,000 --> 00:08:21,000
then hopefully what I believe is that 

168
00:08:21,000 --> 00:08:24,000
it's gonna try, you know, C in the front, and then it's gonna permute A and B 

169
00:08:24,000 --> 00:08:27,000
behind it, and then similarly on down. 

170
00:08:27,000 --> 00:08:30,000
So some simple cases that I can see 

171
00:08:30,000 --> 00:08:34,000
verifying that it does produce, kind of, the input string as itself, and then it does the 

172
00:08:34,000 --> 00:08:37,000
back end rearrangement, leaving this in the front, and then it makes the next choice for what can 

173
00:08:37,000 --> 00:08:40,000
go in the front, and then the back end rearrangement. And kind of seeing the 

174
00:08:40,000 --> 00:08:44,000
pattern that matches my belief about how the code works, right, 

175
00:08:44,000 --> 00:08:45,000
helps me to feel good. What happens if I 

176
00:08:45,000 --> 00:08:48,000
put in 

177
00:08:48,000 --> 00:08:50,000
something that has double letters in it? 

178
00:08:50,000 --> 00:08:53,000
So I put A P P L E in there. 

179
00:08:53,000 --> 00:08:56,000
And all the way back at the beginning, right, I can 

180
00:08:56,000 --> 00:08:58,000
plot more of them, right, that grows quite 

181
00:08:58,000 --> 00:09:02,000
quickly right as we add more and more letters, right? Seeing the apple, appel, 

182
00:09:02,000 --> 00:09:02,000
and stuff like that. 

183
00:09:02,000 --> 00:09:05,000
There's a point where it starts picking the P to go in the front, 

184
00:09:05,000 --> 00:09:10,000
and the code as it's written, right, doesn't actually make it a combination for this P 

185
00:09:10,000 --> 00:09:11,000
and this P really being different. 

186
00:09:11,000 --> 00:09:13,000
So it goes through a whole sequence of 

187
00:09:13,000 --> 00:09:17,000
pull the second character to the front, and then permute the remaining four. 

188
00:09:17,000 --> 00:09:20,000
And then it says, and now pull the third character to the front and permute 

189
00:09:20,000 --> 00:09:22,000
the remaining four, which turns out to be exactly the same thing. So there should be 

190
00:09:22,000 --> 00:09:25,000
this whole sequence in the middle, right, 

191
00:09:25,000 --> 00:09:27,000
of the same Ps 

192
00:09:27,000 --> 00:09:29,000
repeated twice 

193
00:09:29,000 --> 00:09:31,000
because we haven't gone over a way to do anything about that, right? 

194
00:09:31,000 --> 00:09:33,000
So 

195
00:09:33,000 --> 00:09:36,000
-but it is reassuring to know that it did somehow didn't get, you know, confused by the idea of 

196
00:09:36,000 --> 00:09:38,000
there being two double letters. [Inaudible] if I do this -if I just say A 

197
00:09:38,000 --> 00:09:41,000
B A, right? 

198
00:09:41,000 --> 00:09:44,000
Something a little bit smaller to look at, right? 

199
00:09:44,000 --> 00:09:47,000
A in the front. A in the front goes permuted, B in the front, and then it ends up permuting 

200
00:09:47,000 --> 00:09:50,000
these two ways that ends up being exactly the same, and then I get a duplicate of those in 

201
00:09:50,000 --> 00:09:51,000
the front. 

202
00:09:51,000 --> 00:09:53,000
So right now, it doesn't know that there's anything to worry about in terms 

203
00:09:53,000 --> 00:09:55,000
of duplicates? 

204
00:09:55,000 --> 00:09:57,000
What's a really easy way to get rid of duplicates? 

205
00:09:57,000 --> 00:09:59,000
Don't think recursively, think -use a set. 

206
00:09:59,000 --> 00:10:01,000
Right? I could just stuff them in a set, right? 

207
00:10:01,000 --> 00:10:04,000
And then if it comes across the same one again it's like, yeah, 

208
00:10:04,000 --> 00:10:07,000
whatever. So it would still do the extra work of finding those down, 

209
00:10:07,000 --> 00:10:11,000
but would actually, like, I could print the set at the end having coalesced any of the duplicates. 

210
00:10:11,000 --> 00:10:13,000
To 

211
00:10:13,000 --> 00:10:15,000
actually change it in the code, 

212
00:10:15,000 --> 00:10:18,000
it's actually not that hard either. 

213
00:10:18,000 --> 00:10:19,000
The idea here is that 

214
00:10:19,000 --> 00:10:21,000
for all of the characters that remain, right, 

215
00:10:21,000 --> 00:10:25,000
and sometimes what I want to choose from is of the remaining characters 

216
00:10:25,000 --> 00:10:25,000
uniqued, 

217
00:10:25,000 --> 00:10:27,000
right? Pick one to move to the front. 

218
00:10:27,000 --> 00:10:29,000
So if there's three more Ps 

219
00:10:29,000 --> 00:10:31,000
that remain in rest, 

220
00:10:31,000 --> 00:10:34,000
I don't need to try each of those Ps individually in the front, right? They'll produce 

221
00:10:34,000 --> 00:10:37,000
the same result -pulling one and leaving the other two behind 

222
00:10:37,000 --> 00:10:39,000
is completely irrelevant. 

223
00:10:39,000 --> 00:10:42,000
So an easy way to actually stop it from even generating them, 

224
00:10:42,000 --> 00:10:46,000
is when looking at the character here is to make sure that it is -that it 

225
00:10:46,000 --> 00:10:50,000
doesn't duplicate anything else in the rest. And so 

226
00:10:50,000 --> 00:10:53,000
probably the easiest way to do that is to either pick the first of the Ps or the last 

227
00:10:53,000 --> 00:10:57,000
of the Ps, right, and to recur on and ignore the other ones. 

228
00:10:57,000 --> 00:11:00,000
So, for example, if right here I did a find on the rest 

229
00:11:00,000 --> 00:11:02,000
after I -do you see any more of these? 

230
00:11:02,000 --> 00:11:04,000
And if you do, 

231
00:11:04,000 --> 00:11:07,000
then skip it and just let those go. Or, you know, 

232
00:11:07,000 --> 00:11:10,000
do the first. Don't do the remaining ones. You can either look to the left of look to the 

233
00:11:10,000 --> 00:11:13,000
right and see if you see any more, and if so, 

234
00:11:13,000 --> 00:11:14,000
skip the, 

235
00:11:14,000 --> 00:11:19,000
you know, early or later ones depending on what your strategy is. 

236
00:11:19,000 --> 00:11:25,000
Any questions about permute here? [Inaudible]. 

237
00:11:25,000 --> 00:11:27,000
So the [inaudible] can be just -look down here, right, it just looks like that, right? 

238
00:11:27,000 --> 00:11:31,000
This is a very common thing. You'll see this again, and again, and it tends to be that the 

239
00:11:31,000 --> 00:11:33,000
outer call, right, it tends to have this sort of 

240
00:11:33,000 --> 00:11:34,000
this, you know, solve this problem, 

241
00:11:34,000 --> 00:11:37,000
and then it turns out during the recursive calls you need to maintain some state 

242
00:11:37,000 --> 00:11:40,000
about where you are in the problem. You know, like, how many letters you moved, or 

243
00:11:40,000 --> 00:11:44,000
what permutation you've built so far, or where you are in the maze, or whatever it is you're 

244
00:11:44,000 --> 00:11:45,000
trying to solve. 

245
00:11:45,000 --> 00:11:49,000
And so typically that wrapper call is just gonna be setting up the initial call in a 

246
00:11:49,000 --> 00:11:52,000
way that has the initial form of that state 

247
00:11:52,000 --> 00:11:52,000
present 

248
00:11:52,000 --> 00:11:56,000
that the client to the function didn't need to know about. It's just our own housekeeping that we're 

249
00:11:56,000 --> 00:11:58,000
setting up. 

250
00:11:58,000 --> 00:12:01,000
Seems almost kind of silly to write down the function that has just line that just turns it 

251
00:12:01,000 --> 00:12:04,000
into, basically, it's just exchanging 

252
00:12:04,000 --> 00:12:06,000
-setting up the 

253
00:12:06,000 --> 00:12:11,000
other parameters. 

254
00:12:11,000 --> 00:12:13,000
I 

255
00:12:13,000 --> 00:12:17,000
am going to show you the other kind of master patter, and 

256
00:12:17,000 --> 00:12:20,000
then we're gonna go on to kind of use them to solve other problems. 

257
00:12:20,000 --> 00:12:24,000
This is the one that was already alluded to, this idea of a combinations. Instead 

258
00:12:24,000 --> 00:12:26,000
of actually producing all of the four character strings that involve 

259
00:12:26,000 --> 00:12:28,000
rearrangements of A B C D, 

260
00:12:28,000 --> 00:12:32,000
what if I were to [inaudible] in kind of the subgroups, or the way I could chose certain 

261
00:12:32,000 --> 00:12:34,000
characters out of that 

262
00:12:34,000 --> 00:12:35,000
initial input, and 

263
00:12:35,000 --> 00:12:39,000
potentially exclude some, potentially include some? So if I have A B C, 

264
00:12:39,000 --> 00:12:41,000
then the subsets of the subgroups of that 

265
00:12:41,000 --> 00:12:45,000
would be the single characters A B and C. The empty string A B and C itself the 

266
00:12:45,000 --> 00:12:50,000
full one, and then the combinations of two, A B, A C, and B C. 

267
00:12:50,000 --> 00:12:53,000
Now, in this case we're gonna say that order doesn't matter. We're not -whereas permutations was all 

268
00:12:53,000 --> 00:12:54,000
about order, I'm 

269
00:12:54,000 --> 00:12:57,000
gonna use -I'm gonna structure this one where I don't care. If it's A B or 

270
00:12:57,000 --> 00:12:59,000
B A I'm gonna consider it the same subset. 

271
00:12:59,000 --> 00:13:05,000
So I'm just interested in inclusion. Is A in or out? Is B in or out? Is C in or out? 

272
00:13:05,000 --> 00:13:09,000
And so the recursive strategy we're gonna take is exactly what I have just 

273
00:13:09,000 --> 00:13:12,000
kind of alluded to in my English description there, 

274
00:13:12,000 --> 00:13:15,000
is that I've got an input, A B C. 

275
00:13:15,000 --> 00:13:18,000
Each of those elements has either the opportunity of being in the subset or 

276
00:13:18,000 --> 00:13:19,000
not. 

277
00:13:19,000 --> 00:13:21,000
And I need to make that decision for everyone 

278
00:13:21,000 --> 00:13:25,000
-every single element, and then I need to kind of explore all the possible 

279
00:13:25,000 --> 00:13:26,000
combinations of that, right? 

280
00:13:26,000 --> 00:13:29,000
When A is in, what if B is out? When A is in, what if B is in? 

281
00:13:29,000 --> 00:13:32,000
So the recursion that I'm gonna use here 

282
00:13:32,000 --> 00:13:35,000
is that at each step of the way, I'm gonna separate one element from the 

283
00:13:35,000 --> 00:13:36,000
input, 

284
00:13:36,000 --> 00:13:39,000
and probably the easiest way to do that is just to kind of take the front 

285
00:13:39,000 --> 00:13:40,000
most element off the input 

286
00:13:40,000 --> 00:13:42,000
and sort of 

287
00:13:42,000 --> 00:13:45,000
separate it into this character by itself and then the remainder. Similarly, the way 

288
00:13:45,000 --> 00:13:46,000
I did with permute, 

289
00:13:46,000 --> 00:13:49,000
and then given that element I have 

290
00:13:49,000 --> 00:13:51,000
earmarked here, I can 

291
00:13:51,000 --> 00:13:54,000
try putting it in the current subset or not. I need to try both, so I'm gonna make 

292
00:13:54,000 --> 00:13:56,000
two recursive calls here, 

293
00:13:56,000 --> 00:13:58,000
one recursive call where I've added it in, 

294
00:13:58,000 --> 00:14:02,000
one recursive call where I haven't added it in. In both cases, right, I will have 

295
00:14:02,000 --> 00:14:04,000
removed it from the rest, 

296
00:14:04,000 --> 00:14:08,000
so what's being chosen from to complete that subset 

297
00:14:08,000 --> 00:14:10,000
always is a little bit smaller, a little bit easier. 

298
00:14:10,000 --> 00:14:14,000
So this is very, very much like the problem I described as the chose 

299
00:14:14,000 --> 00:14:18,000
problem. Trying to choose four people from a dorm to go to flicks was 

300
00:14:18,000 --> 00:14:19,000
picking Bob 

301
00:14:19,000 --> 00:14:21,000
and then -[inaudible] to Bob and not Bob, and then 

302
00:14:21,000 --> 00:14:25,000
saying, well, Bob could go, in which I need to pick three people to go with him, 

303
00:14:25,000 --> 00:14:29,000
or Bob could not go and I need to pick four people to go without Bob. 

304
00:14:29,000 --> 00:14:34,000
This is very much that same pattern. Two recursive calls. Identify one in or out. 

305
00:14:34,000 --> 00:14:36,000
The base case becomes when there's nothing left 

306
00:14:36,000 --> 00:14:39,000
to check out. 

307
00:14:39,000 --> 00:14:41,000
So I start with the input A B C -A 

308
00:14:41,000 --> 00:14:42,000
B C D let's say. 

309
00:14:42,000 --> 00:14:45,000
I look at that first element -I just need to pick one. Might as well pick the front one, it's the 

310
00:14:45,000 --> 00:14:47,000
easy one to get to. 

311
00:14:47,000 --> 00:14:48,000
I add it to the subset, 

312
00:14:48,000 --> 00:14:52,000
remove it from the input, and make a recursive call. 

313
00:14:52,000 --> 00:14:54,000
When that recursion completely terminates, 

314
00:14:54,000 --> 00:14:56,000
I get back to this call, 

315
00:14:56,000 --> 00:14:58,000
and I do the same thing again. 

316
00:14:58,000 --> 00:15:02,000
Remaining input is B C D again but now the subset that I've been building doesn't 

317
00:15:02,000 --> 00:15:03,000
include. 

318
00:15:03,000 --> 00:15:05,000
So inclusion exclusion 

319
00:15:05,000 --> 00:15:13,000
are the two things that I'm trying. So the 

320
00:15:13,000 --> 00:15:16,000
subset problem, right, very similar in structure to the way that I set 

321
00:15:16,000 --> 00:15:20,000
up permutations, right, as I'm gonna keep track of two strings as I'm working my way 

322
00:15:20,000 --> 00:15:20,000
down 

323
00:15:20,000 --> 00:15:24,000
the remainder in the rest, right, things that I haven't yet explored 

324
00:15:24,000 --> 00:15:28,000
so far is what characters I've chosen to place into the subset that I'm building. 

325
00:15:28,000 --> 00:15:32,000
If I get to the end where there's nothing left in the rest, so there's no 

326
00:15:32,000 --> 00:15:33,000
more choices to make, 

327
00:15:33,000 --> 00:15:37,000
then what I have in the subset is what I have in the subset, and I go ahead and print it. 

328
00:15:37,000 --> 00:15:38,000
In the case that there's still something to look at 

329
00:15:38,000 --> 00:15:41,000
I make these two calls, 

330
00:15:41,000 --> 00:15:44,000
one where I've appended it in, where I haven't, and then both cases, right, where I 

331
00:15:44,000 --> 00:15:47,000
have subtracted it off of the 

332
00:15:47,000 --> 00:15:49,000
rest by using the subster to 

333
00:15:49,000 --> 00:15:55,000
truncate that front character off. 

334
00:15:55,000 --> 00:15:56,000
So the way that 

335
00:15:56,000 --> 00:15:57,000
permute was making calls, right, was in a loop, 

336
00:15:57,000 --> 00:16:00,000
and so sometimes it's a little bit misleading. You look at it and you think there's 

337
00:16:00,000 --> 00:16:03,000
only one recursive call, but in fact it's in inside a loop, and so it's making, 

338
00:16:03,000 --> 00:16:06,000
potentially, end recursive calls where end is the length of 

339
00:16:06,000 --> 00:16:08,000
the input. 

340
00:16:08,000 --> 00:16:10,000
It gets a little bit shorter each time through but there's always, you know, however many 

341
00:16:10,000 --> 00:16:13,000
characters are in rest is how many recursive calls it makes. 

342
00:16:13,000 --> 00:16:17,000
The subsets code actually makes exactly two recursive calls at any given stage, in or out, 

343
00:16:17,000 --> 00:16:21,000
and then recurs on that and what is one remaining. 

344
00:16:21,000 --> 00:16:23,000
It also needs a wrapper 

345
00:16:23,000 --> 00:16:26,000
for the same exact reason that permutations did. It's 

346
00:16:26,000 --> 00:16:28,000
just that we are trying to 

347
00:16:28,000 --> 00:16:29,000


348
00:16:29,000 --> 00:16:32,000
list the subsets of a particular string, in fact, there's some housekeeping that's going along 

349
00:16:32,000 --> 00:16:36,000
with it. We're just trying the subset so far is something we don't necessarily 

350
00:16:36,000 --> 00:16:38,000
want to put into the public interface in the way that somebody would have to 

351
00:16:38,000 --> 00:16:44,000
know what to pass to that to get the right thing. Anybody have 

352
00:16:44,000 --> 00:16:48,000
a question about this? 

353
00:16:48,000 --> 00:16:50,000
So given the way this code is written, 

354
00:16:50,000 --> 00:17:05,000
what is the first subset that is printed if I give it the input A B C D? 

355
00:17:05,000 --> 00:17:07,000
A B C D. Just like it was with permute, right? Everything went in. 

356
00:17:07,000 --> 00:17:19,000
What is the second one printed after that? 

357
00:17:19,000 --> 00:17:20,000
A B C, right? So I'm 

358
00:17:20,000 --> 00:17:22,000
gonna look at my little diagram with you 

359
00:17:22,000 --> 00:17:27,000
to help kind of trace this process of the recursive call, right, is that 

360
00:17:27,000 --> 00:17:31,000
the leftmost arm is the inclusion arm, the right arm is the exclusion arm. 

361
00:17:31,000 --> 00:17:34,000
At every level of the tree, right, we're looking at the next character of 

362
00:17:34,000 --> 00:17:36,000
the rest and deciding whether to go in or out, 

363
00:17:36,000 --> 00:17:38,000
the first call it makes is always in, 

364
00:17:38,000 --> 00:17:41,000
so at the beginning it says, I'm choosing about A. Is A in? Sure. 

365
00:17:41,000 --> 00:17:44,000
And then it gets back to the level of recursion. It says, okay, look at the first 

366
00:17:44,000 --> 00:17:48,000
thing of rest, that's B. Is B in? Sure. Goes down the right arm, right? 

367
00:17:48,000 --> 00:17:52,000
Is C in? Sure. Is D in? Sure. It gets to here and now we have nothing left, so we 

368
00:17:52,000 --> 00:17:54,000
have [inaudible] A B C D. 

369
00:17:54,000 --> 00:17:58,000
With the rest being empty, we go ahead and print it [inaudible] there's no more choices to 

370
00:17:58,000 --> 00:18:01,000
make. We've looked at every letter and decided whether it was in or out. 

371
00:18:01,000 --> 00:18:05,000
It will come back to here, and I'll say, okay, I've finished all the things I can make 

372
00:18:05,000 --> 00:18:06,000
with D in, 

373
00:18:06,000 --> 00:18:09,000
how about we try it with D out. And so then D out 

374
00:18:09,000 --> 00:18:11,000
gives us just the A B C. 

375
00:18:11,000 --> 00:18:13,000
After it's done everything it can do with 

376
00:18:13,000 --> 00:18:17,000
A B C in, it comes back to here and says, okay, well now do this arm, 

377
00:18:17,000 --> 00:18:21,000
and this will drop C off, and then try D in, D out. 

378
00:18:21,000 --> 00:18:25,000
And so it will go from the biggest sets to the smaller sets, not quite 

379
00:18:25,000 --> 00:18:26,000
monotonically though. 

380
00:18:26,000 --> 00:18:28,000
The very last set printed will be the empty set, 

381
00:18:28,000 --> 00:18:31,000
and that will be the one where it was excluded all the way down, which after it kind of tried 

382
00:18:31,000 --> 00:18:34,000
all these combinations of in out, in out, in out, it 

383
00:18:34,000 --> 00:18:37,000
eventually got to the out, out, out, out, out, out, out case which will give me the 

384
00:18:37,000 --> 00:18:40,000
empty set on that arm. 

385
00:18:40,000 --> 00:18:43,000
Again, if I reverse the calls, right, I'd still see all the same subsets in 

386
00:18:43,000 --> 00:18:46,000
the end. They just come out in a different order. 

387
00:18:46,000 --> 00:18:50,000
But it is worthwhile to model the recursion in your own head to have this 

388
00:18:50,000 --> 00:18:54,000
idea of understanding about how it goes deep, right? That 

389
00:18:54,000 --> 00:18:57,000
it always makes that recursive call and has to work its way all the way to the 

390
00:18:57,000 --> 00:19:00,000
base case and terminate that recursion before it will unfold 

391
00:19:00,000 --> 00:19:03,000
and revisit the second call that was made, and 

392
00:19:03,000 --> 00:19:11,000
then fully explore where it goes before it completes that whole sequence. 

393
00:19:11,000 --> 00:19:16,000
Anybody want to ask me a question about these guys? These are 

394
00:19:16,000 --> 00:19:21,000
just really, really important pieces of code, and so I'm trying to 

395
00:19:21,000 --> 00:19:25,000
make sure that I don't move past something that still feels a little bit 

396
00:19:25,000 --> 00:19:27,000
mystical or confusing to you because 

397
00:19:27,000 --> 00:19:29,000
everything I want to do for the rest of today 

398
00:19:29,000 --> 00:19:30,000
builds on this. 

399
00:19:30,000 --> 00:19:33,000
So now if there's something about either of these pieces of code 

400
00:19:33,000 --> 00:19:38,000
that would help you -yeah. What would 

401
00:19:38,000 --> 00:19:40,000
be the simplest way to do that? 

402
00:19:40,000 --> 00:19:43,000
So probably the simplest way, like, if you said, oh, I just really want it to be in alphabetical order, 

403
00:19:43,000 --> 00:19:45,000
would be to put them in a set, right, and then 

404
00:19:45,000 --> 00:19:47,000
have the set be the order for you. So you said 

405
00:19:47,000 --> 00:19:49,000
order doesn't matter? Oh, you 

406
00:19:49,000 --> 00:19:53,000
did care about how they got ordered. So, like, let's say you 

407
00:19:53,000 --> 00:19:57,000
didn't want B C D to equal C D B. 

408
00:19:57,000 --> 00:20:00,000
So in that case, right, you would be more likely to kind of add a permutation step into 

409
00:20:00,000 --> 00:20:04,000
it, right? So if B C D was not the same thing as A B C, right, it would be, like, 

410
00:20:04,000 --> 00:20:05,000
well 

411
00:20:05,000 --> 00:20:07,000
I'm gonna chose -so in this case, right, 

412
00:20:07,000 --> 00:20:11,000
it always -well the subsets will always be printed as kind of a subsequence. So -and let's 

413
00:20:11,000 --> 00:20:14,000
say if the input was the alphabet, just easy way 

414
00:20:14,000 --> 00:20:15,000
to describe it, 

415
00:20:15,000 --> 00:20:19,000
all of the subsets I'm choosing will always be in alphabetical order because I'm always choosing A in or not, B in 

416
00:20:19,000 --> 00:20:19,000
or not. 

417
00:20:19,000 --> 00:20:23,000
If I really wanted B Z to be distinct from Z B, 

418
00:20:23,000 --> 00:20:27,000
then really what I want to be doing at each step is picking the next character to go, 

419
00:20:27,000 --> 00:20:28,000


420
00:20:28,000 --> 00:20:29,000
and not 

421
00:20:29,000 --> 00:20:32,000
always assuming the next one had to be the next one in sequence, so I would do more like a 

422
00:20:32,000 --> 00:20:36,000
permute kind of loop that's like pick the next one that goes, remove it from what 

423
00:20:36,000 --> 00:20:38,000
remains and recur, 

424
00:20:38,000 --> 00:20:40,000
and that I need that separate step we talked about of -and 

425
00:20:40,000 --> 00:20:42,000
in addition to kind of 

426
00:20:42,000 --> 00:20:43,000


427
00:20:43,000 --> 00:20:45,000
picking, we also have to 

428
00:20:45,000 --> 00:20:48,000
leave open the opportunity that we didn't pick anything and we just kind of left the subject as is, right, so we 

429
00:20:48,000 --> 00:20:50,000
could [inaudible] or not. And 

430
00:20:50,000 --> 00:20:54,000
so permute always assumes we have to have picked everything. The subset code 

431
00:20:54,000 --> 00:20:57,000
would also allow for 

432
00:20:57,000 --> 00:20:58,000
some of them just being entirely skipped. 

433
00:20:58,000 --> 00:21:02,000
So we pick the next one, right, and then eventually 

434
00:21:02,000 --> 00:21:04,000
stopped picking. 

435
00:21:04,000 --> 00:21:07,000
[Inaudible] just in your wrapper function 

436
00:21:07,000 --> 00:21:13,000
then [inaudible] put a for loop or something like that, right? When you're through changing your string? Yeah, you can certainly do that, like in a permute from the outside too, right. 

437
00:21:13,000 --> 00:21:16,000
So there's often very, you know, 

438
00:21:16,000 --> 00:21:19,000
multiple different ways you can get it the same thing whether you want to put it in the recursion or 

439
00:21:19,000 --> 00:21:20,000
outside the recursion, 

440
00:21:20,000 --> 00:21:22,000
have the set help you do it or not, 

441
00:21:22,000 --> 00:21:26,000
that can get you the same result. 

442
00:21:26,000 --> 00:21:28,000
So let me try to 

443
00:21:28,000 --> 00:21:32,000
identify what's the same about these to try to kind of back away from it and 

444
00:21:32,000 --> 00:21:33,000
kind of 

445
00:21:33,000 --> 00:21:36,000
move just to see how these are more similar than they are different, right, 

446
00:21:36,000 --> 00:21:40,000
even though the code ends up kind of being -having some details in it 

447
00:21:40,000 --> 00:21:43,000
that -if you kind of look at it from far away these are both problems that are 

448
00:21:43,000 --> 00:21:45,000
about 

449
00:21:45,000 --> 00:21:45,000
choice. 

450
00:21:45,000 --> 00:21:50,000
That the recursive calls that we see have kind of a branching structure and a depth factor 

451
00:21:50,000 --> 00:21:53,000
that actually relates to the problem if you think about it in terms of decisions, 

452
00:21:53,000 --> 00:21:57,000
that in making a permutation your decision is what character goes next, right? In the 

453
00:21:57,000 --> 00:22:01,000
subset it's like, well, whether this character goes in or not 

454
00:22:01,000 --> 00:22:05,000
that the recursive tree that I was drawing that it shows all those calls, 

455
00:22:05,000 --> 00:22:09,000
the depths of it represents the number of choices you make. Each 

456
00:22:09,000 --> 00:22:13,000
recursive call makes a choice, right? A yes, no, or a next letter to go, and then recurs from 

457
00:22:13,000 --> 00:22:15,000
there. So I make, you know, 

458
00:22:15,000 --> 00:22:18,000
one of those calls, and then there's N minus 1 beneath it that represent 

459
00:22:18,000 --> 00:22:22,000
the further decisions I make that builds on that. And so, in the case of permutation, once I've 

460
00:22:22,000 --> 00:22:23,000
picked the, you 

461
00:22:23,000 --> 00:22:25,000
know, N minus 1 

462
00:22:25,000 --> 00:22:29,000
things to go, there's only one thing left, right? And so in some sense the tree is 

463
00:22:29,000 --> 00:22:31,000
N because I have to pick N things that go in the permutation and then I'm 

464
00:22:31,000 --> 00:22:32,000
done. 

465
00:22:32,000 --> 00:22:35,000
In the subsets, it's also N, and that's because for each of the characters I'm deciding 

466
00:22:35,000 --> 00:22:37,000
whether it's in or out. So I 

467
00:22:37,000 --> 00:22:40,000
looked at A and decided in or out. I looked at B and decided in or out. And I did that all the 

468
00:22:40,000 --> 00:22:41,000
way down. 

469
00:22:41,000 --> 00:22:42,000
That was the life of the input. 

470
00:22:42,000 --> 00:22:44,000
The branching 

471
00:22:44,000 --> 00:22:48,000
represents how many recursive calls were made 

472
00:22:48,000 --> 00:22:52,000
at each level of the recursion. In the case of subsets, it's always exactly two. 

473
00:22:52,000 --> 00:22:54,000
In, out, all the way down, 

474
00:22:54,000 --> 00:22:59,000
restarts at 1, branches to 2, goes to 4, goes to 8, 16, and so on. 

475
00:22:59,000 --> 00:23:01,000
In the permute case, right, 

476
00:23:01,000 --> 00:23:05,000
there are N calls at the beginning. I have N different letters to choose from, so 

477
00:23:05,000 --> 00:23:10,000
it's a very wide spread there, and that at that next level, it's N minus 1. 

478
00:23:10,000 --> 00:23:12,000
Still very wide. And N minus 2. And 

479
00:23:12,000 --> 00:23:16,000
so the overall tree has kind of an N times N minus 1 times N minus 

480
00:23:16,000 --> 00:23:19,000
2 all the way down to the bottom, which the factorial function 

481
00:23:19,000 --> 00:23:22,000
-which grows very, very quickly. 

482
00:23:22,000 --> 00:23:26,000
Even for small inputs, right, the number of permutations is enormous. 

483
00:23:26,000 --> 00:23:28,000
The number of subsets is to the end 

484
00:23:28,000 --> 00:23:29,000


485
00:23:29,000 --> 00:23:30,000
in or out, right, all the way across. 

486
00:23:30,000 --> 00:23:32,000
Also, a very, 

487
00:23:32,000 --> 00:23:34,000
you know, 

488
00:23:34,000 --> 00:23:37,000
resource intensive problem to solve, not nearly as bad as permutation, but both of 

489
00:23:37,000 --> 00:23:41,000
them, even for small sizes of N, start to become pretty quickly intractable. 

490
00:23:41,000 --> 00:23:44,000
This is not the fault of recursion, right, these problems are not hard to solve because 

491
00:23:44,000 --> 00:23:48,000
we're solving them in the wrong way. It's because there are N factorial permutations. There are 

492
00:23:48,000 --> 00:23:49,000
[inaudible] different subsets, 

493
00:23:49,000 --> 00:23:52,000
right? Anything that's going to print to the N things, or N factorial things is going 

494
00:23:52,000 --> 00:23:56,000
to do N factorial work to do so. You can't avoid it. 

495
00:23:56,000 --> 00:23:59,000
There's a big amount of work to be done in there. 

496
00:23:59,000 --> 00:24:02,000
But what we're trying to look at here is this idea that those trees, right, 

497
00:24:02,000 --> 00:24:04,000
represent decisions. 

498
00:24:04,000 --> 00:24:08,000
There's some decisions that are made, you know, a decision is made at each level of recursion, 

499
00:24:08,000 --> 00:24:09,000
which then 

500
00:24:09,000 --> 00:24:11,000
is kind of a little bit closer 

501
00:24:11,000 --> 00:24:14,000
to having no more decisions to make. You have so many decisions to make, which is 

502
00:24:14,000 --> 00:24:18,000
the depth of the recursion. Once you've made all those decisions, you hit your base case 

503
00:24:18,000 --> 00:24:19,000
and you're done. The 

504
00:24:19,000 --> 00:24:23,000
tree being very wide and very deep makes for expensive exploration. 

505
00:24:23,000 --> 00:24:27,000
What we're gonna look at is a way that we can take the same structure of the 

506
00:24:27,000 --> 00:24:31,000
problem, one that fundamentally could be exhaustive, exhaustive meaning tried every 

507
00:24:31,000 --> 00:24:35,000
possible combination, every possible rearrangement and option, 

508
00:24:35,000 --> 00:24:38,000
and only explore some part of the tree. 

509
00:24:38,000 --> 00:24:41,000
So only look around in some region, 

510
00:24:41,000 --> 00:24:43,000
and as soon as we find something that's good enough. 

511
00:24:43,000 --> 00:24:46,000
So in the case, for example, of a search problem, it might be that we're searching 

512
00:24:46,000 --> 00:24:50,000
this space that could potentially cause us to look at every option, 

513
00:24:50,000 --> 00:24:54,000
but we're also willing to say if we make some decisions that turn out good enough, 

514
00:24:54,000 --> 00:24:57,000
that get us to our goal, or whatever it is we're looking for, 

515
00:24:57,000 --> 00:25:00,000
we won't have to keep working any farther. So I'm gonna show 

516
00:25:00,000 --> 00:25:03,000
you how we can take an exhaustive recursion problem and turn it into 

517
00:25:03,000 --> 00:25:06,000
what's called a recursive backtracker. So 

518
00:25:06,000 --> 00:25:07,000
there's 

519
00:25:07,000 --> 00:25:10,000
a lot of text on this slide but let me just tell you in English what we're trying to 

520
00:25:10,000 --> 00:25:12,000
get at. 

521
00:25:12,000 --> 00:25:13,000
That 

522
00:25:13,000 --> 00:25:14,000


523
00:25:14,000 --> 00:25:17,000
the idea behind permutations or subsets is that at every level there's all 

524
00:25:17,000 --> 00:25:20,000
these choices and we're gonna try every single one of them. 

525
00:25:20,000 --> 00:25:25,000
Now imagine we were gonna make a little bit less a guarantee about that. 

526
00:25:25,000 --> 00:25:26,000
Let's design the function 

527
00:25:26,000 --> 00:25:30,000
to return some sort of state that's like I succeeded or I failed. Did 

528
00:25:30,000 --> 00:25:33,000
I find what I was looking for? 

529
00:25:33,000 --> 00:25:33,000


530
00:25:33,000 --> 00:25:38,000
At each call, I still have the possibility of multiple calls of in out, or a choice 

531
00:25:38,000 --> 00:25:40,000
from what's there. 

532
00:25:40,000 --> 00:25:42,000
I'm gonna go ahead and make the choice, 

533
00:25:42,000 --> 00:25:44,000
make the recursive call, 

534
00:25:44,000 --> 00:25:47,000
and then catch the result from that recursive call, and see whether it 

535
00:25:47,000 --> 00:25:51,000
succeeded. Was that a good choice? Did that choice get me to where I wanted to be? 

536
00:25:51,000 --> 00:25:52,000
If it did, 

537
00:25:52,000 --> 00:25:53,000
then I'm done. 

538
00:25:53,000 --> 00:25:56,000
I won't try anything else. So I'll stop early, 

539
00:25:56,000 --> 00:25:59,000
quite going around the for loop, quit making other recursive calls, 

540
00:25:59,000 --> 00:26:02,000
and just immediately [inaudible] say I'm done. 

541
00:26:02,000 --> 00:26:03,000
If it didn't 

542
00:26:03,000 --> 00:26:07,000
-it came back with a failure, some sort of code that said it didn't get where I 

543
00:26:07,000 --> 00:26:10,000
want to do, then I'll try a different choice. 

544
00:26:10,000 --> 00:26:14,000
And, again, I'll be optimistic. It's a very optimistic way of doing stuff. It says 

545
00:26:14,000 --> 00:26:17,000
make a choice, assume it's a good one, and go with it. 

546
00:26:17,000 --> 00:26:19,000
Only when you learn it didn't work out 

547
00:26:19,000 --> 00:26:23,000
do you revisit that decision and back up and try again. 

548
00:26:23,000 --> 00:26:27,000
So let me show you the code. I think it's gonna make more sense, actually, if 

549
00:26:27,000 --> 00:26:28,000
I 

550
00:26:28,000 --> 00:26:30,000
do it in terms of looking at what the code looks like. 

551
00:26:30,000 --> 00:26:35,000
This is the pseudo code at which all recursive backtrackers at their heart 

552
00:26:35,000 --> 00:26:37,000
come down to this pattern. 

553
00:26:37,000 --> 00:26:41,000
So what I -I tried to be abstract [inaudible] so what does it mean to solve a 

554
00:26:41,000 --> 00:26:44,000
problem, and what's the configuration? That depends on the domain and the problem 

555
00:26:44,000 --> 00:26:45,000
we're trying to solve. 

556
00:26:45,000 --> 00:26:48,000
But the structure of them all looks the same in that sense that 

557
00:26:48,000 --> 00:26:53,000
if there are choices to be made -so the idea is that we cast the problem as a decision 

558
00:26:53,000 --> 00:26:54,000
problem. 

559
00:26:54,000 --> 00:26:56,000
There are a bunch of choices to be made. 

560
00:26:56,000 --> 00:26:58,000
Each [inaudible] will make one choice 

561
00:26:58,000 --> 00:27:00,000
and then attempt to recursively solve it. So 

562
00:27:00,000 --> 00:27:04,000
there's some available choices, in or out, or one of next, or where to place a 

563
00:27:04,000 --> 00:27:07,000
tile on a board, or whether to take a left or right turn and go straight in a 

564
00:27:07,000 --> 00:27:10,000
maze. Any of these things could be the choices here. 

565
00:27:10,000 --> 00:27:11,000
We make a choice, 

566
00:27:11,000 --> 00:27:13,000
we feel good about it, we commit to it, 

567
00:27:13,000 --> 00:27:16,000
and we say, well, if we can solve from here -so we kind of update our statement so we've made 

568
00:27:16,000 --> 00:27:19,000
that term, or, 

569
00:27:19,000 --> 00:27:21,000
you know, chosen that letter, whatever it is we're doing. 

570
00:27:21,000 --> 00:27:24,000
If that recursive call returned true 

571
00:27:24,000 --> 00:27:25,000
then we return true, 

572
00:27:25,000 --> 00:27:28,000
so we don't do any unwinding. We don't try all the other choices. We stop that for 

573
00:27:28,000 --> 00:27:29,000
loop early. 

574
00:27:29,000 --> 00:27:32,000
We say that worked. That was good enough. 

575
00:27:32,000 --> 00:27:35,000
If the solve came back with a negative result, 

576
00:27:35,000 --> 00:27:36,000
that causes us to unmake that choice, 

577
00:27:36,000 --> 00:27:39,000
and then we come back around here and we try another one. 

578
00:27:39,000 --> 00:27:42,000
Again, we're optimistic. Okay, left didn't work, go straight. 

579
00:27:42,000 --> 00:27:46,000
If straight doesn't work, okay, go right. If right didn't work and we don't have any 

580
00:27:46,000 --> 00:27:50,000
more choices, then we return false, and 

581
00:27:50,000 --> 00:27:55,000
this false is the one that then causes some earlier decision to get unmade 

582
00:27:55,000 --> 00:28:00,000
which allows us to revisit some earlier optimistic choice, undo it, and 

583
00:28:00,000 --> 00:28:01,000
try again. 

584
00:28:01,000 --> 00:28:04,000
The base case is hit when we run out of choices 

585
00:28:04,000 --> 00:28:08,000
where we've -whatever configuration we're at is, like, okay, we're at a dead end, or we're at 

586
00:28:08,000 --> 00:28:10,000
the goal, or we've 

587
00:28:10,000 --> 00:28:14,000
run out of letters to try. Whatever it is, right, that tells us, okay, we didn't 

588
00:28:14,000 --> 00:28:17,000
-there's nothing more to decide. Is this where we wanted to be? 

589
00:28:17,000 --> 00:28:18,000
Did it solve the problem? 

590
00:28:18,000 --> 00:28:23,000
And I'm being kind of very deliberate today about what does it mean [inaudible] update the configuration, or what does it 

591
00:28:23,000 --> 00:28:25,000
mean for it to be the goal state because for different problems it definitely means different 

592
00:28:25,000 --> 00:28:29,000
things. But the code for them all looks the same 

593
00:28:29,000 --> 00:28:30,000
kind of in 

594
00:28:30,000 --> 00:28:33,000
its skeletal form. 

595
00:28:33,000 --> 00:28:38,000
So let me take a piece of code and turn it into a recursive backtracker with you. 

596
00:28:38,000 --> 00:28:40,000
So I've got recursive permute up 

597
00:28:40,000 --> 00:28:44,000
here. So as it is, recursive permute tries every possible permutation, prints them all. 

598
00:28:44,000 --> 00:28:47,000
What I'm interested in is is 

599
00:28:47,000 --> 00:28:51,000
this sequence a letters an anagram. Meaning, it is -can be rearranged into 

600
00:28:51,000 --> 00:28:54,000
something that's an English word. Okay. 

601
00:28:54,000 --> 00:28:56,000
So what I'm gonna do is I'm gonna go in and edit it. The 

602
00:28:56,000 --> 00:28:59,000
first thing I'm gonna do is I'm gonna change it to where it's gonna return some 

603
00:28:59,000 --> 00:29:00,000
information. 

604
00:29:00,000 --> 00:29:08,000
That information's gonna be yes it works, no it didn't. Okay? Now I'm gonna do this. 

605
00:29:08,000 --> 00:29:10,000
I'm 

606
00:29:10,000 --> 00:29:13,000
gonna 

607
00:29:13,000 --> 00:29:17,000
add a parameter to this because I -in order to tell that it's a word I have to 

608
00:29:17,000 --> 00:29:19,000
have someplace to look it up. I'm gonna use the lexicon that actually we're using on this 

609
00:29:19,000 --> 00:29:22,000
assignment. 

610
00:29:22,000 --> 00:29:24,000
And so 

611
00:29:24,000 --> 00:29:26,000
when I get to the bottom 

612
00:29:26,000 --> 00:29:30,000
and I have no more choices, I've got some permutation I've assembled here in -so 

613
00:29:30,000 --> 00:29:31,000
far. 

614
00:29:31,000 --> 00:29:35,000
And I'm going to check and see if it's in the dictionary. 

615
00:29:35,000 --> 00:29:38,000
If the dictionary says that that's a word then 

616
00:29:38,000 --> 00:29:41,000
I'm gonna say this was good. That permutation was good. 

617
00:29:41,000 --> 00:29:44,000
You don't need to look at any more permutations. Otherwise I'll return false which will 

618
00:29:44,000 --> 00:29:46,000
say, well, this thing isn't a word. Why don't you try again? 

619
00:29:46,000 --> 00:29:48,000
I'm gonna 

620
00:29:48,000 --> 00:29:53,000
change the name of the function while I'm at it to be a little more descriptive, and we'll call it is anagram. 

621
00:29:53,000 --> 00:29:58,000
And then when I make the call here [inaudible] 

622
00:29:58,000 --> 00:30:00,000
third argument. 

623
00:30:00,000 --> 00:30:03,000
I'm not just gonna make the call and let it go away. I really want to know did that 

624
00:30:03,000 --> 00:30:06,000
work, so I'm gonna say, well, if 

625
00:30:06,000 --> 00:30:08,000
it's an anagram 

626
00:30:08,000 --> 00:30:11,000
then return true. 

627
00:30:11,000 --> 00:30:16,000
So if given the choice I made -I've got these letters X J Q P A B C, 

628
00:30:16,000 --> 00:30:16,000
right? 

629
00:30:16,000 --> 00:30:20,000
It'll pick a letter and it'll say, well if, you know, put that letter in the front 

630
00:30:20,000 --> 00:30:23,000
and then go for it. If you can make a word out of having made that 

631
00:30:23,000 --> 00:30:26,000
choice, out of what remains, then you're done. You don't need to try anything else. Otherwise 

632
00:30:26,000 --> 00:30:29,000
we'll come back around and make some of the further calls in that loop 

633
00:30:29,000 --> 00:30:32,000
to see if it worked out. 

634
00:30:32,000 --> 00:30:34,000
At the bottom, I also need 

635
00:30:34,000 --> 00:30:36,000
another failure case here, 

636
00:30:36,000 --> 00:30:38,000
and that comes when 

637
00:30:38,000 --> 00:30:43,000
the earlier choices, right -so I got, let's say somebody has given me X J, 

638
00:30:43,000 --> 00:30:46,000
and then it says, given X J, can you permute A and B to make a word? Well, it turns out 

639
00:30:46,000 --> 00:30:47,000
that 

640
00:30:47,000 --> 00:30:50,000
you can -you know this ahead of time. It doesn't have the same vision 

641
00:30:50,000 --> 00:30:54,000
you do. But it says X J? A B? There's just nothing you can do but it'll try them all 

642
00:30:54,000 --> 00:30:57,000
dutifully. Tried A in the front and then B behind, and then tried B in the front and A behind it, and 

643
00:30:57,000 --> 00:31:01,000
after it says that, it says, you know what, okay, that just isn't working, right? 

644
00:31:01,000 --> 00:31:02,000
It must be some 

645
00:31:02,000 --> 00:31:05,000
earlier decision that was really at fault. 

646
00:31:05,000 --> 00:31:08,000
This returned false is going to cause 

647
00:31:08,000 --> 00:31:09,000
the, you 

648
00:31:09,000 --> 00:31:13,000
know, sort of stacked up previous anagram calls to say, oh yeah, that 

649
00:31:13,000 --> 00:31:16,000
choice of X for the first letter was really 

650
00:31:16,000 --> 00:31:19,000
questionable. So imagine I've had, like, E X, you know, 

651
00:31:19,000 --> 00:31:21,000
T I. I'm trying to 

652
00:31:21,000 --> 00:31:24,000
spell the word exit -is a possibility of it. That once I have that X in the 

653
00:31:24,000 --> 00:31:27,000
front it turns out nothing is going to work out, but it's gonna go through and try X 

654
00:31:27,000 --> 00:31:30,000
E I T, X E T I, and so on. 

655
00:31:30,000 --> 00:31:33,000
Well, after all those things have been tried it says, you know what, X in the front wasn't it, 

656
00:31:33,000 --> 00:31:37,000
right? Let's try again with I in the front. Well after it does that it won't get anywhere either. 

657
00:31:37,000 --> 00:31:38,000
Eventually it'll try E in the front 

658
00:31:38,000 --> 00:31:41,000
and then it won't have to try anything else after that because that will eventually 

659
00:31:41,000 --> 00:31:44,000
work out. 

660
00:31:44,000 --> 00:31:47,000
So if I put this guy in like that, 

661
00:31:47,000 --> 00:31:49,000
and I 

662
00:31:49,000 --> 00:31:59,000
build myself a lexicon, and then 

663
00:31:59,000 --> 00:32:01,000
I change this to 

664
00:32:01,000 --> 00:32:04,000


665
00:32:04,000 --> 00:32:09,000
anagram word. I 

666
00:32:09,000 --> 00:32:13,000
can't spell. I'd better 

667
00:32:13,000 --> 00:32:16,000
pass my lexicon because I'm gonna need that to 

668
00:32:16,000 --> 00:32:18,000
do my word lookups. 

669
00:32:18,000 --> 00:32:20,000
[Inaudible]. And down here. 

670
00:32:20,000 --> 00:32:23,000
Whoops. 

671
00:32:23,000 --> 00:32:28,000
Okay. I 

672
00:32:28,000 --> 00:32:33,000
think 

673
00:32:33,000 --> 00:32:36,000
that looks like it's okay. Well, no 

674
00:32:36,000 --> 00:32:43,000
-finish this thing off here. 

675
00:32:43,000 --> 00:32:47,000
And so if I type in, you know, a word that I know is a word to begin 

676
00:32:47,000 --> 00:32:47,000
with, 

677
00:32:47,000 --> 00:32:49,000
like 

678
00:32:49,000 --> 00:32:52,000
boat, I happen to know the way the permutations work [inaudible] try that right away and find 

679
00:32:52,000 --> 00:32:52,000
that. 

680
00:32:52,000 --> 00:32:56,000
What if I get it toab, you know, which is a rearrangement of that, it eventually did find them. 

681
00:32:56,000 --> 00:32:59,000
What if I give it something like this, 

682
00:32:59,000 --> 00:33:02,000
which there's just no way you can get that in there. So it seems to [inaudible] it's 

683
00:33:02,000 --> 00:33:04,000
not telling us where the word is. I can actually go and change it. 

684
00:33:04,000 --> 00:33:07,000
Maybe that'd be a nice thing to say. Why don't I print the word 

685
00:33:07,000 --> 00:33:11,000
when it finds it? If 

686
00:33:11,000 --> 00:33:14,000
lex dot contains 

687
00:33:14,000 --> 00:33:16,000
-words so far 

688
00:33:16,000 --> 00:33:20,000
-then print it. That 

689
00:33:20,000 --> 00:33:25,000
way I can find out what word it thinks it made out of it. So if I 

690
00:33:25,000 --> 00:33:27,000
type toab -now 

691
00:33:27,000 --> 00:33:30,000
look at that, bota. Who would know? That dictionary's full of some really ridiculous 

692
00:33:30,000 --> 00:33:33,000
words. 

693
00:33:33,000 --> 00:33:37,000
Now I'll get back with exit. Let's type some other words. 

694
00:33:37,000 --> 00:33:40,000
Query. So it's finding some 

695
00:33:40,000 --> 00:33:44,000
words, and then if I give it some word that I know is just nonsense 

696
00:33:44,000 --> 00:33:46,000
it won't print anything 

697
00:33:46,000 --> 00:33:47,000
[inaudible] false. 

698
00:33:47,000 --> 00:33:51,000
And so in this case, what it's doing is its come to a partial exploration, right, 

699
00:33:51,000 --> 00:33:53,000
of the permutation tree 

700
00:33:53,000 --> 00:33:55,000
based on 

701
00:33:55,000 --> 00:34:00,000
this notion of being able to stop early on success. So in the case of this one, right, 

702
00:34:00,000 --> 00:34:03,000
even six nonsense characters, it really did do the full permutation, in this case, 

703
00:34:03,000 --> 00:34:06,000
the six factorial permutations, and discover that none of them worked. 

704
00:34:06,000 --> 00:34:08,000
But in the case of exit or the 

705
00:34:08,000 --> 00:34:10,000
boat that, 

706
00:34:10,000 --> 00:34:13,000
you know, early in the process it may have kind of made a decision, okay so [inaudible] 

707
00:34:13,000 --> 00:34:16,000
in this case it will try all the permutations with Q in the front, 

708
00:34:16,000 --> 00:34:17,000
right? 

709
00:34:17,000 --> 00:34:20,000
Which means, okay, we'll go with it, and then it'll do them in order to start with, but it'll 

710
00:34:20,000 --> 00:34:23,000
start kind of rearranging and jumbling them up, and eventually, right, 

711
00:34:23,000 --> 00:34:26,000
it will find something that did work with putting in the front, and it will never unmake that 

712
00:34:26,000 --> 00:34:30,000
decision about Q. It will just sort of have -made that decision early, 

713
00:34:30,000 --> 00:34:34,000
committed to it, and worked out, and then it covers a whole space of the tree that never got 

714
00:34:34,000 --> 00:34:38,000
explored of R in front, and Y in the front, and E in the front 

715
00:34:38,000 --> 00:34:40,000
because it had a notion of 

716
00:34:40,000 --> 00:34:43,000
what is a satisfactory outcome. So the base case that it finally got to in 

717
00:34:43,000 --> 00:34:47,000
this case met the standard for being a word was all it wanted to find, so it just 

718
00:34:47,000 --> 00:34:49,000
had to work through the base cases 

719
00:34:49,000 --> 00:34:50,000
until it found one, 

720
00:34:50,000 --> 00:35:00,000
and potentially that could be very few of them relative the huge space. All right. 

721
00:35:00,000 --> 00:35:02,000
I have this code 

722
00:35:02,000 --> 00:35:05,000
actually on this slide. So it's 

723
00:35:05,000 --> 00:35:08,000
permute, and that is turning into is anagram. And so, in blue, trying to highlight 

724
00:35:08,000 --> 00:35:11,000
the things that changed in the process, right, that 

725
00:35:11,000 --> 00:35:15,000
the structure of kind of how it's exploring, and making the recursive calls is exactly 

726
00:35:15,000 --> 00:35:16,000
the same. 

727
00:35:16,000 --> 00:35:19,000
But what we're using now is some return information from the function to 

728
00:35:19,000 --> 00:35:22,000
tell us how the progress went, 

729
00:35:22,000 --> 00:35:23,000
and then 

730
00:35:23,000 --> 00:35:28,000
having our base case return some sense of did we get where we wanted to be, 

731
00:35:28,000 --> 00:35:32,000
and then when we make the recursive call, if it did succeed, right, 

732
00:35:32,000 --> 00:35:35,000
we immediately return true and unwind out of the recursion, 

733
00:35:35,000 --> 00:35:37,000
doing no further exploration, 

734
00:35:37,000 --> 00:35:40,000
and in the case where all of our choices 

735
00:35:40,000 --> 00:35:41,000


736
00:35:41,000 --> 00:35:45,000
gave us no success, right, we will return the call that says, well that was unworkable how we got 

737
00:35:45,000 --> 00:35:49,000
to where we were. 

738
00:35:49,000 --> 00:35:51,000
So this is the transformation that 

739
00:35:51,000 --> 00:35:54,000
you want to feel like you could actually sort of apply again and again, taking 

740
00:35:54,000 --> 00:35:58,000
something that was exhaustive, and looked at a whole space, 

741
00:35:58,000 --> 00:36:01,000
and then had -change it into a form where it's like, okay, well I wanted to stop 

742
00:36:01,000 --> 00:36:04,000
early when I get to something that's good enough. 

743
00:36:04,000 --> 00:36:07,000
A lot of problems, right, that are recursive backtrackers just end up being 

744
00:36:07,000 --> 00:36:08,000
procedural code 

745
00:36:08,000 --> 00:36:11,000
that got turned into this 

746
00:36:11,000 --> 00:36:15,000
based on a goal that you wanted to get to being one of the possibilities of the 

747
00:36:15,000 --> 00:36:18,000
exploration. 

748
00:36:18,000 --> 00:36:22,000
Anybody have any questions of what we got there? Okay. 

749
00:36:22,000 --> 00:36:24,000
I'm gonna show you some more 

750
00:36:24,000 --> 00:36:26,000
just because they are 

751
00:36:26,000 --> 00:36:29,000
-there are a million problems in this space, and the more of them you see, I 

752
00:36:29,000 --> 00:36:32,000
think, the more the patterns will start to emerge. 

753
00:36:32,000 --> 00:36:35,000
Each of these, right, we're gonna think of as decision problems, right, that we have some number 

754
00:36:35,000 --> 00:36:37,000
of decisions to make, 

755
00:36:37,000 --> 00:36:39,000
and we're gonna try to 

756
00:36:39,000 --> 00:36:42,000
make a decision in each recursive call 

757
00:36:42,000 --> 00:36:45,000
knowing that that gives us fewer decisions that we have to make in the 

758
00:36:45,000 --> 00:36:48,000
smaller form of the sub problem that we've built that way, 

759
00:36:48,000 --> 00:36:51,000
and then the decisions that we have open 

760
00:36:51,000 --> 00:36:53,000
to us, the options there 

761
00:36:53,000 --> 00:36:56,000
represent the different recursive calls we can make. Maybe it's a for loop, or 

762
00:36:56,000 --> 00:36:59,000
maybe a list of the explicit alternatives that we have 

763
00:36:59,000 --> 00:37:03,000
that will be open to us in any particular call. 

764
00:37:03,000 --> 00:37:06,000
This is a CS kind of classic problem. It's one that, you know, it doesn't seem like 

765
00:37:06,000 --> 00:37:09,000
it has a lot of utility but it's still interesting to think about, which is if 

766
00:37:09,000 --> 00:37:12,000
you have an eight by eight chessboard, which is the standard chessboard size, 

767
00:37:12,000 --> 00:37:14,000
and you had eight queen pieces, 

768
00:37:14,000 --> 00:37:18,000
could you place those eight queens on the board 

769
00:37:18,000 --> 00:37:21,000
in such a way that no queen is threatened by any other? The queen is 

770
00:37:21,000 --> 00:37:23,000
the most powerful 

771
00:37:23,000 --> 00:37:24,000
player on the board, right, can move 

772
00:37:24,000 --> 00:37:27,000
any number of spaces horizontally, vertically, or diagonally on any 

773
00:37:27,000 --> 00:37:29,000
straight line basically, 

774
00:37:29,000 --> 00:37:32,000
and so it does seem like, you know, that there's a lot of contention on the 

775
00:37:32,000 --> 00:37:35,000
board to get them all in there in such a way that they can't 

776
00:37:35,000 --> 00:37:37,000
go after each other. 

777
00:37:37,000 --> 00:37:41,000
And so if we think of this as a decision problem, 

778
00:37:41,000 --> 00:37:44,000
each call's gonna make one decision and recur on the rest. The decisions we have to 

779
00:37:44,000 --> 00:37:45,000
make are 

780
00:37:45,000 --> 00:37:50,000
we need to place, you know, eight queens let's say, if the board is an eight by eight board. 

781
00:37:50,000 --> 00:37:54,000
So at each call we could place one queen, leaving us with M minus 1 to 

782
00:37:54,000 --> 00:37:55,000
go. 

783
00:37:55,000 --> 00:37:59,000
The choices for that queen might be that one way to kind of 

784
00:37:59,000 --> 00:38:02,000
keep our problem 

785
00:38:02,000 --> 00:38:04,000
-just to manage the logistics of it is to say, well, we know that there's going to be a 

786
00:38:04,000 --> 00:38:07,000
queen in each column, 

787
00:38:07,000 --> 00:38:08,000
right, 

788
00:38:08,000 --> 00:38:10,000
it certainly can't be that there's two in one column. So 

789
00:38:10,000 --> 00:38:13,000
we can just do the problem column by column and say, well, the first thing we'll do is place 

790
00:38:13,000 --> 00:38:16,000
a queen in the leftmost column. 

791
00:38:16,000 --> 00:38:18,000
The next call will make a queen 

792
00:38:18,000 --> 00:38:21,000
-place a queen in the column to the right of that, and then so on. So we'll work our way 

793
00:38:21,000 --> 00:38:23,000
across the board from left to right, 

794
00:38:23,000 --> 00:38:25,000
and then the choices for that queen 

795
00:38:25,000 --> 00:38:27,000
will be any of the [inaudible] 

796
00:38:27,000 --> 00:38:32,000
and some of those actually are -we may be able to easily eliminate as 

797
00:38:32,000 --> 00:38:35,000
possibilities. So, for example, once this queen is down here in the bottommost row, and 

798
00:38:35,000 --> 00:38:40,000
we move on to this next column, there's no reason to even try placing the queen 

799
00:38:40,000 --> 00:38:43,000
right next to it because we can see that that immediately threatens. 

800
00:38:43,000 --> 00:38:46,000
So what we'll try is, is there a spot in this column that 

801
00:38:46,000 --> 00:38:48,000
works given the previous decisions I've made, 

802
00:38:48,000 --> 00:38:51,000
and if so, make that decision and move on. 

803
00:38:51,000 --> 00:38:54,000
And only if we learned that that decision, right, 

804
00:38:54,000 --> 00:39:00,000
that we just made optimistically isn't successful will we back up and try again. 

805
00:39:00,000 --> 00:39:10,000
So let me do a little demo with you. 

806
00:39:10,000 --> 00:39:12,000
Kind of shows this 

807
00:39:12,000 --> 00:39:14,000
doing its job. 

808
00:39:14,000 --> 00:39:17,000
Okay. 

809
00:39:17,000 --> 00:39:20,000
So [inaudible] I'm gonna do it as I said, kind of column by column. 

810
00:39:20,000 --> 00:39:24,000
[Inaudible] is that I'm placing the queen in the leftmost column to begin, and the question 

811
00:39:24,000 --> 00:39:27,000
mark here says this is a spot under consideration. I look at the 

812
00:39:27,000 --> 00:39:29,000
configuration I'm in, 

813
00:39:29,000 --> 00:39:32,000
and I say, is this a plausible place to put the queen? 

814
00:39:32,000 --> 00:39:34,000
And there's no reason not to, 

815
00:39:34,000 --> 00:39:38,000
so I go ahead and let the queen sit there. 

816
00:39:38,000 --> 00:39:42,000
Okay, so now I'm going to make my second recursive call. I say I've placed one queen, now there's three 

817
00:39:42,000 --> 00:39:43,000
more queens to go. 

818
00:39:43,000 --> 00:39:47,000
Why don't we go ahead and place the queens that remain to the right of this. And so 

819
00:39:47,000 --> 00:39:50,000
the next recursive call comes in and says, if you can place the queens given the 

820
00:39:50,000 --> 00:39:54,000
decision I've already made, then tell me yes, and then I'll know all is good. 

821
00:39:54,000 --> 00:39:58,000
So it looks at the bottommost row, and it says, oh, no, that won't work, 

822
00:39:58,000 --> 00:40:00,000
right? There's a queen right there. 

823
00:40:00,000 --> 00:40:03,000
It looks at the next one and then sees the diagonal attack. Okay. Moves up to 

824
00:40:03,000 --> 00:40:05,000
here and says, okay, that's good. 

825
00:40:05,000 --> 00:40:06,000
That'll work, 

826
00:40:06,000 --> 00:40:08,000
right? Looks at all of them and it's okay. 

827
00:40:08,000 --> 00:40:12,000
So now it says, okay, well I've made two decision. There's just two to go. I'm 

828
00:40:12,000 --> 00:40:16,000
feeling good about it. Go ahead and make the recursive call. 

829
00:40:16,000 --> 00:40:19,000
The third call comes in, looks at that row, not good, 

830
00:40:19,000 --> 00:40:21,000
looks at that row, not good, 

831
00:40:21,000 --> 00:40:25,000
looks at that row, not good, looks at that row, not good. Now this one -there weren't any 

832
00:40:25,000 --> 00:40:28,000
options at all that were viable. 

833
00:40:28,000 --> 00:40:30,000
We got here, 

834
00:40:30,000 --> 00:40:35,000
and given the earlier decisions, and so the idea is that, given our optimism, right, we 

835
00:40:35,000 --> 00:40:39,000
sort of made the calls and just sort of moved on. And now we've got in the situation where we 

836
00:40:39,000 --> 00:40:42,000
have tried all the possibilities in this third recursive call and there was 

837
00:40:42,000 --> 00:40:46,000
no way to make progress. It's gonna hit the return false at the bottom of the 

838
00:40:46,000 --> 00:40:47,000
backtracking that says, 

839
00:40:47,000 --> 00:40:50,000
you know what, there was some earlier problem. 

840
00:40:50,000 --> 00:40:50,000


841
00:40:50,000 --> 00:40:54,000
There was no way I could have solved it given the two choices -or, you know, whatever 

842
00:40:54,000 --> 00:40:56,000
-we don't even know what choices were made, but there were some previous choices made, and 

843
00:40:56,000 --> 00:40:58,000
given the state that was passed to this call, 

844
00:40:58,000 --> 00:41:01,000
there's no way to solve it from here. 

845
00:41:01,000 --> 00:41:03,000
And so this is gonna trigger the backtracking. So 

846
00:41:03,000 --> 00:41:06,000
that backtracking is coming back to an earlier decision that you made and unmaking 

847
00:41:06,000 --> 00:41:07,000
it. 

848
00:41:07,000 --> 00:41:12,000
It's a return false coming out of that third call that then causes the second call to 

849
00:41:12,000 --> 00:41:13,000
try again. 

850
00:41:13,000 --> 00:41:17,000
And it goes up and it says okay, well where did I leave off? I tried the first couple of ones. 

851
00:41:17,000 --> 00:41:21,000
Okay, let's try moving it up a notch and see how that goes. 

852
00:41:21,000 --> 00:41:22,000
Then, again, 

853
00:41:22,000 --> 00:41:25,000
optimistic, makes the call and goes for it. 

854
00:41:25,000 --> 00:41:28,000
Can't do this one. That looks good. 

855
00:41:28,000 --> 00:41:31,000
And now we're on our way to placing the last queen, feeling really comfortable and 

856
00:41:31,000 --> 00:41:33,000
confidant, 

857
00:41:33,000 --> 00:41:34,000
but 

858
00:41:34,000 --> 00:41:35,000
discovering quickly, 

859
00:41:35,000 --> 00:41:39,000
right, that there was no possible. So it turns out this configuration with these three 

860
00:41:39,000 --> 00:41:42,000
queens, not solvable. Something must be wrong. 

861
00:41:42,000 --> 00:41:46,000
Back up to the most immediate decision. She knows it doesn't unmake, you know, 

862
00:41:46,000 --> 00:41:50,000
earlier decisions until it really has been proven that that can't work, so 

863
00:41:50,000 --> 00:41:52,000
at this point it says, okay, well let's try finding 

864
00:41:52,000 --> 00:41:53,000
something else in this 

865
00:41:53,000 --> 00:41:54,000
column. 

866
00:41:54,000 --> 00:41:55,000
No go. 

867
00:41:55,000 --> 00:41:58,000
That says, okay, well that one failed so it must be that I made the wrong decision in 

868
00:41:58,000 --> 00:42:01,000
the second column. Well, it turns out the second column -that was the last choice 

869
00:42:01,000 --> 00:42:05,000
it had. So in fact it really was my first decision 

870
00:42:05,000 --> 00:42:08,000
that got us off to the wrong foot. 

871
00:42:08,000 --> 00:42:11,000
And now, having tried everything that there was possible, given the queen in the 

872
00:42:11,000 --> 00:42:14,000
lower left in realizing none of them worked out, it comes back and says, okay, let's 

873
00:42:14,000 --> 00:42:18,000
try again, and at this point it actually will go fairly quickly. 

874
00:42:18,000 --> 00:42:21,000
Making that initial first decision 

875
00:42:21,000 --> 00:42:22,000
was 

876
00:42:22,000 --> 00:42:24,000
the magic that 

877
00:42:24,000 --> 00:42:26,000
got it solved. And 

878
00:42:26,000 --> 00:42:30,000
then we have a complete solution to the queens. 

879
00:42:30,000 --> 00:42:32,000
We put it onto eight, 

880
00:42:32,000 --> 00:42:34,000
and let it go. 

881
00:42:34,000 --> 00:42:38,000
You can see it kind of checking the board, backing up, and you notice that it 

882
00:42:38,000 --> 00:42:42,000
made that lower left decision kind of in -it's sticking to it, and so the idea is 

883
00:42:42,000 --> 00:42:46,000
that it always backs up to the most recent decision point 

884
00:42:46,000 --> 00:42:47,000
when it fails, 

885
00:42:47,000 --> 00:42:50,000
and only after kind of that one has kind of tried all its options will it actually 

886
00:42:50,000 --> 00:42:54,000
back up and consider a previous decision as being unworthy 

887
00:42:54,000 --> 00:43:01,000
and revisiting it. 

888
00:43:01,000 --> 00:43:04,000
In this case that first decision did work out, 

889
00:43:04,000 --> 00:43:06,000
the queen being in the lower left. 

890
00:43:06,000 --> 00:43:09,000
It turns out there were -you know, you saw the second one had to kind of slowly get 

891
00:43:09,000 --> 00:43:12,000
inched up in the second row. Right? It wasn't gonna work with the third row. It tried 

892
00:43:12,000 --> 00:43:15,000
that for a while. Tried the fourth row for a while. 

893
00:43:15,000 --> 00:43:18,000
All the possibilities after that, but eventually it was that fifth row 

894
00:43:18,000 --> 00:43:22,000
that then kind of gave it the breathing room to get those other queens out there. 

895
00:43:22,000 --> 00:43:25,000
But it did not end up trying, for example, all the other positions for the queen in 

896
00:43:25,000 --> 00:43:30,000
the first row, so it actually -it really looked at a much more constrained part of the entire 

897
00:43:30,000 --> 00:43:32,000
search tree than 

898
00:43:32,000 --> 00:43:34,000
an exhaustive recursion 

899
00:43:34,000 --> 00:43:39,000
of the whole thing would have done. 

900
00:43:39,000 --> 00:43:46,000
The code for that ?whoops 

901
00:43:46,000 --> 00:43:48,000
-looks something like this. 

902
00:43:48,000 --> 00:43:49,000
And 

903
00:43:49,000 --> 00:43:51,000
one of the things that I'll strongly encourage you to do when you're writing 

904
00:43:51,000 --> 00:43:54,000
a recursive backtracking routine, 

905
00:43:54,000 --> 00:43:58,000
something I learned from Stuart Regis, who long ago was my mentor, 

906
00:43:58,000 --> 00:43:59,000
was the idea that 

907
00:43:59,000 --> 00:44:03,000
when -trying to make this code look as simple as possible, that one of the things 

908
00:44:03,000 --> 00:44:06,000
you want to do is try to move away the details of the problem. For example, 

909
00:44:06,000 --> 00:44:08,000
like, is safe 

910
00:44:08,000 --> 00:44:12,000
-given the current placement of queens, and the row you're trying, and the column you're at, 

911
00:44:12,000 --> 00:44:15,000
trying to decide that there's not some existing conflict on the board with the 

912
00:44:15,000 --> 00:44:19,000
queen already being threatened by an existing queen just involves us 

913
00:44:19,000 --> 00:44:22,000
kind of traipsing across the grid and looking at different things. 

914
00:44:22,000 --> 00:44:26,000
But putting in its own helper function makes this code much easier to read, right? 

915
00:44:26,000 --> 00:44:28,000
Similarly, placing the queen in the board, removing the queen from the board, 

916
00:44:28,000 --> 00:44:32,000
there are things they need to do. Go up to state and draw some things on the 

917
00:44:32,000 --> 00:44:34,000
graphical display. 

918
00:44:34,000 --> 00:44:37,000
Put all that code somewhere else so you don't have to look at it, and then this 

919
00:44:37,000 --> 00:44:41,000
algorithm can be very easy to read. It's like for all of the row. So given 

920
00:44:41,000 --> 00:44:44,000
the column we're trying to place a queen in, we've got this grid 

921
00:44:44,000 --> 00:44:46,000
of boolean that shows where the queens are so far, 

922
00:44:46,000 --> 00:44:50,000
that for all of the rows across the board, if, 

923
00:44:50,000 --> 00:44:54,000
right, it's safe to place a queen in that row and this column, then place the 

924
00:44:54,000 --> 00:44:56,000
queen and see if you can solve 

925
00:44:56,000 --> 00:44:59,000
starting from the column to the right, given this new update to the board. If it 

926
00:44:59,000 --> 00:45:03,000
worked out, great, nothing more we need to do. Otherwise we need to take back that 

927
00:45:03,000 --> 00:45:05,000
queen, unmake that decision, 

928
00:45:05,000 --> 00:45:06,000
and try again. 

929
00:45:06,000 --> 00:45:09,000
Try a higher row. Try a higher row, right. 

930
00:45:09,000 --> 00:45:13,000
Again, assume it's gonna work out. If it does, great. If it doesn't, unmake it, try 

931
00:45:13,000 --> 00:45:16,000
it again. If we tried all the rows that were open to us, 

932
00:45:16,000 --> 00:45:21,000
and we never got to this case where this returned true, then we return false, which 

933
00:45:21,000 --> 00:45:22,000
causes some 

934
00:45:22,000 --> 00:45:26,000
previous one -we're backing up to a column behind it. So if we were currently trying to 

935
00:45:26,000 --> 00:45:27,000
put a queen in column two, 

936
00:45:27,000 --> 00:45:31,000
and we end up returning false, it's gonna cause column one to unmake a decision 

937
00:45:31,000 --> 00:45:33,000
and move the queen up a little bit higher. 

938
00:45:33,000 --> 00:45:38,000
If all of the options for column one fail, it'll back up to column zero. 

939
00:45:38,000 --> 00:45:41,000
The base case here at the end, is if we ever get to where 

940
00:45:41,000 --> 00:45:45,000
the column is past the number of columns on the board, then that means we placed a queen 

941
00:45:45,000 --> 00:45:47,000
all the way across the board and 

942
00:45:47,000 --> 00:45:50,000
we're in success land. So all 

943
00:45:50,000 --> 00:45:54,000
this code kind of looks the same kind of standing back from it, right, it's 

944
00:45:54,000 --> 00:45:54,000
like, 

945
00:45:54,000 --> 00:45:57,000
for each choice, if you can make that choice, make it. 

946
00:45:57,000 --> 00:46:02,000
If you solved it from here, great, otherwise, unmake that choice. 

947
00:46:02,000 --> 00:46:06,000
Here's my return false when I ran out of options. There's my base case -it says 

948
00:46:06,000 --> 00:46:09,000
if I have gotten to where there's no more decisions to make, I've placed all the 

949
00:46:09,000 --> 00:46:10,000
queens, 

950
00:46:10,000 --> 00:46:14,000
I've chosen all the letters, whatever, did I -am I where I wanted to be? There's no 

951
00:46:14,000 --> 00:46:17,000
some sort of true or false analysis that comes out there about 

952
00:46:17,000 --> 00:46:21,000
being in the right state. How do you feel 

953
00:46:21,000 --> 00:46:24,000
about that? You guys look 

954
00:46:24,000 --> 00:46:24,000
tired today, and 

955
00:46:24,000 --> 00:46:28,000
I didn't even give you an assignment due today, so this can't be my fault, 

956
00:46:28,000 --> 00:46:30,000
right? 

957
00:46:30,000 --> 00:46:33,000
I got a couple more examples, and I'm probably actually just gonna go ahead and try to spend some time on 

958
00:46:33,000 --> 00:46:36,000
them on Monday because I really don't want to -I 

959
00:46:36,000 --> 00:46:37,000
want 

960
00:46:37,000 --> 00:46:38,000
to 

961
00:46:38,000 --> 00:46:41,000
give you a little bit more practice though. So we'll see. We'll see. I'll do at 

962
00:46:41,000 --> 00:46:44,000
least one or two more of them on Monday before we start talking about pointers and linked lists, and so 

963
00:46:44,000 --> 00:47:00,000
I will see you then. But having a good weekend. Come and hang out in Turbine with me.