Python Sudoku Solver Tutorial with Backtracking p.2

Key Takeaways

hey guys and welcome back to part two of sodoko solver with backtracking now I guess let's just get right into it we've only got two more functions actually to code and then we'll go through the solution uh print out kind of some of the steps and look at exactly how it's working and why it's doing that one more time to just make sure everyone really understands what's actually going on here now uh what we need to do first of all is remember we were talking about the things we kind of needed to do so obviously we need to be able to print the board out uh just for a nice visual and then we also needed to find empty uh sorry excuse me spaces which is what we're doing here now the next thing we need to do is find if the current board is valid so given uh kind of a position and a board check if by like when we try to put that in or given the board is it valid or not uh so to do this is pretty straightforward all we're going to do is just Define valid and what we're going to do is we're going to take three parameters which is board um number which is the the thing we've inserted and then a position now our position we'd like to come in as uh as actually this this IG here so what we'll do to start is well we need to check uh three things so essentially we need to check the row the column and kind of the little square that what do you call that we're in so to do this what we'll simply do is just say uh well we'll do the first step which is check row now checking the row is pretty straightforward so it's checking the column the square is a bit more complicated get it but it's not that difficult so what we're going to do for the row is we'll simply Loop through every single column in the in the given row so to do that well we'll just say 4 I in range the length of Bo zero which I mean will be nine but I'm just doing this in case we like made the board bigger or something uh and then what we'll do is we'll say if Bo and we'll say position which is what we're going to be given zero which will stand for actually the row because remember we're going to get it in as row column so position zero of pause which will be a topple will be the row so for this row uh we'll check if pause Z and then I equals equals n and if pause one does not equal I and then what we'll simply say is return false now what this does I know I went through this kind of fast is essentially we're going to check through each um um column so like each element in the row and we're going to see if it's equal to whatever the number is that we just added in now what we'll do though is we'll say uh what do you call it as long like we're going to check that but if the position we're checking is actually the position that we um we just inserted something into then we won't bother checking that so that's what this does here is essentially says well yeah obviously we're going to find the number that we're looking for cuz we just put it in like that's what we're going to do in the other function is we're going to insert it into the board so we'll just make sure that when we're checking through the board that if it's the position we just inserted we ignore that position but if it's any other position obviously that that's going to matter because that means we have two of the same numbers in that row right okay so that's that's fine for that so now we're going to check the column so uh vertically so to do this um again it's pretty straightforward we're just going to say 4 I in range and then the length of Bo and what we're going to do is literally like the exact same thing as this except we're just going to change uh this right here and and you'll see this in a second so I'm going to say instead of this we're going to say this is I uh yes that's I and this is pause one and then same thing here we'll just say if pause zero does not equal I now what this is going to do is very same thing as this going to go down now the way it goes down is we're going to Loop through every single brow so 0 to 9 or 0 to 8 I guess in this case and then what we'll do is we'll just check if our current kind of x value or column value is equal to um the same number that we just inserted for each row and again we'll make sure that it's not the exact position that we just inserted something into pretty straightforward uh okay and now we need to actually check like the 3X3 little cubes to make sure that the same number is not in there this one is a bit more uh confusing but it's not that difficult so what we're going to do is we need to determine kind of which box we're in so maybe I can bring up my output here yeah so we need to determine are we in this box this like one of nine boxes so to do that we're just going to use a bit of integer division to figure out essentially which box we're in so what I'm going to say I'm going to say boxor x equals and we'll say boxcore y equals and for X all I'm going to do is I'm going to get well our X position which is going to be the first position because that's our column right we're going to integer divide that by three and then we're going to say pause 0 integer division by three now what this is going to do let me bring up this again is given a position so let's say like this position here is three uh or is 0 three right so row 0o column 3 so we're going to say well what box are we in so if our row is zero well 0o integer division by 3 is zero which means we're going to be in the box at position zero okay uh which means like the highest up level box all right and then we we're going to be in is well we're going to be in uh box one in terms of X because well three integer division by 3 is three so that means well we're in this box so you can think of it like 01 or 1 0 whereas the top here is 0 0 so this box that I'm highlighting uh in the top left is 0 0 this one would be 0 1 this one would be 02 then we go 1 Z 1 1 1 two and so on so forth okay that's how we're going to do the boxes so now that we know what box we're in where were we here we're going to Loop through that box so we're simply just going to Loop through all nine elements in that box and then again make sure that we don't have the same element appearing twice so to do that is very straightforward we're going to say 4 I in range and we're going to say boxcore y * 3 comma boxcore y ultied 3 + 3 and then we're going to repeat this so actually do that um except we're just going to do J and we're going to change this to be X and I'll talk about why we do this in one second okay so what are we doing here so essentially why are we multiplying by three is the main question well the thing is right this these values are going to give us either 0 one 0 1 or two so if we get something like two well that means we're in this box right um on this side so somewhere on the far right hand side so to actually check through these elements well this element starts at index 6 and then 7even and then 8 so to get this there uh what we need to do is we need to Simply find what box we're in and multiply it by three so if we're in box two well we need to multiply that by three to get to index 6 and then same thing for the yv value right like say we're down here well we've gone to the right but now we need to get down so if we say that we're in box at y Val two well we need to multiply that by three so that's why we're going to start here and then by adding three what we'll do is We'll add one more then so we'll be like down outside of the screen or outside of the box but since the for Loops only go to uh what is it they don't include the last element we'll end up looping through 0 4 0 1 0 02 07 right we'll Loop through all those elements that's the way this works so now uh what we'll simply do is we're going to say if and we'll say Bo and in this case I J equals equals num and we'll say uh i j does not equal to position then we will return false so exact same thing as before we'll Loop through the box we'll check if any other element in the box is equal to the one we just added again making sure that we're not going to check the same position that we just added in uh and then if that's true we'll return false cuz obviously we found a duplicate now if we make it to the end of all these checks then that means everything's fine is actually a valid position so we will return true and that's it for valid um so now we just need to actually code the algorithm that's going to use these functions and backtrack for us so to do this I'm just going to call this solve and all it's going to take is Bo which is just going to stand again for board um now to do this uh is actually fairly straightforward we're going to do this recursively which means that we're going to call this function from inside of itself now our base case for the recursion is going to be that this is full meaning that we've actually filled up the entire board now remember the way that our backtracking algorithm works is actually once we get down to like this position here we've completed the board and we've found a solution because if we ever reach a position where that solution isn't valid right like say remember when we got here and we had eight we backtracked and we went back which means that eventually when we hit the end of our board we've actually found the solution because there's no other possible way to get there other than what we've done so far so that is um essentially how that works uh once we reach the end of the board we fill everything up we've actually found the solution we don't need to check if that's valid solution because we will have already found it based on the way that our algorithm works so what we'll simply do is we'll say if uh and then we're going to check actually find empty so we're going to say we'll do this we're going to say find equals find empty given the board and we'll say if not find now if not find what we're going to do is we're actually going to return true which means that we've found the solution that done so this function simply returns to us either true or false indicating whether we found the solution or not now otherwise what I'm going to do is I'm just going to say row column equals find and then down here we're actually going to start our algorithm so this is the base case of recursion essentially what this means is once we reach this case we're done and we're going to be working through the recursive um algorithm to us eventually try and hit this case so once we get to a case where the board is full we finished we've completed we found the solution and that's what's known as our base case of recursion now if this is not the case well that means that find uh must have returned some value to us which is going to be a row uh and a column now actually I think I need to go into uh find empty and I need to actually sorry go down here and return none now this just means that uh essentially if there is no squares that are equal to zero no blank squares return none which means that it will trigger this so we could return false as well uh and we'll say we're done okay so now after that we have row column equals find which was returned from here obviously so what we'll do is we're going to say now is we're going to Loop through the values 1 to 9 and attempt to put those in our solution remember that's what we do we're going to check through all those values so to do that we're going to say 4 I in range 110 which means we'll go through 1 and N uh inclusively then what we'll do is we're going to try um this value inside of our solution so I'll show you this in one second okay so we're going to say if valid and then Board number and what do you call it position which is going to be row column because that's the position we found that was empty and num actually is going to be I excuse me here so if this is valid what we'll do is we will plug in um that value so to plug in that value what we're going to do is we're essentially going to put it in the board so we we're going to say board at position which is going to be row column equals I like that okay so what we're going to do is Loop through values 1 to 10 we're going to make sure that if we add them into the board um like they'll be valid so we'll add them and then what do you call it if they are uh valid or whatever like so if they're valid then we'll add it into the board and then what we're going to do next is we're going to make sure that or we're going to we're going to try to solve the solution from this point forward you guys will see this works in a second we're going to say if solve Bo then we're simply going to return true otherwise so we actually don't need an Alys we'll just say Bo row call equals z and then at the end here we're going to return false and this is actually our entire solution like we're actually finished but I'm going to walk through step by- step how this works CU I know it's a bit confusing so what we're doing right is we're checking we're going to Loop through vales 1 to 10 or 1 to 9 and we're going to check if by adding those into our board it would be a valid solution okay we try that if it's valid what we'll do is we'll actually add it into the board and then what we'll do is we'll recursively try to finish the solution by calling solve on our new board so we're going to add let's say like one into the board and then we're going to call solve again with that new value added and keep trying trying trying trying trying until eventually we either find a solution or we get to the to the point where we've looped through all the different numbers and none of them are valid now if that happens right if we Loop through all the numbers and none of them are valid we're going to return false which means that obviously solve isn't going to be true so we're going to backtrack and say that the last element that we just added reset it because that that can't be correct and maybe possibly try this for loop again with a different value right that's what we need to do so that's essentially the way the solution works if we can't finish the solution based on whatever value we've just added we need to reset that value and try a different value and then repeat that process again recursively and that's kind of the only way I can explain this if you don't understand it after that I'd recommend go back and watch the first video on how I went through all the stuff but now all we have to actually do to solve this solution is simply call solve on board now what I'm going to do is print board before and print board after because I want to see the difference and I want to see the solve solution so that that's all we need to do let me make sure I didn't make any mistakes which I likely did um okay so well I just I should probably use our function that's print board to get that nice output so let's do that actually my bad on that uh and let's also print a space so that we can actually see it let's just do that okay now let's try it all right there we go so this is what we started with and this is our finished solution now I'll quickly skim through it and make sure that there's no like very visible mistakes but I'm pretty sure um that this is correct and this actually did work so that is essentially how we use um this kind of method of backtracking to solve our sodoko board and notice that this happened pretty well instantly like I didn't have to wait at all for this to happen and that's because of the backtracking but if I had done the naive solution that we talked about before well we would still be sitting here and sitting here and probably waiting for a few days for this to actually happen which is obviously not ideal so anyways that is kind of it for any of you that really are still interested and still watching right now what I'm going to do is I'm going to print out step by step what happens to the board every time that we call this solve function so that you guys can get an idea of exactly what uh is going on so let's do this uh I'm going to print this there's quite a few steps but let's go up to the beginning and look at some of them so uh I want to like obviously let's just look at this first row okay so what we start by doing is obviously this right here is the first zero we find so we're going to try to insert uh any valid values in here now the valid one that we find is three so we try three and then what we do is we go to the next step and we try nine now we notice that when by putting nine in here at the next step there's no valid position we can use so what we do is we set nine uh back to zero so we backtrack okay and we changed the value of uh what is it of three because by using three we got to n which means there's no and then here there was nothing we could put so what we do is we backtrack we set that to zero and then we change this to five and then notice that we keep I'm scrolling down we keep using five because that's valid and then what we're doing is once we decide here my bad that we're three then we continue on from the next solution we find nine we say Nine's valid and then we keep going going going going going until eventually we reach a valid solution and that is essentially how this works and that that's all there is really to it you can apply this algorithm to a ton of different problems um I don't know it's really useful it's nice to know and I personally had a really awesome time making this and I think it's a really cool program so with that being said once again all the code is on my website if you want to download any of this if you guys enjoyed the video please make sure you leave a like And subscribe to the channel and if you like videos like this let me know because I'm really interested in doing them and I'll definitely make more [Music]