Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)

Key Takeaways

so today we're gonna look at a problem that is on the caliber of n queens in terms of backtracking this is the Sudoku solver problem so basically you're given a Sudoku puzzle and you need to create an algorithm that solves that puzzle we are going to make this problem fantastically simple in this video because once you know the keys to solving it it becomes very easy to implement it's fine you can come through ok so we're going to apply the same keys the three keys to backtracking and we're going to create a recursive algorithm that solves each cell going through so after this video will you be a better person probably not well you know how to solve a Sudoku puzzle I'm pretty sure you will so let's get into it all right so I've noticed in the past few videos that I have been pretty loud and like yelling I don't know I get kind of excited doing these but I'm gonna take a little tone down approach to this one implement a Sudoku solver this question follows the same pattern as her previous backtracking problems we're going to make a choice we're going to have constraints on that choice and we're going to have a goal that we want to reach at the end here's a pseudo keyboard let's first look at the constraints and the rules on this problem we want to have only the numbers 139 in every row every column and every sub grid you can see there's nine sub grades here we have a nine by nine board and we're going to have three sub grids and each of these rows so there's a subject there's one there's one you can you see what I mean so the key is whenever we're doing problems like this there's many ways to approach them but we notice with this problem that we are told to make choices and find a globally correct answer so this probably entails backtracking but we're going to look at both approaches to this problem the brute force as well as the backtracking approach and see how they differ so our first approach to this question is going to be a brute-force approach so the brute force goes like this we're going to generate every single possible board of Sudoku it's not going to be a valid pseudo board just every possible board that we could generate from a nine given this we would try to place a one-year numbers one through nine here numbers one through nine here 1 through 9 1 through 9 1 through 9 we would generate every single possible board and then once we have all the possible boards that we could have gotten from the certain issue arrangement then we validate each of those boards we validate each of the exponential amounts of full boards that we get at the end so generate all boards validate all of those exponential boards exponential amount of boards the problem is that in a well-formed sodoku board there's going to only be one solution so we are going to be generating and exponential amounts of boards we are not going to direct our recursion we're just going to generate all the possible boards it can literally be a board of just all fives all these empty spaces get fives and then we're going to see whether that is a valid sodoku board and we're only going to choose one of that exponential amount it's wasting a lot of time and that's not the approach you want to go so what we want to do is we want to direct our recursion and we want to use backtracking for this problem so now we get to the three keys to backtracking to solve this problem the three key things we need to understand when we solve this first of all we need to be cognizant of our choice every time we see a cell with a number we can't do anything with that it already has a number whenever we see an empty cell then that is our chance to take action and and place a number what numbers can we place we can place a number 1 through 9 in an empty cell that is our decision space every single cell is going to have a basically a recursive call that has the potentiality to place 1 through 9 so whenever used this cell I say hey let me place 139 when I reached this cell I say I can place 1 through 9 and then i recurse on that decision we choose a number recurse on the decision we are going to traverse the board in a fashion like this we're going to go row by row and we're going to solve each column in the row when we finish a row we're going to advance to the next row and we're going to set the column back to zero solve column zero all the way up to the length minus one and then we know we're done and then we go down here to the next row and reset our column that is our choice in the empty spaces we're going to place one through nine so our constraints our placements cannot break the board so if I place a 5 there that means we broke in our constraints do you see here in the road there is a 5 right there so we cannot do that our constraints are when we place an item it cannot break the board when we place an item it can't break the board what we do is when we place an item before we even place it we see will this item break the pseudo whoo properties we would not even place 5 there because we know it would break it but how do we know are we going to do it N squared time check and check the whole board check whether the whole board is invalid no and here's the reason why every single decision we make up to the point of this placement whether we're here or whether we're all the way down here every decision ensured that that placement would be a valid board we do not place an item if it breaks the board so if I place a 1 here and then I have to make a placement in the next cell I know every placement before what I'm doing right now did not break the board so what does that mean that means the placement right there the placement I'm doing all I need to see is does it break the row it's sitting in does it break the column it's sitting in and does it break the sub grid it is sitting and these are our constraints so right here all I need to know is can I place a 1 here no I can't there's a 1 here and there's a 1 in the call can I place a 2 here there's no 2 and in the column there's no two in the row and there's no 2 in the sub grid so I can place the two less place too and so now I come to this cell this cell already has a number I skip it and now I come to this cell and you see what I'm getting at we tried placements in each cell going in a fashion where we traverse the board like this and go finish a row go to the next row finish that row goes next row finish that row go to the next row and what we do is we ensure that the placement we are placing is not going to break the board and what will happen is when I'm at the tap placement I know every single placement performing has not broken the board and therefore I only need to check the row column and sub grid finally what is our goal our goal is to fill the whole board we want to fill every empty space in this board how do I know I am finished when I finished the last row and I go to the next row if I am out of balance on the number of rows if my thorough number on working on equals the number of rows I am an indexed one out of bounds and then I know I have finished every row remember in programming we index off a zero not one so now that we have the three keys to recursion we know how to approach this problem and we can build a recursive function that one makes a choice on every empty cell trying numbers one through nine before we place an item and do our recursion on it we are going to see if it breaks our Sudoku properties if it does not break our properties we place the item advance to the next column if we finish a row we're going to advance to the next row and then go to column zero that is our base case and again the code is in the description if you want to see this I've commented every line it is so crystal clear and it will make sense when you read it so now let's get on to the space and time complexity to this problem so if you want to see the full solution to this problem the code is in the description commented fully has passed test cases only code you can throw it in there and try it yourself so that you can get a deep understanding on this problem I highly encourage you to check the code out as well as this explanation so for the time and space complexities to this problem it is kind of it doesn't really make much sense to really discuss time complexities because sodoku boards is traditionally our nine by nine so we can't really scale the size of our input Big O is all about tail behavior and scaling input and pounding on the time and space it would take for our algorithms are up but Sudoku can be generalized to an N by n board and it is a np-complete problem when you generalize the Sudoku problem to it and by n board and therefore we know that at least it is going to be an exponential if not super exponential time complexity so you can do more research on this but definitely in an interview you're probably not going to need to do any proofs or know the rigorous balance only time and space for something this rigorous and difficult this would be difficult to pull off an interview code wise at least until you can find the time in space it would be even harder to understand the amount of force we can make from every decision point and put a bound on the time complexity of that algorithm and how it runs that's all for this video again check the code in the description fully commented it is actually a lot of code that's why I'm not walking through it here I really wish I could walk through it but it would take me like half an hour to an hour to write everything thank you for watching I hope you understand this question better if you like videos like this hit the like button subscribe to the channel I'm trying to cover as many questions I can I want everyone who watches is to have a deep understanding of these concepts and questions and not feel lost when you're answering them because all it takes is understanding the intuition and then you can tackle different questions that you've probably never seen before [Music]