WEBVTT 00:00:00.000 --> 00:00:11.000 00:00:11.000 --> 00:00:14.000 This presentation is delivered by the Stanford Center for Professional Development. 00:00:23.000 --> 00:00:27.000 Today I'm gonna keep talking a little bit more about another procedural recursion example and 00:00:27.000 --> 00:00:31.000 then go on to talk about, kind of, the approach for recursive backtracking, 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. 00:00:36.000 --> 00:00:39.000 This is the last problem I did at the end of 00:00:39.000 --> 00:00:42.000 Wednesday's lecture. It's a very, very important problem, so I don't actually 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 00:00:46.000 --> 00:00:47.000 guys that we're 00:00:47.000 --> 00:00:49.000 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 00:00:51.000 --> 00:00:55.000 other solutions end up just becoming permutations, you know, at the core of it. 00:00:55.000 --> 00:00:56.000 So it's 00:00:56.000 --> 00:01:01.000 a pretty useful pattern to have [inaudible] 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 00:01:05.000 --> 00:01:07.000 gonna print all the A C D A B C D 00:01:07.000 --> 00:01:12.000 A variations that you can get by rearranging all the letters. 00:01:12.000 --> 00:01:15.000 It's a deceptively short piece of 00:01:15.000 --> 00:01:17.000 code that does what's being done here 00:01:17.000 --> 00:01:20.000 -is that it breaks it down in terms of there being the permutation that's 00:01:20.000 --> 00:01:24.000 assembled so far, and then the remaining characters that haven't yet been looked 00:01:24.000 --> 00:01:25.000 at, and so 00:01:25.000 --> 00:01:27.000 at each recursive call it's gonna 00:01:27.000 --> 00:01:30.000 shuffle one character from the 00:01:30.000 --> 00:01:33.000 remainder onto the thing that's been chosen so far. So chose the next 00:01:33.000 --> 00:01:37.000 character in the permutation, and eventually, when the rest is empty, 00:01:37.000 --> 00:01:41.000 then all of the characters have been moved over, and have been laid down in 00:01:41.000 --> 00:01:44.000 permutation, then what I have is a full permutation of the length end. 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 00:01:48.000 --> 00:01:52.000 choices is exactly equal to the number of characters I have left in 00:01:52.000 --> 00:01:53.000 rest, 00:01:53.000 --> 00:01:55.000 and for each of the remaining characters at this point, maybe there's just C 00:01:55.000 --> 00:01:56.000 and D left, 00:01:56.000 --> 00:01:58.000 then I'm gonna try each of them 00:01:58.000 --> 00:02:03.000 as the next character in the permutation, and then permute what remains after 00:02:03.000 --> 00:02:04.000 having made that choice. 00:02:04.000 --> 00:02:05.000 And so this is 00:02:05.000 --> 00:02:07.000 [inaudible] operations here of 00:02:07.000 --> 00:02:09.000 attaching that [inaudible] 00:02:09.000 --> 00:02:13.000 into the existing so far, and then subtracting it 00:02:13.000 --> 00:02:14.000 out of the rest 00:02:14.000 --> 00:02:18.000 to set up the arguments for that recursive call. A 00:02:18.000 --> 00:02:21.000 little bit at the end we talked about this idea of a wrapper function where 00:02:21.000 --> 00:02:24.000 the interface to list permutations from a client point of view probably just wants to 00:02:24.000 --> 00:02:26.000 be, here's a string to permute 00:02:26.000 --> 00:02:27.000 the fact that [inaudible] 00:02:27.000 --> 00:02:31.000 keep this housekeeping of what I've built so far is really any internal management 00:02:31.000 --> 00:02:34.000 issue, and isn't what I want to expose as part of the interface, 00:02:34.000 --> 00:02:37.000 so we in turn have just a really simple one line translation that the outer 00:02:37.000 --> 00:02:40.000 call just sets up and makes the call to the real recursive function setting up 00:02:40.000 --> 00:02:44.000 the right state for the housekeeping in this case, which is the 00:02:44.000 --> 00:02:47.000 permutation we've assembled at this point. 00:02:47.000 --> 00:02:50.000 So 00:02:50.000 --> 00:02:53.000 I'd like to ask you a few questions about this 00:02:53.000 --> 00:02:56.000 to see if we're kind of seeing the same things. Can 00:02:56.000 --> 00:03:00.000 someone tell me what is the first permutation that's printed by this 00:03:00.000 --> 00:03:14.000 if I put in the string A B C D? 00:03:14.000 --> 00:03:17.000 Anyone want to help me? 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, 00:03:21.000 --> 00:03:23.000 the very first time, and that's because, 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 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 00:03:29.000 --> 00:03:32.000 the next character of rest and attach it to the permutation 00:03:32.000 --> 00:03:36.000 as its first time through the for loop. So the first time through the very first 00:03:36.000 --> 00:03:38.000 for loop it's got A B C D to chose, it chooses A, 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 00:03:43.000 --> 00:03:46.000 next call does exactly the same thing, chooses the first of what remains, which 00:03:46.000 --> 00:03:49.000 is B, attaches it to the permutation and keeps going. 00:03:49.000 --> 00:03:50.000 So the kind of 00:03:50.000 --> 00:03:53.000 deep arm of the recursion making that first choice and working its way down to 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 00:03:57.000 --> 00:03:57.000 the 00:03:57.000 --> 00:04:01.000 -and bottoms on the recursion before it comes back and revisits any previous 00:04:01.000 --> 00:04:03.000 decision, will go A B C D, 00:04:03.000 --> 00:04:04.000 and then 00:04:04.000 --> 00:04:08.000 eventually come back and start trying other things, but that very first one, 00:04:08.000 --> 00:04:11.000 right, is all just the sequence there. 00:04:11.000 --> 00:04:13.000 The next one that's after it, right, 00:04:13.000 --> 00:04:14.000 is A B D C, 00:04:14.000 --> 00:04:17.000 which involved unmaking those last couple decisions. 00:04:17.000 --> 00:04:19.000 If I look at 00:04:19.000 --> 00:04:22.000 the tree that I have here that may help to sort of identify it. 00:04:22.000 --> 00:04:24.000 That permute of emptying A B C, 00:04:24.000 --> 00:04:27.000 the first choice it makes is go with A, and then the 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 00:04:30.000 --> 00:04:34.000 printed our here will be A B C D, we get to the base case. 00:04:34.000 --> 00:04:36.000 Once it's tried this, it'll come back to this one, and on this 00:04:36.000 --> 00:04:39.000 one it'll say, well, try the other characters. Well, there's no other 00:04:39.000 --> 00:04:41.000 characters. In fact, this one also finishes. 00:04:41.000 --> 00:04:46.000 It'll get back to here as it unwinds the stack the way the stack 00:04:46.000 --> 00:04:49.000 gets back to where it was previously in these recursive calls. And now it says, okay, 00:04:49.000 --> 00:04:51.000 and now try the ones that have, 00:04:51.000 --> 00:04:54.000 on the second iteration of that for loop, D in the front, 00:04:54.000 --> 00:04:56.000 and so it ends up putting A B D together, 00:04:56.000 --> 00:04:58.000 leaving C, and then getting A B D C. And 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 00:05:02.000 --> 00:05:03.000 in the front. 00:05:03.000 --> 00:05:06.000 There are eight of them. 00:05:06.000 --> 00:05:07.000 I believe three, two 00:05:07.000 --> 00:05:10.000 -no, six. Six of them 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 00:05:14.000 --> 00:05:18.000 working out that whole part, which involves kind of the [inaudible] of this whole arm, 00:05:18.000 --> 00:05:21.000 will eventually unwind back to the initial permute call, 00:05:21.000 --> 00:05:22.000 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 00:05:26.000 --> 00:05:28.000 down from reading the A C D behind it. 00:05:28.000 --> 00:05:30.000 So we'll see all the As 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 00:05:33.000 --> 00:05:36.000 bunch that leads with D. 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 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 00:05:42.000 --> 00:05:44.000 is the sense of being 00:05:44.000 --> 00:05:46.000 able to look at that recursive code, 00:05:46.000 --> 00:05:50.000 and use your mind to kind of trace its activity and think about the 00:05:50.000 --> 00:05:54.000 progress that is made through those recursive calls. Just 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 00:05:57.000 --> 00:05:59.000 highlight for you. 00:05:59.000 --> 00:06:05.000 00:06:05.000 --> 00:06:08.000 I think that's about what 00:06:08.000 --> 00:06:08.000 it's gonna do. 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 00:06:11.000 --> 00:06:15.000 would be an excellent time for you to ask a question that I could help 00:06:15.000 --> 00:06:17.000 kind of get your understanding 00:06:17.000 --> 00:06:19.000 made more clear. So 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. 00:06:24.000 --> 00:06:29.000 Is there a simple change you can make to this 00:06:29.000 --> 00:06:29.000 code 00:06:29.000 --> 00:06:32.000 so that it does combinations [inaudible]? 00:06:32.000 --> 00:06:36.000 Does combinations -you mean, like, will skip letters? 00:06:36.000 --> 00:06:42.000 Right. Yes. It turns out we're gonna make that change in not five minutes. 00:06:42.000 --> 00:06:45.000 In effect, what you would do -and there's a pretty simple change with 00:06:45.000 --> 00:06:47.000 this form. I'm gonna show you a slightly different way of doing it, 00:06:47.000 --> 00:06:48.000 but one way of doing it would be to say, 00:06:48.000 --> 00:06:52.000 well, give me the letter, don't attach it to next right? So right now, the 00:06:52.000 --> 00:06:56.000 choices are pick one of the letters that remain and then attach it to 00:06:56.000 --> 00:07:00.000 the permutation. Another option you could do was pick a letter and just discard it, 00:07:00.000 --> 00:07:03.000 right? And so, in which case, I wouldn't add it into so far. 00:07:03.000 --> 00:07:06.000 I would still subtract it from here, and I'd make another recursive call 00:07:06.000 --> 00:07:07.000 saying, now 00:07:07.000 --> 00:07:10.000 how about the permutations that don't involve A at all? And 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 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 00:07:17.000 --> 00:07:21.000 formulate the same thing in a little bit, but 00:07:21.000 --> 00:07:27.000 -anybody want to own up to having something that confuses them? [Inaudible] ask how you, like, 00:07:27.000 --> 00:07:29.000 what you would set up to test it? 00:07:29.000 --> 00:07:30.000 So [inaudible] one of 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 00:07:33.000 --> 00:07:35.000 here just in case, right, 00:07:35.000 --> 00:07:38.000 hoping you would 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, 00:07:41.000 --> 00:07:44.000 you know, throw some strings at it and see what happens, right? 00:07:44.000 --> 00:07:45.000 And so 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 00:07:49.000 --> 00:07:49.000 string, 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 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, 00:07:55.000 --> 00:07:58.000 right, immediately realizes there's no choices and it says, well, look, there's nothing to 00:07:58.000 --> 00:08:00.000 print other than that empty string. 00:08:00.000 --> 00:08:02.000 What if I give it a single character string? 00:08:02.000 --> 00:08:04.000 Right? I get that string back. I'm like, 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 00:08:07.000 --> 00:08:09.000 the base case on the subsequent one. 00:08:09.000 --> 00:08:12.000 Now I start doing better ones. A and B, 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 00:08:16.000 --> 00:08:17.000 the front, 00:08:17.000 --> 00:08:20.000 and I put the B A behind, 00:08:20.000 --> 00:08:21.000 then hopefully what I believe is that 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 00:08:24.000 --> 00:08:27.000 behind it, and then similarly on down. 00:08:27.000 --> 00:08:30.000 So some simple cases that I can see 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 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 00:08:37.000 --> 00:08:40.000 go in the front, and then the back end rearrangement. And kind of seeing the 00:08:40.000 --> 00:08:44.000 pattern that matches my belief about how the code works, right, 00:08:44.000 --> 00:08:45.000 helps me to feel good. What happens if I 00:08:45.000 --> 00:08:48.000 put in 00:08:48.000 --> 00:08:50.000 something that has double letters in it? 00:08:50.000 --> 00:08:53.000 So I put A P P L E in there. 00:08:53.000 --> 00:08:56.000 And all the way back at the beginning, right, I can 00:08:56.000 --> 00:08:58.000 plot more of them, right, that grows quite 00:08:58.000 --> 00:09:02.000 quickly right as we add more and more letters, right? Seeing the apple, appel, 00:09:02.000 --> 00:09:02.000 and stuff like that. 00:09:02.000 --> 00:09:05.000 There's a point where it starts picking the P to go in the front, 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 00:09:10.000 --> 00:09:11.000 and this P really being different. 00:09:11.000 --> 00:09:13.000 So it goes through a whole sequence of 00:09:13.000 --> 00:09:17.000 pull the second character to the front, and then permute the remaining four. 00:09:17.000 --> 00:09:20.000 And then it says, and now pull the third character to the front and permute 00:09:20.000 --> 00:09:22.000 the remaining four, which turns out to be exactly the same thing. So there should be 00:09:22.000 --> 00:09:25.000 this whole sequence in the middle, right, 00:09:25.000 --> 00:09:27.000 of the same Ps 00:09:27.000 --> 00:09:29.000 repeated twice 00:09:29.000 --> 00:09:31.000 because we haven't gone over a way to do anything about that, right? 00:09:31.000 --> 00:09:33.000 So 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 00:09:36.000 --> 00:09:38.000 there being two double letters. [Inaudible] if I do this -if I just say A 00:09:38.000 --> 00:09:41.000 B A, right? 00:09:41.000 --> 00:09:44.000 Something a little bit smaller to look at, right? 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 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 00:09:50.000 --> 00:09:51.000 the front. 00:09:51.000 --> 00:09:53.000 So right now, it doesn't know that there's anything to worry about in terms 00:09:53.000 --> 00:09:55.000 of duplicates? 00:09:55.000 --> 00:09:57.000 What's a really easy way to get rid of duplicates? 00:09:57.000 --> 00:09:59.000 Don't think recursively, think -use a set. 00:09:59.000 --> 00:10:01.000 Right? I could just stuff them in a set, right? 00:10:01.000 --> 00:10:04.000 And then if it comes across the same one again it's like, yeah, 00:10:04.000 --> 00:10:07.000 whatever. So it would still do the extra work of finding those down, 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. 00:10:11.000 --> 00:10:13.000 To 00:10:13.000 --> 00:10:15.000 actually change it in the code, 00:10:15.000 --> 00:10:18.000 it's actually not that hard either. 00:10:18.000 --> 00:10:19.000 The idea here is that 00:10:19.000 --> 00:10:21.000 for all of the characters that remain, right, 00:10:21.000 --> 00:10:25.000 and sometimes what I want to choose from is of the remaining characters 00:10:25.000 --> 00:10:25.000 uniqued, 00:10:25.000 --> 00:10:27.000 right? Pick one to move to the front. 00:10:27.000 --> 00:10:29.000 So if there's three more Ps 00:10:29.000 --> 00:10:31.000 that remain in rest, 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 00:10:34.000 --> 00:10:37.000 the same result -pulling one and leaving the other two behind 00:10:37.000 --> 00:10:39.000 is completely irrelevant. 00:10:39.000 --> 00:10:42.000 So an easy way to actually stop it from even generating them, 00:10:42.000 --> 00:10:46.000 is when looking at the character here is to make sure that it is -that it 00:10:46.000 --> 00:10:50.000 doesn't duplicate anything else in the rest. And so 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 00:10:53.000 --> 00:10:57.000 of the Ps, right, and to recur on and ignore the other ones. 00:10:57.000 --> 00:11:00.000 So, for example, if right here I did a find on the rest 00:11:00.000 --> 00:11:02.000 after I -do you see any more of these? 00:11:02.000 --> 00:11:04.000 And if you do, 00:11:04.000 --> 00:11:07.000 then skip it and just let those go. Or, you know, 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 00:11:10.000 --> 00:11:13.000 right and see if you see any more, and if so, 00:11:13.000 --> 00:11:14.000 skip the, 00:11:14.000 --> 00:11:19.000 you know, early or later ones depending on what your strategy is. 00:11:19.000 --> 00:11:25.000 Any questions about permute here? [Inaudible]. 00:11:25.000 --> 00:11:27.000 So the [inaudible] can be just -look down here, right, it just looks like that, right? 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 00:11:31.000 --> 00:11:33.000 outer call, right, it tends to have this sort of 00:11:33.000 --> 00:11:34.000 this, you know, solve this problem, 00:11:34.000 --> 00:11:37.000 and then it turns out during the recursive calls you need to maintain some state 00:11:37.000 --> 00:11:40.000 about where you are in the problem. You know, like, how many letters you moved, or 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 00:11:44.000 --> 00:11:45.000 trying to solve. 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 00:11:49.000 --> 00:11:52.000 way that has the initial form of that state 00:11:52.000 --> 00:11:52.000 present 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 00:11:56.000 --> 00:11:58.000 setting up. 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 00:12:01.000 --> 00:12:04.000 into, basically, it's just exchanging 00:12:04.000 --> 00:12:06.000 -setting up the 00:12:06.000 --> 00:12:11.000 other parameters. 00:12:11.000 --> 00:12:13.000 I 00:12:13.000 --> 00:12:17.000 am going to show you the other kind of master patter, and 00:12:17.000 --> 00:12:20.000 then we're gonna go on to kind of use them to solve other problems. 00:12:20.000 --> 00:12:24.000 This is the one that was already alluded to, this idea of a combinations. Instead 00:12:24.000 --> 00:12:26.000 of actually producing all of the four character strings that involve 00:12:26.000 --> 00:12:28.000 rearrangements of A B C D, 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 00:12:32.000 --> 00:12:34.000 characters out of that 00:12:34.000 --> 00:12:35.000 initial input, and 00:12:35.000 --> 00:12:39.000 potentially exclude some, potentially include some? So if I have A B C, 00:12:39.000 --> 00:12:41.000 then the subsets of the subgroups of that 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 00:12:45.000 --> 00:12:50.000 full one, and then the combinations of two, A B, A C, and B C. 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 00:12:53.000 --> 00:12:54.000 about order, I'm 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 00:12:57.000 --> 00:12:59.000 B A I'm gonna consider it the same subset. 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? 00:13:05.000 --> 00:13:09.000 And so the recursive strategy we're gonna take is exactly what I have just 00:13:09.000 --> 00:13:12.000 kind of alluded to in my English description there, 00:13:12.000 --> 00:13:15.000 is that I've got an input, A B C. 00:13:15.000 --> 00:13:18.000 Each of those elements has either the opportunity of being in the subset or 00:13:18.000 --> 00:13:19.000 not. 00:13:19.000 --> 00:13:21.000 And I need to make that decision for everyone 00:13:21.000 --> 00:13:25.000 -every single element, and then I need to kind of explore all the possible 00:13:25.000 --> 00:13:26.000 combinations of that, right? 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? 00:13:29.000 --> 00:13:32.000 So the recursion that I'm gonna use here 00:13:32.000 --> 00:13:35.000 is that at each step of the way, I'm gonna separate one element from the 00:13:35.000 --> 00:13:36.000 input, 00:13:36.000 --> 00:13:39.000 and probably the easiest way to do that is just to kind of take the front 00:13:39.000 --> 00:13:40.000 most element off the input 00:13:40.000 --> 00:13:42.000 and sort of 00:13:42.000 --> 00:13:45.000 separate it into this character by itself and then the remainder. Similarly, the way 00:13:45.000 --> 00:13:46.000 I did with permute, 00:13:46.000 --> 00:13:49.000 and then given that element I have 00:13:49.000 --> 00:13:51.000 earmarked here, I can 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 00:13:54.000 --> 00:13:56.000 two recursive calls here, 00:13:56.000 --> 00:13:58.000 one recursive call where I've added it in, 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 00:14:02.000 --> 00:14:04.000 removed it from the rest, 00:14:04.000 --> 00:14:08.000 so what's being chosen from to complete that subset 00:14:08.000 --> 00:14:10.000 always is a little bit smaller, a little bit easier. 00:14:10.000 --> 00:14:14.000 So this is very, very much like the problem I described as the chose 00:14:14.000 --> 00:14:18.000 problem. Trying to choose four people from a dorm to go to flicks was 00:14:18.000 --> 00:14:19.000 picking Bob 00:14:19.000 --> 00:14:21.000 and then -[inaudible] to Bob and not Bob, and then 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, 00:14:25.000 --> 00:14:29.000 or Bob could not go and I need to pick four people to go without Bob. 00:14:29.000 --> 00:14:34.000 This is very much that same pattern. Two recursive calls. Identify one in or out. 00:14:34.000 --> 00:14:36.000 The base case becomes when there's nothing left 00:14:36.000 --> 00:14:39.000 to check out. 00:14:39.000 --> 00:14:41.000 So I start with the input A B C -A 00:14:41.000 --> 00:14:42.000 B C D let's say. 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 00:14:45.000 --> 00:14:47.000 easy one to get to. 00:14:47.000 --> 00:14:48.000 I add it to the subset, 00:14:48.000 --> 00:14:52.000 remove it from the input, and make a recursive call. 00:14:52.000 --> 00:14:54.000 When that recursion completely terminates, 00:14:54.000 --> 00:14:56.000 I get back to this call, 00:14:56.000 --> 00:14:58.000 and I do the same thing again. 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 00:15:02.000 --> 00:15:03.000 include. 00:15:03.000 --> 00:15:05.000 So inclusion exclusion 00:15:05.000 --> 00:15:13.000 are the two things that I'm trying. So the 00:15:13.000 --> 00:15:16.000 subset problem, right, very similar in structure to the way that I set 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 00:15:20.000 --> 00:15:20.000 down 00:15:20.000 --> 00:15:24.000 the remainder in the rest, right, things that I haven't yet explored 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. 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 00:15:32.000 --> 00:15:33.000 more choices to make, 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. 00:15:37.000 --> 00:15:38.000 In the case that there's still something to look at 00:15:38.000 --> 00:15:41.000 I make these two calls, 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 00:15:44.000 --> 00:15:47.000 have subtracted it off of the 00:15:47.000 --> 00:15:49.000 rest by using the subster to 00:15:49.000 --> 00:15:55.000 truncate that front character off. 00:15:55.000 --> 00:15:56.000 So the way that 00:15:56.000 --> 00:15:57.000 permute was making calls, right, was in a loop, 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 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, 00:16:03.000 --> 00:16:06.000 potentially, end recursive calls where end is the length of 00:16:06.000 --> 00:16:08.000 the input. 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 00:16:10.000 --> 00:16:13.000 characters are in rest is how many recursive calls it makes. 00:16:13.000 --> 00:16:17.000 The subsets code actually makes exactly two recursive calls at any given stage, in or out, 00:16:17.000 --> 00:16:21.000 and then recurs on that and what is one remaining. 00:16:21.000 --> 00:16:23.000 It also needs a wrapper 00:16:23.000 --> 00:16:26.000 for the same exact reason that permutations did. It's 00:16:26.000 --> 00:16:28.000 just that we are trying to 00:16:28.000 --> 00:16:29.000 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 00:16:32.000 --> 00:16:36.000 with it. We're just trying the subset so far is something we don't necessarily 00:16:36.000 --> 00:16:38.000 want to put into the public interface in the way that somebody would have to 00:16:38.000 --> 00:16:44.000 know what to pass to that to get the right thing. Anybody have 00:16:44.000 --> 00:16:48.000 a question about this? 00:16:48.000 --> 00:16:50.000 So given the way this code is written, 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? 00:17:05.000 --> 00:17:07.000 A B C D. Just like it was with permute, right? Everything went in. 00:17:07.000 --> 00:17:19.000 What is the second one printed after that? 00:17:19.000 --> 00:17:20.000 A B C, right? So I'm 00:17:20.000 --> 00:17:22.000 gonna look at my little diagram with you 00:17:22.000 --> 00:17:27.000 to help kind of trace this process of the recursive call, right, is that 00:17:27.000 --> 00:17:31.000 the leftmost arm is the inclusion arm, the right arm is the exclusion arm. 00:17:31.000 --> 00:17:34.000 At every level of the tree, right, we're looking at the next character of 00:17:34.000 --> 00:17:36.000 the rest and deciding whether to go in or out, 00:17:36.000 --> 00:17:38.000 the first call it makes is always in, 00:17:38.000 --> 00:17:41.000 so at the beginning it says, I'm choosing about A. Is A in? Sure. 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 00:17:44.000 --> 00:17:48.000 thing of rest, that's B. Is B in? Sure. Goes down the right arm, right? 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 00:17:52.000 --> 00:17:54.000 have [inaudible] A B C D. 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 00:17:58.000 --> 00:18:01.000 make. We've looked at every letter and decided whether it was in or out. 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 00:18:05.000 --> 00:18:06.000 with D in, 00:18:06.000 --> 00:18:09.000 how about we try it with D out. And so then D out 00:18:09.000 --> 00:18:11.000 gives us just the A B C. 00:18:11.000 --> 00:18:13.000 After it's done everything it can do with 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, 00:18:17.000 --> 00:18:21.000 and this will drop C off, and then try D in, D out. 00:18:21.000 --> 00:18:25.000 And so it will go from the biggest sets to the smaller sets, not quite 00:18:25.000 --> 00:18:26.000 monotonically though. 00:18:26.000 --> 00:18:28.000 The very last set printed will be the empty set, 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 00:18:31.000 --> 00:18:34.000 all these combinations of in out, in out, in out, it 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 00:18:37.000 --> 00:18:40.000 empty set on that arm. 00:18:40.000 --> 00:18:43.000 Again, if I reverse the calls, right, I'd still see all the same subsets in 00:18:43.000 --> 00:18:46.000 the end. They just come out in a different order. 00:18:46.000 --> 00:18:50.000 But it is worthwhile to model the recursion in your own head to have this 00:18:50.000 --> 00:18:54.000 idea of understanding about how it goes deep, right? That 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 00:18:57.000 --> 00:19:00.000 base case and terminate that recursion before it will unfold 00:19:00.000 --> 00:19:03.000 and revisit the second call that was made, and 00:19:03.000 --> 00:19:11.000 then fully explore where it goes before it completes that whole sequence. 00:19:11.000 --> 00:19:16.000 Anybody want to ask me a question about these guys? These are 00:19:16.000 --> 00:19:21.000 just really, really important pieces of code, and so I'm trying to 00:19:21.000 --> 00:19:25.000 make sure that I don't move past something that still feels a little bit 00:19:25.000 --> 00:19:27.000 mystical or confusing to you because 00:19:27.000 --> 00:19:29.000 everything I want to do for the rest of today 00:19:29.000 --> 00:19:30.000 builds on this. 00:19:30.000 --> 00:19:33.000 So now if there's something about either of these pieces of code 00:19:33.000 --> 00:19:38.000 that would help you -yeah. What would 00:19:38.000 --> 00:19:40.000 be the simplest way to do that? 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, 00:19:43.000 --> 00:19:45.000 would be to put them in a set, right, and then 00:19:45.000 --> 00:19:47.000 have the set be the order for you. So you said 00:19:47.000 --> 00:19:49.000 order doesn't matter? Oh, you 00:19:49.000 --> 00:19:53.000 did care about how they got ordered. So, like, let's say you 00:19:53.000 --> 00:19:57.000 didn't want B C D to equal C D B. 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 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, 00:20:04.000 --> 00:20:05.000 well 00:20:05.000 --> 00:20:07.000 I'm gonna chose -so in this case, right, 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 00:20:11.000 --> 00:20:14.000 say if the input was the alphabet, just easy way 00:20:14.000 --> 00:20:15.000 to describe it, 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 00:20:19.000 --> 00:20:19.000 or not. 00:20:19.000 --> 00:20:23.000 If I really wanted B Z to be distinct from Z B, 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, 00:20:27.000 --> 00:20:28.000 00:20:28.000 --> 00:20:29.000 and not 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 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 00:20:36.000 --> 00:20:38.000 remains and recur, 00:20:38.000 --> 00:20:40.000 and that I need that separate step we talked about of -and 00:20:40.000 --> 00:20:42.000 in addition to kind of 00:20:42.000 --> 00:20:43.000 00:20:43.000 --> 00:20:45.000 picking, we also have to 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 00:20:48.000 --> 00:20:50.000 could [inaudible] or not. And 00:20:50.000 --> 00:20:54.000 so permute always assumes we have to have picked everything. The subset code 00:20:54.000 --> 00:20:57.000 would also allow for 00:20:57.000 --> 00:20:58.000 some of them just being entirely skipped. 00:20:58.000 --> 00:21:02.000 So we pick the next one, right, and then eventually 00:21:02.000 --> 00:21:04.000 stopped picking. 00:21:04.000 --> 00:21:07.000 [Inaudible] just in your wrapper function 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. 00:21:13.000 --> 00:21:16.000 So there's often very, you know, 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 00:21:19.000 --> 00:21:20.000 outside the recursion, 00:21:20.000 --> 00:21:22.000 have the set help you do it or not, 00:21:22.000 --> 00:21:26.000 that can get you the same result. 00:21:26.000 --> 00:21:28.000 So let me try to 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 00:21:32.000 --> 00:21:33.000 kind of 00:21:33.000 --> 00:21:36.000 move just to see how these are more similar than they are different, right, 00:21:36.000 --> 00:21:40.000 even though the code ends up kind of being -having some details in it 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 00:21:43.000 --> 00:21:45.000 about 00:21:45.000 --> 00:21:45.000 choice. 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 00:21:50.000 --> 00:21:53.000 that actually relates to the problem if you think about it in terms of decisions, 00:21:53.000 --> 00:21:57.000 that in making a permutation your decision is what character goes next, right? In the 00:21:57.000 --> 00:22:01.000 subset it's like, well, whether this character goes in or not 00:22:01.000 --> 00:22:05.000 that the recursive tree that I was drawing that it shows all those calls, 00:22:05.000 --> 00:22:09.000 the depths of it represents the number of choices you make. Each 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 00:22:13.000 --> 00:22:15.000 there. So I make, you know, 00:22:15.000 --> 00:22:18.000 one of those calls, and then there's N minus 1 beneath it that represent 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 00:22:22.000 --> 00:22:23.000 picked the, you 00:22:23.000 --> 00:22:25.000 know, N minus 1 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 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 00:22:31.000 --> 00:22:32.000 done. 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 00:22:35.000 --> 00:22:37.000 whether it's in or out. So I 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 00:22:40.000 --> 00:22:41.000 way down. 00:22:41.000 --> 00:22:42.000 That was the life of the input. 00:22:42.000 --> 00:22:44.000 The branching 00:22:44.000 --> 00:22:48.000 represents how many recursive calls were made 00:22:48.000 --> 00:22:52.000 at each level of the recursion. In the case of subsets, it's always exactly two. 00:22:52.000 --> 00:22:54.000 In, out, all the way down, 00:22:54.000 --> 00:22:59.000 restarts at 1, branches to 2, goes to 4, goes to 8, 16, and so on. 00:22:59.000 --> 00:23:01.000 In the permute case, right, 00:23:01.000 --> 00:23:05.000 there are N calls at the beginning. I have N different letters to choose from, so 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. 00:23:10.000 --> 00:23:12.000 Still very wide. And N minus 2. And 00:23:12.000 --> 00:23:16.000 so the overall tree has kind of an N times N minus 1 times N minus 00:23:16.000 --> 00:23:19.000 2 all the way down to the bottom, which the factorial function 00:23:19.000 --> 00:23:22.000 -which grows very, very quickly. 00:23:22.000 --> 00:23:26.000 Even for small inputs, right, the number of permutations is enormous. 00:23:26.000 --> 00:23:28.000 The number of subsets is to the end 00:23:28.000 --> 00:23:29.000 00:23:29.000 --> 00:23:30.000 in or out, right, all the way across. 00:23:30.000 --> 00:23:32.000 Also, a very, 00:23:32.000 --> 00:23:34.000 you know, 00:23:34.000 --> 00:23:37.000 resource intensive problem to solve, not nearly as bad as permutation, but both of 00:23:37.000 --> 00:23:41.000 them, even for small sizes of N, start to become pretty quickly intractable. 00:23:41.000 --> 00:23:44.000 This is not the fault of recursion, right, these problems are not hard to solve because 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 00:23:48.000 --> 00:23:49.000 [inaudible] different subsets, 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 00:23:52.000 --> 00:23:56.000 to do N factorial work to do so. You can't avoid it. 00:23:56.000 --> 00:23:59.000 There's a big amount of work to be done in there. 00:23:59.000 --> 00:24:02.000 But what we're trying to look at here is this idea that those trees, right, 00:24:02.000 --> 00:24:04.000 represent decisions. 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, 00:24:08.000 --> 00:24:09.000 which then 00:24:09.000 --> 00:24:11.000 is kind of a little bit closer 00:24:11.000 --> 00:24:14.000 to having no more decisions to make. You have so many decisions to make, which is 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 00:24:18.000 --> 00:24:19.000 and you're done. The 00:24:19.000 --> 00:24:23.000 tree being very wide and very deep makes for expensive exploration. 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 00:24:27.000 --> 00:24:31.000 problem, one that fundamentally could be exhaustive, exhaustive meaning tried every 00:24:31.000 --> 00:24:35.000 possible combination, every possible rearrangement and option, 00:24:35.000 --> 00:24:38.000 and only explore some part of the tree. 00:24:38.000 --> 00:24:41.000 So only look around in some region, 00:24:41.000 --> 00:24:43.000 and as soon as we find something that's good enough. 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 00:24:46.000 --> 00:24:50.000 this space that could potentially cause us to look at every option, 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, 00:24:54.000 --> 00:24:57.000 that get us to our goal, or whatever it is we're looking for, 00:24:57.000 --> 00:25:00.000 we won't have to keep working any farther. So I'm gonna show 00:25:00.000 --> 00:25:03.000 you how we can take an exhaustive recursion problem and turn it into 00:25:03.000 --> 00:25:06.000 what's called a recursive backtracker. So 00:25:06.000 --> 00:25:07.000 there's 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 00:25:10.000 --> 00:25:12.000 get at. 00:25:12.000 --> 00:25:13.000 That 00:25:13.000 --> 00:25:14.000 00:25:14.000 --> 00:25:17.000 the idea behind permutations or subsets is that at every level there's all 00:25:17.000 --> 00:25:20.000 these choices and we're gonna try every single one of them. 00:25:20.000 --> 00:25:25.000 Now imagine we were gonna make a little bit less a guarantee about that. 00:25:25.000 --> 00:25:26.000 Let's design the function 00:25:26.000 --> 00:25:30.000 to return some sort of state that's like I succeeded or I failed. Did 00:25:30.000 --> 00:25:33.000 I find what I was looking for? 00:25:33.000 --> 00:25:33.000 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 00:25:38.000 --> 00:25:40.000 from what's there. 00:25:40.000 --> 00:25:42.000 I'm gonna go ahead and make the choice, 00:25:42.000 --> 00:25:44.000 make the recursive call, 00:25:44.000 --> 00:25:47.000 and then catch the result from that recursive call, and see whether it 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? 00:25:51.000 --> 00:25:52.000 If it did, 00:25:52.000 --> 00:25:53.000 then I'm done. 00:25:53.000 --> 00:25:56.000 I won't try anything else. So I'll stop early, 00:25:56.000 --> 00:25:59.000 quite going around the for loop, quit making other recursive calls, 00:25:59.000 --> 00:26:02.000 and just immediately [inaudible] say I'm done. 00:26:02.000 --> 00:26:03.000 If it didn't 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 00:26:07.000 --> 00:26:10.000 want to do, then I'll try a different choice. 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 00:26:14.000 --> 00:26:17.000 make a choice, assume it's a good one, and go with it. 00:26:17.000 --> 00:26:19.000 Only when you learn it didn't work out 00:26:19.000 --> 00:26:23.000 do you revisit that decision and back up and try again. 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 00:26:27.000 --> 00:26:28.000 I 00:26:28.000 --> 00:26:30.000 do it in terms of looking at what the code looks like. 00:26:30.000 --> 00:26:35.000 This is the pseudo code at which all recursive backtrackers at their heart 00:26:35.000 --> 00:26:37.000 come down to this pattern. 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 00:26:41.000 --> 00:26:44.000 problem, and what's the configuration? That depends on the domain and the problem 00:26:44.000 --> 00:26:45.000 we're trying to solve. 00:26:45.000 --> 00:26:48.000 But the structure of them all looks the same in that sense that 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 00:26:53.000 --> 00:26:54.000 problem. 00:26:54.000 --> 00:26:56.000 There are a bunch of choices to be made. 00:26:56.000 --> 00:26:58.000 Each [inaudible] will make one choice 00:26:58.000 --> 00:27:00.000 and then attempt to recursively solve it. So 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 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 00:27:07.000 --> 00:27:10.000 maze. Any of these things could be the choices here. 00:27:10.000 --> 00:27:11.000 We make a choice, 00:27:11.000 --> 00:27:13.000 we feel good about it, we commit to it, 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 00:27:16.000 --> 00:27:19.000 that term, or, 00:27:19.000 --> 00:27:21.000 you know, chosen that letter, whatever it is we're doing. 00:27:21.000 --> 00:27:24.000 If that recursive call returned true 00:27:24.000 --> 00:27:25.000 then we return true, 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 00:27:28.000 --> 00:27:29.000 loop early. 00:27:29.000 --> 00:27:32.000 We say that worked. That was good enough. 00:27:32.000 --> 00:27:35.000 If the solve came back with a negative result, 00:27:35.000 --> 00:27:36.000 that causes us to unmake that choice, 00:27:36.000 --> 00:27:39.000 and then we come back around here and we try another one. 00:27:39.000 --> 00:27:42.000 Again, we're optimistic. Okay, left didn't work, go straight. 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 00:27:46.000 --> 00:27:50.000 more choices, then we return false, and 00:27:50.000 --> 00:27:55.000 this false is the one that then causes some earlier decision to get unmade 00:27:55.000 --> 00:28:00.000 which allows us to revisit some earlier optimistic choice, undo it, and 00:28:00.000 --> 00:28:01.000 try again. 00:28:01.000 --> 00:28:04.000 The base case is hit when we run out of choices 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 00:28:08.000 --> 00:28:10.000 the goal, or we've 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 00:28:14.000 --> 00:28:17.000 -there's nothing more to decide. Is this where we wanted to be? 00:28:17.000 --> 00:28:18.000 Did it solve the problem? 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 00:28:23.000 --> 00:28:25.000 mean for it to be the goal state because for different problems it definitely means different 00:28:25.000 --> 00:28:29.000 things. But the code for them all looks the same 00:28:29.000 --> 00:28:30.000 kind of in 00:28:30.000 --> 00:28:33.000 its skeletal form. 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. 00:28:38.000 --> 00:28:40.000 So I've got recursive permute up 00:28:40.000 --> 00:28:44.000 here. So as it is, recursive permute tries every possible permutation, prints them all. 00:28:44.000 --> 00:28:47.000 What I'm interested in is is 00:28:47.000 --> 00:28:51.000 this sequence a letters an anagram. Meaning, it is -can be rearranged into 00:28:51.000 --> 00:28:54.000 something that's an English word. Okay. 00:28:54.000 --> 00:28:56.000 So what I'm gonna do is I'm gonna go in and edit it. The 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 00:28:59.000 --> 00:29:00.000 information. 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. 00:29:08.000 --> 00:29:10.000 I'm 00:29:10.000 --> 00:29:13.000 gonna 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 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 00:29:19.000 --> 00:29:22.000 assignment. 00:29:22.000 --> 00:29:24.000 And so 00:29:24.000 --> 00:29:26.000 when I get to the bottom 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 00:29:30.000 --> 00:29:31.000 far. 00:29:31.000 --> 00:29:35.000 And I'm going to check and see if it's in the dictionary. 00:29:35.000 --> 00:29:38.000 If the dictionary says that that's a word then 00:29:38.000 --> 00:29:41.000 I'm gonna say this was good. That permutation was good. 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 00:29:44.000 --> 00:29:46.000 say, well, this thing isn't a word. Why don't you try again? 00:29:46.000 --> 00:29:48.000 I'm gonna 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. 00:29:53.000 --> 00:29:58.000 And then when I make the call here [inaudible] 00:29:58.000 --> 00:30:00.000 third argument. 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 00:30:03.000 --> 00:30:06.000 work, so I'm gonna say, well, if 00:30:06.000 --> 00:30:08.000 it's an anagram 00:30:08.000 --> 00:30:11.000 then return true. 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, 00:30:16.000 --> 00:30:16.000 right? 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 00:30:20.000 --> 00:30:23.000 and then go for it. If you can make a word out of having made that 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 00:30:26.000 --> 00:30:29.000 we'll come back around and make some of the further calls in that loop 00:30:29.000 --> 00:30:32.000 to see if it worked out. 00:30:32.000 --> 00:30:34.000 At the bottom, I also need 00:30:34.000 --> 00:30:36.000 another failure case here, 00:30:36.000 --> 00:30:38.000 and that comes when 00:30:38.000 --> 00:30:43.000 the earlier choices, right -so I got, let's say somebody has given me X J, 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 00:30:46.000 --> 00:30:47.000 that 00:30:47.000 --> 00:30:50.000 you can -you know this ahead of time. It doesn't have the same vision 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 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 00:30:57.000 --> 00:31:01.000 after it says that, it says, you know what, okay, that just isn't working, right? 00:31:01.000 --> 00:31:02.000 It must be some 00:31:02.000 --> 00:31:05.000 earlier decision that was really at fault. 00:31:05.000 --> 00:31:08.000 This returned false is going to cause 00:31:08.000 --> 00:31:09.000 the, you 00:31:09.000 --> 00:31:13.000 know, sort of stacked up previous anagram calls to say, oh yeah, that 00:31:13.000 --> 00:31:16.000 choice of X for the first letter was really 00:31:16.000 --> 00:31:19.000 questionable. So imagine I've had, like, E X, you know, 00:31:19.000 --> 00:31:21.000 T I. I'm trying to 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 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 00:31:27.000 --> 00:31:30.000 E I T, X E T I, and so on. 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, 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. 00:31:37.000 --> 00:31:38.000 Eventually it'll try E in the front 00:31:38.000 --> 00:31:41.000 and then it won't have to try anything else after that because that will eventually 00:31:41.000 --> 00:31:44.000 work out. 00:31:44.000 --> 00:31:47.000 So if I put this guy in like that, 00:31:47.000 --> 00:31:49.000 and I 00:31:49.000 --> 00:31:59.000 build myself a lexicon, and then 00:31:59.000 --> 00:32:01.000 I change this to 00:32:01.000 --> 00:32:04.000 00:32:04.000 --> 00:32:09.000 anagram word. I 00:32:09.000 --> 00:32:13.000 can't spell. I'd better 00:32:13.000 --> 00:32:16.000 pass my lexicon because I'm gonna need that to 00:32:16.000 --> 00:32:18.000 do my word lookups. 00:32:18.000 --> 00:32:20.000 [Inaudible]. And down here. 00:32:20.000 --> 00:32:23.000 Whoops. 00:32:23.000 --> 00:32:28.000 Okay. I 00:32:28.000 --> 00:32:33.000 think 00:32:33.000 --> 00:32:36.000 that looks like it's okay. Well, no 00:32:36.000 --> 00:32:43.000 -finish this thing off here. 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 00:32:47.000 --> 00:32:47.000 with, 00:32:47.000 --> 00:32:49.000 like 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 00:32:52.000 --> 00:32:52.000 that. 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. 00:32:56.000 --> 00:32:59.000 What if I give it something like this, 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 00:33:02.000 --> 00:33:04.000 not telling us where the word is. I can actually go and change it. 00:33:04.000 --> 00:33:07.000 Maybe that'd be a nice thing to say. Why don't I print the word 00:33:07.000 --> 00:33:11.000 when it finds it? If 00:33:11.000 --> 00:33:14.000 lex dot contains 00:33:14.000 --> 00:33:16.000 -words so far 00:33:16.000 --> 00:33:20.000 -then print it. That 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 00:33:25.000 --> 00:33:27.000 type toab -now 00:33:27.000 --> 00:33:30.000 look at that, bota. Who would know? That dictionary's full of some really ridiculous 00:33:30.000 --> 00:33:33.000 words. 00:33:33.000 --> 00:33:37.000 Now I'll get back with exit. Let's type some other words. 00:33:37.000 --> 00:33:40.000 Query. So it's finding some 00:33:40.000 --> 00:33:44.000 words, and then if I give it some word that I know is just nonsense 00:33:44.000 --> 00:33:46.000 it won't print anything 00:33:46.000 --> 00:33:47.000 [inaudible] false. 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, 00:33:51.000 --> 00:33:53.000 of the permutation tree 00:33:53.000 --> 00:33:55.000 based on 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, 00:34:00.000 --> 00:34:03.000 even six nonsense characters, it really did do the full permutation, in this case, 00:34:03.000 --> 00:34:06.000 the six factorial permutations, and discover that none of them worked. 00:34:06.000 --> 00:34:08.000 But in the case of exit or the 00:34:08.000 --> 00:34:10.000 boat that, 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] 00:34:13.000 --> 00:34:16.000 in this case it will try all the permutations with Q in the front, 00:34:16.000 --> 00:34:17.000 right? 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 00:34:20.000 --> 00:34:23.000 start kind of rearranging and jumbling them up, and eventually, right, 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 00:34:26.000 --> 00:34:30.000 decision about Q. It will just sort of have -made that decision early, 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 00:34:34.000 --> 00:34:38.000 explored of R in front, and Y in the front, and E in the front 00:34:38.000 --> 00:34:40.000 because it had a notion of 00:34:40.000 --> 00:34:43.000 what is a satisfactory outcome. So the base case that it finally got to in 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 00:34:47.000 --> 00:34:49.000 had to work through the base cases 00:34:49.000 --> 00:34:50.000 until it found one, 00:34:50.000 --> 00:35:00.000 and potentially that could be very few of them relative the huge space. All right. 00:35:00.000 --> 00:35:02.000 I have this code 00:35:02.000 --> 00:35:05.000 actually on this slide. So it's 00:35:05.000 --> 00:35:08.000 permute, and that is turning into is anagram. And so, in blue, trying to highlight 00:35:08.000 --> 00:35:11.000 the things that changed in the process, right, that 00:35:11.000 --> 00:35:15.000 the structure of kind of how it's exploring, and making the recursive calls is exactly 00:35:15.000 --> 00:35:16.000 the same. 00:35:16.000 --> 00:35:19.000 But what we're using now is some return information from the function to 00:35:19.000 --> 00:35:22.000 tell us how the progress went, 00:35:22.000 --> 00:35:23.000 and then 00:35:23.000 --> 00:35:28.000 having our base case return some sense of did we get where we wanted to be, 00:35:28.000 --> 00:35:32.000 and then when we make the recursive call, if it did succeed, right, 00:35:32.000 --> 00:35:35.000 we immediately return true and unwind out of the recursion, 00:35:35.000 --> 00:35:37.000 doing no further exploration, 00:35:37.000 --> 00:35:40.000 and in the case where all of our choices 00:35:40.000 --> 00:35:41.000 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 00:35:45.000 --> 00:35:49.000 to where we were. 00:35:49.000 --> 00:35:51.000 So this is the transformation that 00:35:51.000 --> 00:35:54.000 you want to feel like you could actually sort of apply again and again, taking 00:35:54.000 --> 00:35:58.000 something that was exhaustive, and looked at a whole space, 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 00:36:01.000 --> 00:36:04.000 early when I get to something that's good enough. 00:36:04.000 --> 00:36:07.000 A lot of problems, right, that are recursive backtrackers just end up being 00:36:07.000 --> 00:36:08.000 procedural code 00:36:08.000 --> 00:36:11.000 that got turned into this 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 00:36:15.000 --> 00:36:18.000 exploration. 00:36:18.000 --> 00:36:22.000 Anybody have any questions of what we got there? Okay. 00:36:22.000 --> 00:36:24.000 I'm gonna show you some more 00:36:24.000 --> 00:36:26.000 just because they are 00:36:26.000 --> 00:36:29.000 -there are a million problems in this space, and the more of them you see, I 00:36:29.000 --> 00:36:32.000 think, the more the patterns will start to emerge. 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 00:36:35.000 --> 00:36:37.000 of decisions to make, 00:36:37.000 --> 00:36:39.000 and we're gonna try to 00:36:39.000 --> 00:36:42.000 make a decision in each recursive call 00:36:42.000 --> 00:36:45.000 knowing that that gives us fewer decisions that we have to make in the 00:36:45.000 --> 00:36:48.000 smaller form of the sub problem that we've built that way, 00:36:48.000 --> 00:36:51.000 and then the decisions that we have open 00:36:51.000 --> 00:36:53.000 to us, the options there 00:36:53.000 --> 00:36:56.000 represent the different recursive calls we can make. Maybe it's a for loop, or 00:36:56.000 --> 00:36:59.000 maybe a list of the explicit alternatives that we have 00:36:59.000 --> 00:37:03.000 that will be open to us in any particular call. 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 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 00:37:09.000 --> 00:37:12.000 you have an eight by eight chessboard, which is the standard chessboard size, 00:37:12.000 --> 00:37:14.000 and you had eight queen pieces, 00:37:14.000 --> 00:37:18.000 could you place those eight queens on the board 00:37:18.000 --> 00:37:21.000 in such a way that no queen is threatened by any other? The queen is 00:37:21.000 --> 00:37:23.000 the most powerful 00:37:23.000 --> 00:37:24.000 player on the board, right, can move 00:37:24.000 --> 00:37:27.000 any number of spaces horizontally, vertically, or diagonally on any 00:37:27.000 --> 00:37:29.000 straight line basically, 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 00:37:32.000 --> 00:37:35.000 board to get them all in there in such a way that they can't 00:37:35.000 --> 00:37:37.000 go after each other. 00:37:37.000 --> 00:37:41.000 And so if we think of this as a decision problem, 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 00:37:44.000 --> 00:37:45.000 make are 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. 00:37:50.000 --> 00:37:54.000 So at each call we could place one queen, leaving us with M minus 1 to 00:37:54.000 --> 00:37:55.000 go. 00:37:55.000 --> 00:37:59.000 The choices for that queen might be that one way to kind of 00:37:59.000 --> 00:38:02.000 keep our problem 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 00:38:04.000 --> 00:38:07.000 queen in each column, 00:38:07.000 --> 00:38:08.000 right, 00:38:08.000 --> 00:38:10.000 it certainly can't be that there's two in one column. So 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 00:38:13.000 --> 00:38:16.000 a queen in the leftmost column. 00:38:16.000 --> 00:38:18.000 The next call will make a queen 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 00:38:21.000 --> 00:38:23.000 across the board from left to right, 00:38:23.000 --> 00:38:25.000 and then the choices for that queen 00:38:25.000 --> 00:38:27.000 will be any of the [inaudible] 00:38:27.000 --> 00:38:32.000 and some of those actually are -we may be able to easily eliminate as 00:38:32.000 --> 00:38:35.000 possibilities. So, for example, once this queen is down here in the bottommost row, and 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 00:38:40.000 --> 00:38:43.000 right next to it because we can see that that immediately threatens. 00:38:43.000 --> 00:38:46.000 So what we'll try is, is there a spot in this column that 00:38:46.000 --> 00:38:48.000 works given the previous decisions I've made, 00:38:48.000 --> 00:38:51.000 and if so, make that decision and move on. 00:38:51.000 --> 00:38:54.000 And only if we learned that that decision, right, 00:38:54.000 --> 00:39:00.000 that we just made optimistically isn't successful will we back up and try again. 00:39:00.000 --> 00:39:10.000 So let me do a little demo with you. 00:39:10.000 --> 00:39:12.000 Kind of shows this 00:39:12.000 --> 00:39:14.000 doing its job. 00:39:14.000 --> 00:39:17.000 Okay. 00:39:17.000 --> 00:39:20.000 So [inaudible] I'm gonna do it as I said, kind of column by column. 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 00:39:24.000 --> 00:39:27.000 mark here says this is a spot under consideration. I look at the 00:39:27.000 --> 00:39:29.000 configuration I'm in, 00:39:29.000 --> 00:39:32.000 and I say, is this a plausible place to put the queen? 00:39:32.000 --> 00:39:34.000 And there's no reason not to, 00:39:34.000 --> 00:39:38.000 so I go ahead and let the queen sit there. 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 00:39:42.000 --> 00:39:43.000 more queens to go. 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 00:39:47.000 --> 00:39:50.000 the next recursive call comes in and says, if you can place the queens given the 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. 00:39:54.000 --> 00:39:58.000 So it looks at the bottommost row, and it says, oh, no, that won't work, 00:39:58.000 --> 00:40:00.000 right? There's a queen right there. 00:40:00.000 --> 00:40:03.000 It looks at the next one and then sees the diagonal attack. Okay. Moves up to 00:40:03.000 --> 00:40:05.000 here and says, okay, that's good. 00:40:05.000 --> 00:40:06.000 That'll work, 00:40:06.000 --> 00:40:08.000 right? Looks at all of them and it's okay. 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 00:40:12.000 --> 00:40:16.000 feeling good about it. Go ahead and make the recursive call. 00:40:16.000 --> 00:40:19.000 The third call comes in, looks at that row, not good, 00:40:19.000 --> 00:40:21.000 looks at that row, not good, 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 00:40:25.000 --> 00:40:28.000 options at all that were viable. 00:40:28.000 --> 00:40:30.000 We got here, 00:40:30.000 --> 00:40:35.000 and given the earlier decisions, and so the idea is that, given our optimism, right, we 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 00:40:39.000 --> 00:40:42.000 have tried all the possibilities in this third recursive call and there was 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 00:40:46.000 --> 00:40:47.000 backtracking that says, 00:40:47.000 --> 00:40:50.000 you know what, there was some earlier problem. 00:40:50.000 --> 00:40:50.000 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 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 00:40:56.000 --> 00:40:58.000 given the state that was passed to this call, 00:40:58.000 --> 00:41:01.000 there's no way to solve it from here. 00:41:01.000 --> 00:41:03.000 And so this is gonna trigger the backtracking. So 00:41:03.000 --> 00:41:06.000 that backtracking is coming back to an earlier decision that you made and unmaking 00:41:06.000 --> 00:41:07.000 it. 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 00:41:12.000 --> 00:41:13.000 try again. 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. 00:41:17.000 --> 00:41:21.000 Okay, let's try moving it up a notch and see how that goes. 00:41:21.000 --> 00:41:22.000 Then, again, 00:41:22.000 --> 00:41:25.000 optimistic, makes the call and goes for it. 00:41:25.000 --> 00:41:28.000 Can't do this one. That looks good. 00:41:28.000 --> 00:41:31.000 And now we're on our way to placing the last queen, feeling really comfortable and 00:41:31.000 --> 00:41:33.000 confidant, 00:41:33.000 --> 00:41:34.000 but 00:41:34.000 --> 00:41:35.000 discovering quickly, 00:41:35.000 --> 00:41:39.000 right, that there was no possible. So it turns out this configuration with these three 00:41:39.000 --> 00:41:42.000 queens, not solvable. Something must be wrong. 00:41:42.000 --> 00:41:46.000 Back up to the most immediate decision. She knows it doesn't unmake, you know, 00:41:46.000 --> 00:41:50.000 earlier decisions until it really has been proven that that can't work, so 00:41:50.000 --> 00:41:52.000 at this point it says, okay, well let's try finding 00:41:52.000 --> 00:41:53.000 something else in this 00:41:53.000 --> 00:41:54.000 column. 00:41:54.000 --> 00:41:55.000 No go. 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 00:41:58.000 --> 00:42:01.000 the second column. Well, it turns out the second column -that was the last choice 00:42:01.000 --> 00:42:05.000 it had. So in fact it really was my first decision 00:42:05.000 --> 00:42:08.000 that got us off to the wrong foot. 00:42:08.000 --> 00:42:11.000 And now, having tried everything that there was possible, given the queen in the 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 00:42:14.000 --> 00:42:18.000 try again, and at this point it actually will go fairly quickly. 00:42:18.000 --> 00:42:21.000 Making that initial first decision 00:42:21.000 --> 00:42:22.000 was 00:42:22.000 --> 00:42:24.000 the magic that 00:42:24.000 --> 00:42:26.000 got it solved. And 00:42:26.000 --> 00:42:30.000 then we have a complete solution to the queens. 00:42:30.000 --> 00:42:32.000 We put it onto eight, 00:42:32.000 --> 00:42:34.000 and let it go. 00:42:34.000 --> 00:42:38.000 You can see it kind of checking the board, backing up, and you notice that it 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 00:42:42.000 --> 00:42:46.000 that it always backs up to the most recent decision point 00:42:46.000 --> 00:42:47.000 when it fails, 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 00:42:50.000 --> 00:42:54.000 back up and consider a previous decision as being unworthy 00:42:54.000 --> 00:43:01.000 and revisiting it. 00:43:01.000 --> 00:43:04.000 In this case that first decision did work out, 00:43:04.000 --> 00:43:06.000 the queen being in the lower left. 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 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 00:43:12.000 --> 00:43:15.000 that for a while. Tried the fourth row for a while. 00:43:15.000 --> 00:43:18.000 All the possibilities after that, but eventually it was that fifth row 00:43:18.000 --> 00:43:22.000 that then kind of gave it the breathing room to get those other queens out there. 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 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 00:43:30.000 --> 00:43:32.000 search tree than 00:43:32.000 --> 00:43:34.000 an exhaustive recursion 00:43:34.000 --> 00:43:39.000 of the whole thing would have done. 00:43:39.000 --> 00:43:46.000 The code for that ?whoops 00:43:46.000 --> 00:43:48.000 -looks something like this. 00:43:48.000 --> 00:43:49.000 And 00:43:49.000 --> 00:43:51.000 one of the things that I'll strongly encourage you to do when you're writing 00:43:51.000 --> 00:43:54.000 a recursive backtracking routine, 00:43:54.000 --> 00:43:58.000 something I learned from Stuart Regis, who long ago was my mentor, 00:43:58.000 --> 00:43:59.000 was the idea that 00:43:59.000 --> 00:44:03.000 when -trying to make this code look as simple as possible, that one of the things 00:44:03.000 --> 00:44:06.000 you want to do is try to move away the details of the problem. For example, 00:44:06.000 --> 00:44:08.000 like, is safe 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, 00:44:12.000 --> 00:44:15.000 trying to decide that there's not some existing conflict on the board with the 00:44:15.000 --> 00:44:19.000 queen already being threatened by an existing queen just involves us 00:44:19.000 --> 00:44:22.000 kind of traipsing across the grid and looking at different things. 00:44:22.000 --> 00:44:26.000 But putting in its own helper function makes this code much easier to read, right? 00:44:26.000 --> 00:44:28.000 Similarly, placing the queen in the board, removing the queen from the board, 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 00:44:32.000 --> 00:44:34.000 graphical display. 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 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 00:44:41.000 --> 00:44:44.000 the column we're trying to place a queen in, we've got this grid 00:44:44.000 --> 00:44:46.000 of boolean that shows where the queens are so far, 00:44:46.000 --> 00:44:50.000 that for all of the rows across the board, if, 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 00:44:54.000 --> 00:44:56.000 queen and see if you can solve 00:44:56.000 --> 00:44:59.000 starting from the column to the right, given this new update to the board. If it 00:44:59.000 --> 00:45:03.000 worked out, great, nothing more we need to do. Otherwise we need to take back that 00:45:03.000 --> 00:45:05.000 queen, unmake that decision, 00:45:05.000 --> 00:45:06.000 and try again. 00:45:06.000 --> 00:45:09.000 Try a higher row. Try a higher row, right. 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 00:45:13.000 --> 00:45:16.000 it again. If we tried all the rows that were open to us, 00:45:16.000 --> 00:45:21.000 and we never got to this case where this returned true, then we return false, which 00:45:21.000 --> 00:45:22.000 causes some 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 00:45:26.000 --> 00:45:27.000 put a queen in column two, 00:45:27.000 --> 00:45:31.000 and we end up returning false, it's gonna cause column one to unmake a decision 00:45:31.000 --> 00:45:33.000 and move the queen up a little bit higher. 00:45:33.000 --> 00:45:38.000 If all of the options for column one fail, it'll back up to column zero. 00:45:38.000 --> 00:45:41.000 The base case here at the end, is if we ever get to where 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 00:45:45.000 --> 00:45:47.000 all the way across the board and 00:45:47.000 --> 00:45:50.000 we're in success land. So all 00:45:50.000 --> 00:45:54.000 this code kind of looks the same kind of standing back from it, right, it's 00:45:54.000 --> 00:45:54.000 like, 00:45:54.000 --> 00:45:57.000 for each choice, if you can make that choice, make it. 00:45:57.000 --> 00:46:02.000 If you solved it from here, great, otherwise, unmake that choice. 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 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 00:46:09.000 --> 00:46:10.000 queens, 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 00:46:14.000 --> 00:46:17.000 some sort of true or false analysis that comes out there about 00:46:17.000 --> 00:46:21.000 being in the right state. How do you feel 00:46:21.000 --> 00:46:24.000 about that? You guys look 00:46:24.000 --> 00:46:24.000 tired today, and 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, 00:46:28.000 --> 00:46:30.000 right? 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 00:46:33.000 --> 00:46:36.000 them on Monday because I really don't want to -I 00:46:36.000 --> 00:46:37.000 want 00:46:37.000 --> 00:46:38.000 to 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 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 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.