The Backtracking Blueprint: The Legendary 3 Keys To Backtracking Algorithms

okay so to be honest I I kind of didn't have a  plan for this video but I was thinking what topics   could we address and I mean one of my favorite  topics and one topic that a lot of people have   questions about is the topic of backtracking and  utilizing recursion to express a certain decision   space or express possibilities so what I really  want to do with this is give you the toolkits   give you the blueprint that I somehow I don't know  how this came to me but it just came to me from   doing a bunch of these problems the toolkit and  and the the the patterns you can apply to these   problems and I mean it's recursion in general  but specifically for backtracking problems the   blueprint you need to apply so what I thought  up was something I always call the three keys   of backtracking I've done many many backtracking  videos right there there there there there and   also here here and here so I've done a good amount  of backtracking videos I mean but they're a while   back and I mean my video quality was pretty bad  I didn't have a mic and I kind of want to re-dive   into this and actually explain it again so why  not so what are the three keys to backtracking I   actually addressed this in my I think my favorite  video my n Queens video which is a while back I   also did not have a mic the quality wasn't the  best but that was one of those original videos   that goes a while back what I talked about is  the fundamental keys to backtracking problems   it goes like this you make choices you have  constraints on those choices and at the end   you're going and you're going to converge towards  a goal you have a decision space you can choose   from your decisions are restricted somehow and  your goal is is somewhere your goal is to do   something maybe it's to fill a string maybe it's  to fill n slots maybe it's to solve a Sudoku board   our goal would be to solve this and what we need  to do is see how each of these influence how we   shape our code how we shape our approach and the  way we think about these problems and see how we   can decompose something that's intimidating like  solving a Sudoku board which is the example we'll   do I already did a video on solving Sudoku we'll  run through this as an example to demonstrate   these concepts that I'm trying to get across so  why don't we get into it we have our choice we   have our constraints and we have our goal so what  we need to do is we need to see what each means   and also as always there's a code sample in the  description you can see that but I'll go through   the little code snippets here I'll put them right  there so you can see them but yeah so let's look   at our first concept the choice so what I see  here is I see a Sudoku board and my interviewer   says okay write me an algorithm that solves this  I have no idea how to do this do I use two for   loops or something do I just go through this so  what we need to fundamentally think about is the   core choice the core choice that we are making at  each step this is how we can craft we can craft a   recursive function to solve a problem like this so  we have a Sudoku board and yes that's a Sudoku   board it's a lot of stuff we we don't know how to  start with this but I would say that we do know   how to start with it because we know the choices  we're making what we need to do is we need to fill   these cells we need to fill those cells right and  we need to fill those cells by making choices so   I said a key word there I said a cell so our key  choice will be made on a cell so okay where does   a cell sit well a cell sits in a row and it sits  in a column so okay I have a lead I have a lead on   how I can draw a function so I'll call my function  solve and I'll pass in a row into column and the   job of the function will be to solve that specific  row and column well my next question is how do I   solve a how do I solve a cell how do I actually  do the process so let's reduce our decision space   we have a big Sudoku board why don't we get rid of  every row except the first row so the way we need   to think about this is we need to think about this  compartmentalizing into subproblems so are we want   to solve cells and when we solve all the cells in  a row then we focus on the next row and the next   row and by the time we finish every row we will  have finished but we'll get to the goal part later   so our choice at every single cell is going to be  to place a number what are the numbers we are able   to choose we can choose these guys we can choose  numbers from 1 through 9 so our decision space   that we can choose from is going to be from 1 to  9 so let's bring back that code snippet we were   working on that code snippet right there we're  trying to solve for the row and column but what do   we do inside well I know I have a decision space I  can place numbers 1 through 9 in the cell if it's   empty if it already has a number then I don't want  to place a number there but if it's an empty cell   why don't we run a for loop so let's put a for  loop right there and and there's our for loop it   runs from 1 to 9 I expressed my decision space  we're making progress we're not lost anymore we   know what we're doing so far so we saw a large  Sudoku board we broke the problem down into   solving a cell we're slowly crafting our recursive  function and we're slowly getting there so what we   now need to think about is when I solve a cell I  can place an item so once I place an item it would   kind of look like that so if I place an item it's  going to look like that and we're going to put an   item in the cell and so now I've made a choice  and now I need to express my constraints what   are my constraints so the thing is when we place  an item I could validate the whole Sudoku board   but that's a waste of time that would be to the  order of N squared and we don't want to do that   all we need to do is we need to validate the row  we need to validate the column we need to validate   the sub grid that the number we just placed sits  in so if I place a 2 here if I if in my for loop   my for loop says ok put a 2 there all I need to  know is does the 2 break the row does it break   the column and does it break the sub grid so again  I already have a video on the Sudoku solver stuff   so I don't really want to go into those logistics  I really want to talk only about backtracking here   so ok so the key here is what we need to do is if  that was a valid placement i recurse on it so why   don't we put our recursion right now do you see  that we recurse on our decision so we recurse on   our decision and we'll do some exploration but  do you see what I called it with why did I say   column plus one well I mean think about it if we  solve this column what's the next logical step   we solve the next column and then the next so  my function is a policy my function is a policy   that is going to know what to do based on the  state that it gets input so imagine this if I   am at the end of this row right over here if  you pass me a column that is out of bounds and   I am not at the final row what is the natural  decision of the recursion well the recursion is   gonna say well just solve this cell over here go  to the next row start in the first column so that   crafts a base case so this gets me to our goal  so our goal here is to reach our base cases so   one base case is where we finished our row and we  over bound we out of index on the row and we need   to go to the next row that's one base case and  the final base case is when we're down here the   final base case is when I out of bounds on the  final row when I go out of bounds on the final   row that means every row is finished if I go out  of bounds here then that means there's more rows   to finish it's an outer final row but if it's our  final row and we just finished it that means we've   finished and that craft's our base case so let's  move all our decision space stuff down a little   and let's put our base cases right there so what  we need to see here is we're slowly understanding   sub-problem down craft my decision space adhere  to my constraints converge to a base case and now   what we need to do is we need to keep in mind  what if the decision doesn't work out so if a   decision does not work out once we come back from  our exploration we need to eject our decision and   we can put that right there and it's right there  that's how we remove our decision we just remove   it from the cell we placed on so this is how it  works we craft our function based on our choice we   have base cases we converge to we have a decision  space and we undo our decisions after we explore   on them and what we do is at each of these calls  each of these calls has a goal and it tells us   was the Sudokus solvable given the placements that  we just did so these are the keys to backtracking   the choice you make what is the fundamental  sub-problem what is the core core core decision   space this is our decision space for a cell our  fundamental choice is choosing from this decision   space what we want to express in the cell once  we express that we recurse on that decision if   the decision doesn't work we come back and we  undo it and we make another choice we explore   we undo we make another choice so bring the code  back right there that's what our for loop is for   our for loop is for exploration within the stack  frame this cell needs to explore one through nine   this cell explores one through nine this or cell  explores nothing it already has a number this cell   explores one through nine so this is one approach  to solving the Sudoku problem I don't know if   there's a way faster than this because this is  pretty exponential in time but anyway this is   how backtracking works this is how it pans out in  my mind we make a choice we adhere to constraints   and we have a goal so again I've done many many  videos on this channel super cool effects going   on right there I've done many videos on this but  they were a while back and I wanted to kind of   retouch on this topic and give a kind of brief  over look into how backtracking works and a lot   of times I get questions like how do you know when  you have a backtracking problem so you'll know you   have a backtracking problem when it's easy to it's  easy to express the answer recursively and that's   kind of hard to notice unless you have experience  using backtracking often but you'll just know like   if it's if it says generate all if it says compute  all if it says if it says generate or compute or I   can't really think of other words but if it says  words that are exhaustive they're words implying   exhaustion of a decision space then you have a  really good chance that backtracking is going to   be one of your solutions the only problem with  backtracking for exhausting decision spaces is   often they are exponential in time and there may  be a more there may be a smarter way to go about   things but this is what backtracking is about we  reduced to our fundamental subproblem here and   yeah that's how the Sudoku solver works and again  I already have a video on that I don't think the   video is that good like a lot of my old videos but  yeah this is this is how backtracking works this   is the fundamental gist behind it and i really  didn't have a script for this i kind of just   went with it and just talked a lot so that is all  for this video this was a kind of briefer one and   less in depth into an actual question because I  didn't really have notes for today but yeah this   is backtracking and if you ever get a question  like this I mean practice helps but really   knowing what's going on and being comfortable with  recursion really helps make these decisions and   making crafting these recursive functions easier  it's very difficult and I honestly I'm not the   best at it either I still get stumped on very  simple problems but the more you do it becomes   more straightforward and comfortable so that's  all for this video if you liked this video hit the   like button subscribe to this channel my goal is  to make this one of the world's largest resources   for software engineering interviews and until that  happens I don't think I'm going to stop because I   think it's a necessity I think there just needs  to be people aggressively tackling these these   just this space of issues and I mean this this  interviewing system is kind of weird especially   in software engineering because a lot of people  have complaints about it but I mean if we don't   tackle it head-on I mean nothing's going to get  better if we just complain about it yeah yeah yeah

Channel: Back To Back SWE

Views: 475,435

Keywords: backtracking, backtracking algorithms, recursion, recursion and backtracking, Back To Back SWE, Software Engineering, programming interviews, coding interviews, coding questions, algorithms, Google internship, swe internship, n queens problem using backtracking, graph coloring problem using backtracking, backtracking playlist, sum of subset problem using backtracking, knapsack problem using backtracking, backtracking search in artificial intelligence, benyam ephrem dsa

Id: Zq4upTEaQyM

Length: 13min 44sec (824 seconds)

Published: Sun Mar 03 2019