Python Sudoku Solver Tutorial with Backtracking p.2

hey guys and welcome back to part 2 of Sudoku solver with backtracking now I guess let's just get right into if you only go out to more functions actually to code and then we'll go through the solution 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 understand what's actually going on here now what we need to do first of all is remember we were talking about the things we kind of need to do so obviously we need to be able to print the board out just for a nice visual and then we also needed to find empty 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 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 ah so to do this is pretty straightforward all we're gonna do is just define valid and we're gonna do is gonna take three parameters which is board number which is the the thing we've inserted and then a position now our position we'd like to come in as has actually missed this IGI here so what we'll do to start is what we need to check three things so essentially we need to check the row B column and kind of little square that would he called that we're in so to do this what we'll simply do is just say well we'll do the first step which is check row now checking the row is pretty straightforward so is checking the column the square is a bit more complicated but it's not that difficult so we're gonna 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 for I in range the length of Bo 0 which I mean will be nine but I'm just doing this in case we like made the board bigger or something and then what we'll do is we'll say if Bo and we'll say position which is what we're gonna be given 0 which will stand for actually the row because remember we're gonna get it in as row column so position 0 of pause which will be a tupple will be the row so for this row will check if pause 0 and then equals equals num and if pause one does not equal I and then will simply say this return false now what this does I know I went through this kind of fast is essentially we're gonna check through each column just like each element in the row and we're gonna 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 what do you call it as long at like we're gonna check that but if the position we're checking is actually the position that we 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 gonna find the number that we're looking for because we just put it in like that so we're gonna do in the other function you're gonna 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 work that's gonna 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 gonna check the column so uh vertically so to do this again it's pretty straightforward we're just gonna say for I in range and then the length of Bo what we're gonna do is literally like the exact same thing as this except we're just gonna change this right here and you'll see this in a second so I'm gonna say instead of this we're gonna say this is I yes that's I and this is pause one and then same thing here will just say if pause zero does not equal I now what this is gonna do is very is same thing as this scope is gonna go down now the weight goes down is we're gonna loop through every single row 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 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 okay and now we need to actually check like the 3 by 3 little cubes to make sure that the same numbers not in there this one is a bit more confusing but it's not that difficult so we're gonna do is we need to determine kind of way box were in so maybe I can bring up my output here yeah so we need to determine our B in this box this but like one of nine boxes so to do that we're just gonna use a bit of integer division to figure out essentially which box we're in so what I'm gonna say I'm gonna say box underscore X equals and we'll say box underscore y equals and for X all I'm gonna do is I'm gonna get well our exposition which is going to be the first position because that's our column right we're gonna insert your divide that by three and I'm going to say pause zero integer division by three now what this is going to do let me bring up this again is given a position so let's it like this position here is three or is 0 3 right so row 0 column 3 so we're gonna say well what box are we in so if our row is 0 well 0 integer division by 3 is 0 which means we're gonna be in the Box at position 0 ok which means like the highest up level box alright and then what we're gonna be in is well we're gonna be in box 1 in terms of X because well three integer division by 3 is 3 so that means well we're in this box so you can think of it like 0 1 or 1 0 whereas the top here is 0 0 so this box that I'm highlighting in the top left is 0 0 this one would be 0 1 this would be 0 2 then we go 1 0 1 1 1 2 and so on so forth ok that's how we're gonna do the boxes so now that we know what box were in where were we here we're gonna 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 for I in range and we're gonna say box underscore Y x 3 comma box underscore y x 3 plus 3 and then we're gonna repeat this so I should do that except we're just gonna do J and we're gonna change this to be X and I'll talk about why we do this in one second ok so what are we doing here so essentially why are we multiplying by 3 is the main question well the thing is right this these values are gonna give us either zero one zero one or two so if we get something like two well that means we're in this box right on this side so some are on the far right hand side so to actually check through these elements well this element starts at index six and then seven and then eight so to get there what we need to do is mean to simply find what box are in and multiply it by three so if we're in box two well we need to multiply that by 3 to get to index six and then same thing for the Y value right like say we're down here well we've gotten to the right but now we need to get down so if we say that we're in box at Y value to what we need to multiply that by three so that's where we're gonna start here and by adding three what we'll do is we'll add one more than so we'll be like down outside of the screen or outside of the box but since the four loops only go to what is that they don't include the last element will end up looping through zero four zero one zero zero two zero seven right will loop through all those elements that's the way this works so now we'll simply do is we're gonna say if and we'll say Bo and in this case I J equals equals num and we'll say 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 gonna check the same position that we just added in and then if that's true we'll return false because obviously we found 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 so now we just need to actually code the algorithm that's gonna use these functions and backtrack for us so to do this I'm just gonna call this solve and all it's gonna take is Bo which is just gonna stand again for board now to do this is actually fairly straightforward we're gonna do this recursively which means that we're gonna call this function from inside of itself now our base case for the recursion is gonna 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 essentially how that works 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 a 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 and then we're gonna check actually find empty so we're gonna say all right I will do this where I say find equals find empty given the board and we'll say if not find now if not find what we're gonna do is we're actually gonna return true which means that we've found the solution that we're 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 gonna do is I'm just gonna 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 gonna be working through the recursive 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 must have returned some value to us which is gonna be a row and a column now actually I think I need to go in to find empty and I need to actually go sorry go down here and return none now this just means that 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 and we'll say we're done ok so now after that we have row column equals find which was returned from here obviously so what we're gonna say now is we're gonna loop through the values 1 2 9 an attempt to put those in our solution remember that's what we do we're gonna check through all those values so do that we're gonna say for I in range 1 10 which means we'll go through 1 & 9 inclusively then what we'll do is we're gonna try this value inside of our solution so I'll show you this in one second okay so we're gonna say if valid and then board number and what he call its position which is gonna be row column because that's the position we found that was empty and num actually is gonna be I excuse me here so if this is valid what we'll do is we will plug in that value so to plug in that value what we're gonna do is we're essentially gonna put it in the board so we're gonna say board at position which is gonna be row column equals I like that okay so what we're gonna do is loop through values one to ten we're gonna make sure that if we add them into the board like they'll be valid so we'll add them and then what do you call it if they are valid or whatever like so if they're valid then we'll add it into the board and then what we're gonna do next is we're gonna make sure that or we're gonna we're gonna try to solve the solution from this point forward you as you see this works in second sopressa if solve Bo then we're simply gonna return true otherwise so we actually don't need analysis we will just say Bo row call equals zero and then at the end here we're gonna return false and this is actually our entire solution like we're actually finished but I'm gonna walk through step by step how this works as I know it's a bit confusing so what we're doing right is we're checking if we're gonna loop through values 1 to 10 or 1 to 9 and we're gonna 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 gonna add let's say like 1 into bored and then we're gonna 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 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 gonna return false which means that obviously solve isn't gonna be true so we're gonna 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 this stuff but now all we have to actually do to solve this solution is simply call solve on board now what I'm gonna do is print board before and print board after because I want to see the difference and I want to see the solved solution so that's all we need to do let me make sure they make any mistakes which I likely did okay so well I just pray 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 and let's also print a space so that we can actually see it let's just do that okay now let's try alright 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 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 Sudoku 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'd 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 in still watching right now what I'm gonna do is I'm gonna 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 is going on so let's do this I'm gonna print this there's quite a few steps but let's go up to the beginning and look at some of them so 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 0 we find so we're gonna try to insert any valid values in here now the valid one that we find is 3 so we try 3 and then what we do is we go to the next step and we try 9 now we notice that one 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 back to zero so we backtracked okay and we changed the value of what is it of 3 because by using 3 we got 2 9 which means there's no about and then here there was nothing we could put so what we do is we backtrack we set that to 0 and then we change this to 5 and then notice that we keep on scrolling down we keep using 5 because that's valid and then what we're doing is once we decide here my bad that we're 3 then we continue on for the next solution we find 9 we say 9 is 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 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]

Channel: Tech With Tim

Views: 101,592

Keywords: tech with tim, python tutorials, sudoku solving algorithms, python sudoku solver, sudoku solver python, sudoku backtracking, sudoku backtracking python, python sudoku generator, python sudoku

Id: lK4N8E6uNr4

Length: 17min 42sec (1062 seconds)

Published: Thu Apr 04 2019