Instructor (Julie Zelenski):Hey there. Welcome. Welcome. Welcome. My computerís not quite talking to anything yet here. You guys got an answer for that? Unplug and replug that? Okay, I donít know whatís Ė whether somebody can help make my computer talk to the projector? Yeah. Itís plugged in like ordinary. Yeah, I Ė we do this every day. There we go. Thank you very much. All right, back to your regularly scheduled lecture.
Today Iím gonna keep talking a little bit more about another procedural recursion example and then go on to talk about, kind of, the approach for recursive backtracking, which is taking those procedural recursion examples and kind of twisting them around and doing new things with them. This corresponds with to the work thatís in chapter six of the reader.
And then from here weíre actually gonna do a little detour to pick up an explanation of recursive data in the form of linked lists, and thatís gonna give us a chance to start talking about C++ pointers, which I know everyone has been eagerly awaiting a chance to get a little bit of mystery of the pointers revealed to them. And so the coverage for that is in chapter 2 in the early sections, 2-2 and 2-3. I [inaudible] covered in the text in sort of 9-5. Thereís actually a handout Iíll give out on Mondayís lecture that helps to go along with what weíre doing there so thereís a little bit of supplemental material to kind of work through that. And so itíll be our first chance to see points [inaudible] we can really use them to do something, and so I kind of differed talking about them until now because we donít have a good use until we get there, and that weíll be exploring a recursive data type called the link list. Iíll be hanging out at the Turbine Cafť after class, so if, actually, youíre available this afternoon and want to come and hang out, weíll be there for an hour or two, so if you want to walk over with us or come later when youíre free, that would be great. If not this Friday, hopefully some other one. How many people started the recursion problem set? Got right on it. How many people have already solved a problem or two? Oh, yeah. How many people solved all of them? Okay. Thatís good though. And how is it going so far? Thumbs up? Lots of joy? Joy in Mudville. All right. So as I say, the handout, you know, thereís six problems, each of them is actually very, very short, and that may lull you into believing that, well, you can start at it right before because itís not gonna be typing speed thatís gonna keep you there all night, but it is actually some really dense, complex code to kind of get your head around and think about. And I think, actually, it helps a lot to have started at it, and thought about it, and let it gel for a little time before you have to kind of really work it all the way out. So I do encourage you to get a jump on that as soon as youíve got some time. Okay. This is the last problem I did at the end of Wednesdayís lecture. Itís a very, very important problem, so I donít actually want to move away from it until I feel that Iím getting some signs from you guys that weíre getting some understanding of this because it turns out it forms the basis of a lot of other solutions end up just becoming permutations, you know, at the core of it. So itís a pretty useful pattern to have [inaudible] list the permutations of a string. So youíve got the string, you know, A B C D, and itís gonna print all the A C D A B C D A variations that you can get by rearranging all the letters. Itís a deceptively short piece of code that does whatís being done here Ė is that it breaks it down in terms of there being the permutation thatís assembled so far, and then the remaining characters that havenít yet been looked at, and so at each recursive call itís gonna shuffle one character from the remainder onto the thing thatís been chosen so far. So chose the next character in the permutation, and eventually, when the rest is empty, then all of the characters have been moved over, and have been laid down in permutation, then what I have is a full permutation of the length end. In the case where rest is not empty, Iíve still got some choices to make. The number of choices is exactly equal to the number of characters I have left in rest, and for each of the remaining characters at this point, maybe thereís just C and D left, then Iím gonna try each of them as the next character in the permutation, and then permute what remains after having made that choice. And so this is [inaudible] operations here of attaching that [inaudible] into the existing so far, and then subtracting it out of the rest to set up the arguments for that recursive call. A little bit at the end we talked about this idea of a wrapper function where the interface to list permutations from a client point of view probably just wants to be, hereís a string to permute the fact that [inaudible] keep this housekeeping of what Iíve built so far is really any internal management issue, and isnít what I want to expose as part of the interface, so we in turn have just a really simple one line translation that the outer call just sets up and makes the call to the real recursive function setting up the right state for the housekeeping in this case, which is the permutation weíve assembled at this point. So Iíd like to ask you a few questions about this to see if weíre kind of seeing the same things. Can someone tell me what is the first permutation thatís printed by this if I put in the string A B C D? Anyone want to help me?
A B C D.
Instructor (Julie Zelenski):A B C D. So the exact string I gave it, right, is the one that it picks, right, the very first time, and thatís because, if you look at the way the for loop is structured, the idea is that itís gonna make a choice and itís gonna move through the recursion. Well, the choice it always makes is to take the next character of rest and attach it to the permutation as its first time through the for loop. So the first time through the very first for loop itís got A B C D to chose, it chooses A, and now it recurs on A in the permutation and B C D to go.
Well, the next call does exactly the same thing, chooses the first of what remains, which is B, attaches it to the permutation and keeps going. So the kind of deep arm of the recursion making that first choice and working its way down to the base case, right, right remember the recursion always goes deep. It goes down to the end of the Ė and bottoms on the recursion before it comes back and revisits any previous decision, will go A B C D, and then eventually come back and start trying other things, but that very first one, right, is all just the sequence there.
The next one thatís after it, right, is A B D C, which involved unmaking those last couple decisions. If I look at the tree that I have here that may help to sort of identify it. That permute of emptying A B C, the first choice it makes is go with A, and then the first choice it makes here is go with B, and so on, so that the first thing that we can see printed our here will be A B C D, we get to the base case.
Once itís tried this, itíll come back to this one, and on this one itíll say, well, try the other characters. Well, thereís no other characters. In fact, this one also finishes. Itíll get back to here as it unwinds the stack the way the stack gets back to where it was previously in these recursive calls. And now it says, okay, and now try the ones that have, on the second iteration of that for loop, D in the front, and so it ends up putting A B D together, leaving C, and then getting A B D C.
And then, so on kind of over here, the other variations, it will print all of the ones that have A in the front. There are eight of them. I believe three, two Ė no, six. Six of them that have A in the front, and weíll do all of those. And only after having done all of working out that whole part, which involves kind of the [inaudible] of this whole arm, will eventually unwind back to the initial permute call, and then say, okay, now try again. Go with B in the front and work your way down from reading the A C D behind it. So weíll see all the As then the bunch that lead with B, then the bunch that leads with C, and then finally the bunch that leads with D.
It doesnít turn out Ė matter, actually, what order it visits them in because, in fact, all we cared about was seeing all of them. But part of what Iím trying to get with you is the sense of being able to look at that recursive code, and use your mind to kind of trace its activity and think about the progress that is made through those recursive calls. Just let me look at that code just for a second more and see if thereís any else that I want to highlight for you.
I think thatís about what itís gonna do. So if you donít understand this cost, if thereís something about it that confuses you, now would be an excellent time for you to ask a question that I could help kind of get your understanding made more clear. So when you look at this code, you feel like you believe it works? You understand it?
Student:[Inaudible]. I have a question. Is there a simple change you can make to this code so that it does combinations [inaudible]?
Instructor (Julie Zelenski):Does combinations Ė you mean, like, will skip letters?
Instructor (Julie Zelenski):Yes. It turns out weíre gonna make that change in not five minutes. In effect, what you would do Ė and thereís a pretty simple change with this form. Iím gonna show you a slightly different way of doing it, but one way of doing it would be to say, well, give me the letter, donít attach it to next right? So right now, the choices are pick one of the letters that remain and then attach it to the permutation. Another option you could do was pick a letter and just discard it, right? And so, in which case, I wouldnít add it into so far. I would still subtract it from here, and Iíd make another recursive call saying, now how about the permutations that donít involve A at all? And I would just drop it from the thing and I would recurs on just the B C D part. So a pretty simple change right here. Iím gonna show you thereís a slightly different way to formulate the same thing in a little bit, but Ė anybody want to own up to having something that confuses them?
[Inaudible] ask how you, like, what you would set up to test it?
Instructor (Julie Zelenski):So [inaudible] one of the, you know, the easiest thing to do here, and I have the code kind of actually sitting over here just in case, right, hoping you would ask because right now I just have the most barebones sort of testing. Itís like, yeah, what if I just, you know, throw some strings at it and see what happens, right? And so the easiest strings to throw at it would be things like, well what happens if I give it the empty string, right? You know, so it takes some really simple cases to start because you want to see, well what happens when, you know, you give it an empty input. Is it gonna blow up?
And itís, like, the empty input, right, immediately realizes thereís no choices and it says, well, look, thereís nothing to print other than that empty string. What if I give it a single character string? Right? I get that string back. Iím like, okay, gives me a little bit of inspiration that it made one recursive call, right, and then hit the base case on the subsequent one. Now I start doing better ones.
A and B, 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 the front, and I put the B A behind, then hopefully what I believe is that itís gonna try, you know, C in the front, and then itís gonna permute A and B behind it, and then similarly on down. So some simple cases that I can see verifying that it does produce, kind of, the input string as itself, and then it does the back end rearrangement, leaving this in the front, and then it makes the next choice for what can go in the front, and then the back end rearrangement. And kind of seeing the pattern that matches my belief about how the code works, right, helps me to feel good. What happens if I put in something that has double letters in it? So I put A P P L E in there. And all the way back at the beginning, right, I can plot more of them, right, that grows quite quickly right as we add more and more letters, right? Seeing the apple, appel, and stuff like that. Thereís a point where it starts picking the P to go in the front, and the code as itís written, right, doesnít actually make it a combination for this P and this P really being different. So it goes through a whole sequence of pull the second character to the front, and then permute the remaining four. And then it says, and now pull the third character to the front and permute the remaining four, which turns out to be exactly the same thing. So there should be this whole sequence in the middle, right, of the same Ps repeated twice because we havenít gone over a way to do anything about that, right? So Ė but it is reassuring to know that it did somehow didnít get, you know, confused by the idea of there being two double letters. [Inaudible] if I do this Ė if I just say A B A, right? Something a little bit smaller to look at, right? A in the front. A in the front goes permuted, B in the front, and then it ends up permuting these two ways that ends up being exactly the same, and then I get a duplicate of those in the front. So right now, it doesnít know that thereís anything to worry about in terms of duplicates? Whatís a really easy way to get rid of duplicates? Donít think recursively, think Ė use a set. Right? I could just stuff them in a set, right? And then if it comes across the same one again itís like, yeah, whatever. So it would still do the extra work of finding those down, but would actually, like, I could print the set at the end having coalesced any of the duplicates. To actually change it in the code, itís actually not that hard either. The idea here is that for all of the characters that remain, right, and sometimes what I want to choose from is of the remaining characters uniqued, right? Pick one to move to the front. So if thereís three more Ps that remain in rest, I donít need to try each of those Ps individually in the front, right? Theyíll produce the same result Ė pulling one and leaving the other two behind is completely irrelevant. So an easy way to actually stop it from even generating them, is when looking at the character here is to make sure that it is Ė that it doesnít duplicate anything else in the rest. And so probably the easiest way to do that is to either pick the first of the Ps or the last of the Ps, right, and to recur on and ignore the other ones. So, for example, if right here I did a find on the rest after I Ė do you see any more of these? And if you do, then skip it and just let those go. Or, you know, do the first. Donít do the remaining ones. You can either look to the left of look to the right and see if you see any more, and if so, skip the, you know, early or later ones depending on what your strategy is. Any questions about permute here?
Instructor (Julie Zelenski):So the [inaudible] can be just Ė look down here, right, it just looks like that, right? This is a very common thing. Youíll see this again, and again, and it tends to be that the outer call, right, it tends to have this sort of this, you know, solve this problem, and then it turns out during the recursive calls you need to maintain some state about where you are in the problem. You know, like, how many letters you moved, or what permutation youíve built so far, or where you are in the maze, or whatever it is youíre trying to solve.
And so typically that wrapper call is just gonna be setting up the initial call in a way that has the initial form of that state present that the client to the function didnít need to know about. Itís just our own housekeeping that weíre setting up. Seems almost kind of silly to write down the function that has just line that just turns it into, basically, itís just exchanging Ė setting up the other parameters.
I am going to show you the other kind of master patter, and then weíre gonna go on to kind of use them to solve other problems. This is the one that was already alluded to, this idea of a combinations. Instead of actually producing all of the four character strings that involve rearrangements of A B C D, what if I were to [inaudible] in kind of the subgroups, or the way I could chose certain characters out of that initial input, and potentially exclude some, potentially include some?
So if I have A B C, then the subsets of the subgroups of that would be the single characters A B and C. The empty string A B and C itself the full one, and then the combinations of two, A B, A C, and B C. Now, in this case weíre gonna say that order doesnít matter. Weíre not Ė whereas permutations was all about order, Iím gonna use Ė Iím gonna structure this one where I donít care. If itís A B or B A Iím gonna consider it the same subset. So Iím just interested in inclusion. Is A in or out? Is B in or out? Is C in or out?
And so the recursive strategy weíre gonna take is exactly what I have just kind of alluded to in my English description there, is that Iíve got an input, A B C. Each of those elements has either the opportunity of being in the subset or not. And I need to make that decision for everyone Ė every single element, and then I need to kind of explore all the possible combinations of that, right? When A is in, what if B is out? When A is in, what if B is in? So the recursion that Iím gonna use here is that at each step of the way, Iím gonna separate one element from the input, and probably the easiest way to do that is just to kind of take the front most element off the input and sort of separate it into this character by itself and then the remainder.
Similarly, the way I did with permute, and then given that element I have earmarked here, I can try putting it in the current subset or not. I need to try both, so Iím gonna make two recursive calls here, one recursive call where Iíve added it in, one recursive call where I havenít added it in. In both cases, right, I will have removed it from the rest, so whatís being chosen from to complete that subset always is a little bit smaller, a little bit easier. So this is very, very much like the problem I described as the chose problem. Trying to choose four people from a dorm to go to flicks was picking Bob and then Ė [inaudible] to Bob and not Bob, and then saying, well, Bob could go, in which I need to pick three people to go with him, or Bob could not go and I need to pick four people to go without Bob.
This is very much that same pattern. Two recursive calls. Identify one in or out. The base case becomes when thereís nothing left to check out. So I start with the input A B C Ė A B C D letís say. I look at that first element Ė I just need to pick one. Might as well pick the front one, itís the easy one to get to. I add it to the subset, remove it from the input, and make a recursive call. When that recursion completely terminates, I get back to this call, and I do the same thing again.
Remaining input is B C D again but now the subset that Iíve been building doesnít include. So inclusion exclusion are the two things that Iím trying. So the subset problem, right, very similar in structure to the way that I set up permutations, right, as Iím gonna keep track of two strings as Iím working my way down the remainder in the rest, right, things that I havenít yet explored so far is what characters Iíve chosen to place into the subset that Iím building. If I get to the end where thereís nothing left in the rest, so thereís no more choices to make, then what I have in the subset is what I have in the subset, and I go ahead and print it.
In the case that thereís still something to look at I make these two calls, one where Iíve appended it in, where I havenít, and then both cases, right, where I have subtracted it off of the rest by using the subster to truncate that front character off. So the way that permute was making calls, right, was in a loop, and so sometimes itís a little bit misleading. You look at it and you think thereís only one recursive call, but in fact itís in inside a loop, and so itís making, potentially, end recursive calls where end is the length of the input. It gets a little bit shorter each time through but thereís always, you know, however many characters are in rest is how many recursive calls it makes. The subsets code actually makes exactly two recursive calls at any given stage, in or out, and then recurs on that and what is one remaining. It also needs a wrapper for the same exact reason that permutations did. Itís just that we are trying to list the subsets of a particular string, in fact, thereís some housekeeping thatís going along with it. Weíre just trying the subset so far is something we donít necessarily want to put into the public interface in the way that somebody would have to know what to pass to that to get the right thing. Anybody have a question about this? So given the way this code is written, what is the first subset that is printed if I give it the input A B C D? A B C D. Just like it was with permute, right? Everything went in. What is the second one printed after that? A B C, right? So Iím gonna look at my little diagram with you to help kind of trace this process of the recursive call, right, is that the leftmost arm is the inclusion arm, the right arm is the exclusion arm. At every level of the tree, right, weíre looking at the next character of the rest and deciding whether to go in or out, the first call it makes is always in, so at the beginning it says, Iím choosing about A. Is A in? Sure. And then it gets back to the level of recursion. It says, okay, look at the first thing of rest, thatís B. Is B in? Sure. Goes down the right arm, right? Is C in? Sure. Is D in? Sure. It gets to here and now we have nothing left, so we have [inaudible] A B C D. With the rest being empty, we go ahead and print it [inaudible] thereís no more choices to make. Weíve looked at every letter and decided whether it was in or out. It will come back to here, and Iíll say, okay, Iíve finished all the things I can make with D in, how about we try it with D out. And so then D out gives us just the A B C. After itís done everything it can do with A B C in, it comes back to here and says, okay, well now do this arm, and this will drop C off, and then try D in, D out. And so it will go from the biggest sets to the smaller sets, not quite monotonically though. The very last set printed will be the empty set, and that will be the one where it was excluded all the way down, which after it kind of tried all these combinations of in out, in out, in out, it eventually got to the out, out, out, out, out, out, out case which will give me the empty set on that arm. Again, if I reverse the calls, right, Iíd still see all the same subsets in the end. They just come out in a different order. But it is worthwhile to model the recursion in your own head to have this idea of understanding about how it goes deep, right? That it always makes that recursive call and has to work its way all the way to the base case and terminate that recursion before it will unfold and revisit the second call that was made, and then fully explore where it goes before it completes that whole sequence. Anybody want to ask me a question about these guys? These are just really, really important pieces of code, and so Iím trying to make sure that I donít move past something that still feels a little bit mystical or confusing to you because everything I want to do for the rest of today builds on this. So now if thereís something about either of these pieces of code that would help you Ė yeah.
What would be the simplest way to do that?
Instructor (Julie Zelenski):So probably the simplest way, like, if you said, oh, I just really want it to be in alphabetical order, would be to put them in a set, right, and then have the set be the order for you.
Student:So you said order doesnít matter?
Instructor (Julie Zelenski):Oh, you did care about how they got ordered.
Student:So, like, letís say you didnít want B C D to equal C D B.
Instructor (Julie Zelenski):So in that case, right, you would be more likely to kind of add a permutation step into it, right? So if B C D was not the same thing as A B C, right, it would be, like, well Iím gonna chose Ė so in this case, right, it always Ė well the subsets will always be printed as kind of a subsequence. So Ė and letís say if the input was the alphabet, just easy way to describe it, all of the subsets Iím choosing will always be in alphabetical order because Iím always choosing A in or not, B in or not.
If I really wanted B Z to be distinct from Z B, then really what I want to be doing at each step is picking the next character to go, and not always assuming the next one had to be the next one in sequence, so I would do more like a permute kind of loop thatís like pick the next one that goes, remove it from what remains and recur, and that I need that separate step we talked about of Ė and in addition to kind of picking, we also have to leave open the opportunity that we didnít pick anything and we just kind of left the subject as is, right, so we could [inaudible] or not.
And so permute always assumes we have to have picked everything. The subset code would also allow for some of them just being entirely skipped. So we pick the next one, right, and then eventually stopped picking.
Student:[Inaudible] just in your wrapper function then [inaudible] put a for loop or something like that, right? When youíre through changing your string?
Instructor (Julie Zelenski):Yeah, you can certainly do that, like in a permute from the outside too, right. So thereís often very, you know, multiple different ways you can get it the same thing whether you want to put it in the recursion or outside the recursion, have the set help you do it or not, that can get you the same result.
So let me try to identify whatís the same about these to try to kind of back away from it and kind of move just to see how these are more similar than they are different, right, even though the code ends up kind of being Ė having some details in it that Ė if you kind of look at it from far away these are both problems that are about choice. That the recursive calls that we see have kind of a branching structure and a depth factor that actually relates to the problem if you think about it in terms of decisions, that in making a permutation your decision is what character goes next, right? In the subset itís like, well, whether this character goes in or not that the recursive tree that I was drawing that it shows all those calls, the depths of it represents the number of choices you make.
Each recursive call makes a choice, right? A yes, no, or a next letter to go, and then recurs from there. So I make, you know, one of those calls, and then thereís N minus 1 beneath it that represent the further decisions I make that builds on that. And so, in the case of permutation, once Iíve picked the, you know, N minus 1 things to go, thereís only one thing left, right? And so in some sense the tree is N because I have to pick N things that go in the permutation and then Iím done.
In the subsets, itís also N, and thatís because for each of the characters Iím deciding whether itís in or out. So I looked at A and decided in or out. I looked at B and decided in or out. And I did that all the way down. That was the life of the input. The branching represents how many recursive calls were made at each level of the recursion. In the case of subsets, itís always exactly two. In, out, all the way down, restarts at 1, branches to 2, goes to 4, goes to 8, 16, and so on.
In the permute case, right, there are N calls at the beginning. I have N different letters to choose from, so itís a very wide spread there, and that at that next level, itís N minus 1. Still very wide. And N minus 2. And so the overall tree has kind of an N times N minus 1 times N minus 2 all the way down to the bottom, which the factorial function Ė which grows very, very quickly.
Even for small inputs, right, the number of permutations is enormous. The number of subsets is to the end in or out, right, all the way across. Also, a very, you know, resource intensive problem to solve, not nearly as bad as permutation, but both of them, even for small sizes of N, start to become pretty quickly intractable. This is not the fault of recursion, right, these problems are not hard to solve because weíre solving them in the wrong way.
Itís because there are N factorial permutations. There are [inaudible] different subsets, right? Anything thatís going to print to the N things, or N factorial things is going to do N factorial work to do so. You canít avoid it. Thereís a big amount of work to be done in there. But what weíre trying to look at here is this idea that those trees, right, represent decisions. Thereís some decisions that are made, you know, a decision is made at each level of recursion, which then is kind of a little bit closer to having no more decisions to make. You have so many decisions to make, which is the depth of the recursion. Once youíve made all those decisions, you hit your base case and youíre done.
The tree being very wide and very deep makes for expensive exploration. What weíre gonna look at is a way that we can take the same structure of the problem, one that fundamentally could be exhaustive, exhaustive meaning tried every possible combination, every possible rearrangement and option, and only explore some part of the tree. So only look around in some region, and as soon as we find something thatís good enough.
So in the case, for example, of a search problem, it might be that weíre searching this space that could potentially cause us to look at every option, but weíre also willing to say if we make some decisions that turn out good enough, that get us to our goal, or whatever it is weíre looking for, we wonít have to keep working any farther. So Iím gonna show you how we can take an exhaustive recursion problem and turn it into whatís called a recursive backtracker.
So thereís a lot of text on this slide but let me just tell you in English what weíre trying to get at. That the idea behind permutations or subsets is that at every level thereís all these choices and weíre gonna try every single one of them. Now imagine we were gonna make a little bit less a guarantee about that. Letís design the function to return some sort of state thatís like I succeeded or I failed. Did I find what I was looking for? At each call, I still have the possibility of multiple calls of in out, or a choice from whatís there. Iím gonna go ahead and make the choice, make the recursive call, and then catch the result from that recursive call, and see whether it succeeded.
Was that a good choice? Did that choice get me to where I wanted to be? If it did, then Iím done. I wonít try anything else. So Iíll stop early, quite going around the for loop, quit making other recursive calls, and just immediately [inaudible] say Iím done. If it didnít Ė it came back with a failure, some sort of code that said it didnít get where I want to do, then Iíll try a different choice. And, again, Iíll be optimistic. Itís a very optimistic way of doing stuff. It says make a choice, assume itís a good one, and go with it. Only when you learn it didnít work out do you revisit that decision and back up and try again. So let me show you the code. I think itís gonna make more sense, actually, if I do it in terms of looking at what the code looks like. This is the pseudo code at which all recursive backtrackers at their heart come down to this pattern.
So what I Ė I tried to be abstract [inaudible] so what does it mean to solve a problem, and whatís the configuration? That depends on the domain and the problem weíre trying to solve. But the structure of them all looks the same in that sense that if there are choices to be made Ė so the idea is that we cast the problem as a decision problem. There are a bunch of choices to be made. Each [inaudible] will make one choice and then attempt to recursively solve it.
So thereís some available choices, in or out, or one of next, or where to place a tile on a board, or whether to take a left or right turn and go straight in a maze. Any of these things could be the choices here. We make a choice, we feel good about it, we commit to it, and we say, well, if we can solve from here Ė so we kind of update our statement so weíve made that term, or, you know, chosen that letter, whatever it is weíre doing.
If that recursive call returned true then we return true, so we donít do any unwinding. We donít try all the other choices. We stop that for loop early. We say that worked. That was good enough. If the solve came back with a negative result, that causes us to unmake that choice, and then we come back around here and we try another one. Again, weíre optimistic. Okay, left didnít work, go straight. If straight doesnít work, okay, go right. If right didnít work and we donít have any more choices, then we return false, and this false is the one that then causes some earlier decision to get unmade which allows us to revisit some earlier optimistic choice, undo it, and try again.
The base case is hit when we run out of choices where weíve Ė whatever configuration weíre at is, like, okay, weíre at a dead end, or weíre at the goal, or weíve run out of letters to try. Whatever it is, right, that tells us, okay, we didnít Ė thereís nothing more to decide. Is this where we wanted to be? Did it solve the problem? And Iím being kind of very deliberate today about what does it mean [inaudible] update the configuration, or what does it mean for it to be the goal state because for different problems it definitely means different things. But the code for them all looks the same kind of in its skeletal form.
So let me take a piece of code and turn it into a recursive backtracker with you. So Iíve got recursive permute up here. So as it is, recursive permute tries every possible permutation, prints them all. What Iím interested in is is this sequence a letters an anagram. Meaning, it is Ė can be rearranged into something thatís an English word.
Okay. So what Iím gonna do is Iím gonna go in and edit it. The first thing Iím gonna do is Iím gonna change it to where itís gonna return some information. That informationís gonna be yes it works, no it didnít. Okay? Now Iím gonna do this. Iím gonna add a parameter to this because I Ė in order to tell that itís a word I have to have someplace to look it up. Iím gonna use the lexicon that actually weíre using on this assignment.
And so when I get to the bottom and I have no more choices, Iíve got some permutation Iíve assembled here in Ė so far. And Iím going to check and see if itís in the dictionary. If the dictionary says that thatís a word then Iím gonna say this was good. That permutation was good. You donít need to look at any more permutations. Otherwise Iíll return false which will say, well, this thing isnít a word. Why donít you try again?
Iím gonna change the name of the function while Iím at it to be a little more descriptive, and weíll call it is anagram. And then when I make the call here [inaudible] third argument. Iím not just gonna make the call and let it go away. I really want to know did that work, so Iím gonna say, well, if itís an anagram then return true. So if given the choice I made Ė Iíve got these letters X J Q P A B C, right? Itíll pick a letter and itíll say, well if, you know, put that letter in the front and then go for it.
If you can make a word out of having made that choice, out of what remains, then youíre done. You donít need to try anything else. Otherwise weíll come back around and make some of the further calls in that loop to see if it worked out. At the bottom, I also need another failure case here, and that comes when the earlier choices, right Ė so I got, letís say somebody has given me X J, and then it says, given X J, can you permute A and B to make a word?
Well, it turns out that you can Ė you know this ahead of time. It doesnít have the same vision you do. But it says X J? A B? Thereís just nothing you can do but itíll try them all dutifully. Tried A in the front and then B behind, and then tried B in the front and A behind it, and after it says that, it says, you know what, okay, that just isnít working, right? It must be some earlier decision that was really at fault. This returned false is going to cause the, you know, sort of stacked up previous anagram calls to say, oh yeah, that choice of X for the first letter was really questionable. So imagine Iíve had, like, E X, you know, T I. Iím trying to spell the word exit Ė is a possibility of it. That once I have that X in the front it turns out nothing is going to work out, but itís gonna go through and try X E I T, X E T I, and so on. Well, after all those things have been tried it says, you know what, X in the front wasnít it, right? Letís try again with I in the front. Well after it does that it wonít get anywhere either. Eventually itíll try E in the front and then it wonít have to try anything else after that because that will eventually work out. So if I put this guy in like that, and I build myself a lexicon, and then I change this to anagram word. I canít spell. Iíd better pass my lexicon because Iím gonna need that to do my word lookups. [Inaudible]. And down here. Whoops. Okay. I think that looks like itís okay. Well, no Ė finish this thing off here. And so if I type in, you know, a word that I know is a word to begin with, like boat, I happen to know the way the permutations work [inaudible] try that right away and find that. What if I get it toab, you know, which is a rearrangement of that, it eventually did find them. What if I give it something like this, which thereís just no way you can get that in there. So it seems to [inaudible] itís not telling us where the word is. I can actually go and change it. Maybe thatíd be a nice thing to say. Why donít I print the word when it finds it? If lex dot contains Ė words so far Ė then print it. That way I can find out what word it thinks it made out of it. So if I type toab Ė now look at that, bota. Who would know? That dictionaryís full of some really ridiculous words. Now Iíll get back with exit. Letís type some other words. Query. So itís finding some words, and then if I give it some word that I know is just nonsense it wonít print anything [inaudible] false. And so in this case, what itís doing is its come to a partial exploration, right, of the permutation tree based on this notion of being able to stop early on success. So in the case of this one, right, even six nonsense characters, it really did do the full permutation, in this case, the six factorial permutations, and discover that none of them worked. But in the case of exit or the boat that, you know, early in the process it may have kind of made a decision, okay so [inaudible] in this case it will try all the permutations with Q in the front, right? Which means, okay, weíll go with it, and then itíll do them in order to start with, but itíll start kind of rearranging and jumbling them up, and eventually, right, it will find something that did work with putting in the front, and it will never unmake that decision about Q. It will just sort of have Ė made that decision early, committed to it, and worked out, and then it covers a whole space of the tree that never got explored of R in front, and Y in the front, and E in the front because it had a notion of what is a satisfactory outcome. So the base case that it finally got to in this case met the standard for being a word was all it wanted to find, so it just had to work through the base cases until it found one, and potentially that could be very few of them relative the huge space. All right. I have this code actually on this slide. So itís permute, and that is turning into is anagram. And so, in blue, trying to highlight the things that changed in the process, right, that the structure of kind of how itís exploring, and making the recursive calls is exactly the same. But what weíre using now is some return information from the function to tell us how the progress went, and then having our base case return some sense of did we get where we wanted to be, and then when we make the recursive call, if it did succeed, right, we immediately return true and unwind out of the recursion, doing no further exploration, and in the case where all of our choices gave us no success, right, we will return the call that says, well that was unworkable how we got to where we were. So this is the transformation that you want to feel like you could actually sort of apply again and again, taking something that was exhaustive, and looked at a whole space, and then had Ė change it into a form where itís like, okay, well I wanted to stop early when I get to something thatís good enough. A lot of problems, right, that are recursive backtrackers just end up being procedural code that got turned into this based on a goal that you wanted to get to being one of the possibilities of the exploration. Anybody have any questions of what we got there? Okay. Iím gonna show you some more just because they are Ė there are a million problems in this space, and the more of them you see, I think, the more the patterns will start to emerge. Each of these, right, weíre gonna think of as decision problems, right, that we have some number of decisions to make, and weíre gonna try to make a decision in each recursive call knowing that that gives us fewer decisions that we have to make in the smaller form of the sub problem that weíve built that way, and then the decisions that we have open to us, the options there represent the different recursive calls we can make. Maybe itís a for loop, or maybe a list of the explicit alternatives that we have that will be open to us in any particular call. This is a CS kind of classic problem. Itís one that, you know, it doesnít seem like it has a lot of utility but itís still interesting to think about, which is if you have an eight by eight chessboard, which is the standard chessboard size, and you had eight queen pieces, could you place those eight queens on the board in such a way that no queen is threatened by any other? The queen is the most powerful player on the board, right, can move any number of spaces horizontally, vertically, or diagonally on any straight line basically, and so it does seem like, you know, that thereís a lot of contention on the board to get them all in there in such a way that they canít go after each other. And so if we think of this as a decision problem, each callís gonna make one decision and recur on the rest. The decisions we have to make are we need to place, you know, eight queens letís say, if the board is an eight by eight board. So at each call we could place one queen, leaving us with M minus 1 to go. The choices for that queen might be that one way to kind of keep our problem Ė just to manage the logistics of it is to say, well, we know that thereís going to be a queen in each column, right, it certainly canít be that thereís two in one column. So we can just do the problem column by column and say, well, the first thing weíll do is place a queen in the leftmost column. The next call will make a queen Ė place a queen in the column to the right of that, and then so on. So weíll work our way across the board from left to right, and then the choices for that queen will be any of the [inaudible] and some of those actually are Ė we may be able to easily eliminate as possibilities. So, for example, once this queen is down here in the bottommost row, and we move on to this next column, thereís no reason to even try placing the queen right next to it because we can see that that immediately threatens. So what weíll try is, is there a spot in this column that works given the previous decisions Iíve made, and if so, make that decision and move on. And only if we learned that that decision, right, that we just made optimistically isnít successful will we back up and try again. So let me do a little demo with you. Kind of shows this doing its job. Okay. So [inaudible] Iím gonna do it as I said, kind of column by column. [Inaudible] is that Iím placing the queen in the leftmost column to begin, and the question mark here says this is a spot under consideration. I look at the configuration Iím in, and I say, is this a plausible place to put the queen? And thereís no reason not to, so I go ahead and let the queen sit there.
Okay, so now Iím going to make my second recursive call. I say Iíve placed one queen, now thereís three more queens to go. Why donít we go ahead and place the queens that remain to the right of this. And so the next recursive call comes in and says, if you can place the queens given the decision Iíve already made, then tell me yes, and then Iíll know all is good.
So it looks at the bottommost row, and it says, oh, no, that wonít work, right? Thereís a queen right there. It looks at the next one and then sees the diagonal attack. Okay. Moves up to here and says, okay, thatís good. Thatíll work, right? Looks at all of them and itís okay. So now it says, okay, well Iíve made two decision. Thereís just two to go. Iím feeling good about it. Go ahead and make the recursive call.
The third call comes in, looks at that row, not good, looks at that row, not good, looks at that row, not good, looks at that row, not good. Now this one Ė there werenít any options at all that were viable. We got here, and given the earlier decisions, and so the idea is that, given our optimism, right, we sort of made the calls and just sort of moved on. And now weíve got in the situation where we have tried all the possibilities in this third recursive call and there was no way to make progress. Itís gonna hit the return false at the bottom of the backtracking that says, you know what, there was some earlier problem.
There was no way I could have solved it given the two choices Ė or, you know, whatever Ė we donít even know what choices were made, but there were some previous choices made, and given the state that was passed to this call, thereís no way to solve it from here. And so this is gonna trigger the backtracking. So that backtracking is coming back to an earlier decision that you made and unmaking it. Itís a return false coming out of that third call that then causes the second call to try again.
And it goes up and it says okay, well where did I leave off? I tried the first couple of ones. Okay, letís try moving it up a notch and see how that goes. Then, again, optimistic, makes the call and goes for it. Canít do this one. That looks good. And now weíre on our way to placing the last queen, feeling really comfortable and confidant, but discovering quickly, right, that there was no possible.
So it turns out this configuration with these three queens, not solvable. Something must be wrong. Back up to the most immediate decision. She knows it doesnít unmake, you know, earlier decisions until it really has been proven that that canít work, so at this point it says, okay, well letís try finding something else in this column. No go. That says, okay, well that one failed so it must be that I made the wrong decision in the second column.
Well, it turns out the second column Ė that was the last choice it had. So in fact it really was my first decision that got us off to the wrong foot. And now, having tried everything that there was possible, given the queen in the lower left in realizing none of them worked out, it comes back and says, okay, letís try again, and at this point it actually will go fairly quickly. Making that initial first decision was the magic that got it solved.
And then we have a complete solution to the queens. We put it onto eight, and let it go. You can see it kind of checking the board, backing up, and you notice that it made that lower left decision kind of in Ė itís sticking to it, and so the idea is that it always backs up to the most recent decision point when it fails, and only after kind of that one has kind of tried all its options will it actually back up and consider a previous decision as being unworthy and revisiting it.
In this case that first decision did work out, the queen being in the lower left. It turns out there were Ė you know, you saw the second one had to kind of slowly get inched up in the second row. Right? It wasnít gonna work with the third row. It tried that for a while. Tried the fourth row for a while. All the possibilities after that, but eventually it was that fifth row that then kind of gave it the breathing room to get those other queens out there.
But it did not end up trying, for example, all the other positions for the queen in the first row, so it actually Ė it really looked at a much more constrained part of the entire search tree than an exhaustive recursion of the whole thing would have done. The code for that Ėwhoops Ė looks something like this. And one of the things that Iíll strongly encourage you to do when youíre writing a recursive backtracking routine, something I learned from Stuart Regis, who long ago was my mentor, was the idea that when Ė trying to make this code look as simple as possible, that one of the things you want to do is try to move away the details of the problem.
For example, like, is safe Ė given the current placement of queens, and the row youíre trying, and the column youíre at, trying to decide that thereís not some existing conflict on the board with the queen already being threatened by an existing queen just involves us kind of traipsing across the grid and looking at different things. But putting in its own helper function makes this code much easier to read, right?
Similarly, placing the queen in the board, removing the queen from the board, there are things they need to do. Go up to state and draw some things on the graphical display. Put all that code somewhere else so you donít have to look at it, and then this algorithm can be very easy to read. Itís like for all of the row. So given the column weíre trying to place a queen in, weíve got this grid of boolean that shows where the queens are so far, that for all of the rows across the board, if, right, itís safe to place a queen in that row and this column, then place the queen and see if you can solve starting from the column to the right, given this new update to the board.
If it worked out, great, nothing more we need to do. Otherwise we need to take back that queen, unmake that decision, and try again. Try a higher row. Try a higher row, right. Again, assume itís gonna work out. If it does, great. If it doesnít, unmake it, try it again. If we tried all the rows that were open to us, and we never got to this case where this returned true, then we return false, which causes some previous one Ė weíre backing up to a column behind it. So if we were currently trying to put a queen in column two, and we end up returning false, itís gonna cause column one to unmake a decision and move the queen up a little bit higher.
If all of the options for column one fail, itíll back up to column zero. The base case here at the end, is if we ever get to where the column is past the number of columns on the board, then that means we placed a queen all the way across the board and weíre in success land. So all this code kind of looks the same kind of standing back from it, right, itís like, for each choice, if you can make that choice, make it. If you solved it from here, great, otherwise, unmake that choice.
Hereís my return false when I ran out of options. Thereís my base case Ė it says if I have gotten to where thereís no more decisions to make, Iíve placed all the queens, Iíve chosen all the letters, whatever, did I Ė am I where I wanted to be? Thereís no some sort of true or false analysis that comes out there about being in the right state. How do you feel about that? You guys look tired today, and I didnít even give you an assignment due today, so this canít be my fault, right?
I got a couple more examples, and Iím probably actually just gonna go ahead and try to spend some time on them on Monday because I really donít want to Ė I want to give you a little bit more practice though. So weíll see. Weíll see. Iíll do at least one or two more of them on Monday before we start talking about pointers and linked lists, and so I will see you then. But having a good weekend. Come and hang out in Turbine with me.
[End of Audio]
Duration: 50 minutes