Python Sudoku Solver Tutorial with Backtracking p.1

hey guys and welcome back so in the next few videos what we're going to be doing is using the backtracking algorithm to solve a very common or popular game called Sudoku now this is actually a really fun project and I really personally enjoyed writing this before doing this video but what I'm gonna be doing kind of in this I don't know how many videos it's gonna take maybe two or three is first explaining what backtracking is how that works and why it's a very powerful algorithm for a problem like this and then moving on to actually writing the code and getting all of the everything kind of working now the code is not super complicated for this an algorithm is not that difficult either a lot of people here like backtracking and they think it's confusing or you have to be a computer science major to understand this it's not that difficult I'm gonna try to break it down for you guys in this video and understand exactly what it does but it's really useful this is a really cool project and it looks great on a resume as well especially if you're a student that you made something cool like this so I'll show you guys my working kind of solver right now so essentially this is the code it's nothing too long just a hundred lines and most of its cosmetic anyways in terms of printing out and like the board and everything so it's not anything too complicated but if I run it you can see this is my starting board looks something like this and we end up with a solve solution that is this now you could possibly give this a board where there is no solution I just looked one up online and found like this is the correct solution to the board to make sure that I didn't make any mistakes in this video but this how it works happens pretty well instantly and yeah it's a very fast algorithm as well for something like this okay so let's talk about how we would actually approach this problem so essentially we're given a starting board oops I did not mean to do that I guess I had my eraser on we're given a starting board maybe it looks something like this okay what we're attempting to do essentially is find a solution to this board where you know like we have a valid sudoko solution now this board that I drew here is just some random board I don't know if there's actually a valid solution to this but I'm just gonna walk through kind of the steps on how we would go about doing that using the backtracking algorithm now before I go into that I quickly want to talk about something which is called the naive algorithm so I believe naive is felt like that but essentially what this is is the weight that you would kind of approach this if you didn't know about backtracking so the common way that you might want to do this and obviously it's gonna be very slow is just try every single possible combination of numbers so what I mean by that is just try like one two three four five and keep doing that for every single square and generate every single possible combination of numbers for the board until eventually your solution just works now this would work this algorithm works fine in fact the this way of doing things you can do for almost any kind of solution the issue with this is it is slow and you can think of it as like each square has nine possibilities okay every single square that we have has nine possibilities now I mean you have to count how many squares were given to determine how many to subtract but essentially if you have what a nine by nine grid that's 81 squares with nine possibilities so I believe we end up getting something like nine to the 81 different possible combinations of solutions now I don't know if you guys know anything about Exponential's but 9 to the 81 is an absolutely massive number in fact that's probably in like the trillions or something so think about how many operations your computer would have to do to generate that like kind of subset of solutions or that set of solutions to this board and then it has to be validating all of those as well so this is really not a good way to approach this now I don't want it like I don't know if this math is correct so don't hold me to that but even if it's not and even 9 - like the 9 is still a massive number right you get the point in that doing that is just not efficient at all so what we want to do is use something called backtracking now the way that backtracking works is very simple and all you do essentially is it's similar to the naive algorithm except what you're gonna do is you're gonna pick some kind of empty square so step one pick I should have left myself more room on the side here pick empty ok so what you're gonna do is you gonna pick some kind of empty square so we'll start off by doing and I'm just gonna go from left and down so like like that ok is just pick this square that's our first step pick some kind of empty square and now we're gonna do is try all numbers okay oops don't know what happened there try all numbers and excuse my messy handwriting so essentially what we'll do is we'll start by trying one and then we'll try two and then we'll try three and so on so what we're gonna do though this is a bit different is as soon as we find a number that fits in this square that works then we'll move to the next empty square so try all numbers find one that works okay just yeah I know you probably can't even read that because I didn't really mind up myself enough space to do this but let's try this case so the what we'll do is we'll go we're gonna try one we'll look in this row and we're gonna validate and see if one works does one work well no it doesn't cuz ones right here I'm assuming you guys know a place to do essentially you can't have anything that's the same number in the same row same column or in the same kind of little grid box like this okay so one does not work so what we'll do well we're trying all numbers we didn't haven't found one that works yet so now we'll try to does to work well is to in in the row no it's not is to in the column notes not is it in the Box no it's not so two works so we found one that works and now we will repeat this so what we'll do next is we'll say okay so we'll go to the next empty square so we're gonna go to this step here and we're gonna try one does one work no it doesn't we'll try to does to work no it doesn't does three no it doesn't does four no it doesn't does five yes it does so we found nine four two five three one now I know so far you're thinking well maybe this is this is the same as just trying every single possible solution you're just essentially trying a reading you're correct but there's another step we're gonna add in a second that you will see so what we'll do now is we go to five okay um and now we're go to the next empty square because we're repeating this process and let's try okay so let's try one does one work no it doesn't does - no a doesn't three no four no doesn't five no six the six work I believe six does work yes it does okay so six works so now we have these this is our current solution - five and obviously everything else that's in here alright so next square let's try this again don't worry I'm gonna get to the backtracking part in just a second this is important okay so one no so eventually we end up and we get eight as our possible answer that's the only thing that can go in this row right but look eight it's right here so that's not a valid solution so what do we do now well what we do now is we backtrack okay so as soon as we get to a point where the solution cannot be completed because eight being here is just wrong we can't have that in our solution what we do is we backtrack now these are not really the perfectly correct steps that I'm writing here but I just want you to get an idea of what we do so when we get to eight and we find that this cannot there's no possible position for this square we can't use one we can't like there's nothing that works here based on what we currently have right well what we need to do is we need to backtrack and what that means is we're going to erase eight and we're gonna go back to the previous step and we're gonna trot we're gonna continue from the previous step so we had tried six right so what we'll do now is we'll try seven does 7:00 work no it doesn't because sevens there will try eight does eight work no it doesn't because eights here and we'll try nine does nine work no it doesn't because nine is here so what we do now is the same thing as before so now we're at the point where we have two five and there's nothing that can go in this square because remember we tried what is it like seven or whatever number or we tried six which was here and then the next position after that didn't work so we know now we after trying seven eight nine that these two squares can't be correct because with these two squares being this we can't get two valid spaces here right so what we need to do now is we need to backtrack again so what we do is we say okay so let's erase nine now we're gonna go back to five and we're gonna try something else so now we'll go to five and we'll try six and we'll see the six work yes it does okay so six works so now we repeat the process again and we go here and eventually what do we end up with well we're gonna end up with does one work no so we end up with like nine or something like that we say that doesn't work so then we backtrack so we go here and now instead of six we try seven to seven work no it doesn't what about eight eight does work okay and then we repeat the process and we keep going until eventually we reach a solution that works so essentially what we're doing is we're kind of completing one square at a time and we're gonna just keep recursively checking to make sure all these solutions work until eventually we reach one that does work so rather than trying to continue a solution that can never possibly work which we do with the naive algorithm we're only gonna continue solutions that currently work and then if they don't work will backtrack to the last step and try something again and that's essentially how the backtracking algorithm works I hope that my illustration gave you a bit of an idea as we go through this and kind of code it hopefully you'll understand it more but this is the basis of backtracking pretty straightforward and I want to again emphasize that this is gonna be a lot faster than trying every single possible combination because if we tried every single combination what we do is simply generate like 9 to the 81 different solutions and then just try them all on the board until eventually you find one that works which is really not an efficient way to approach this problem ok so here we are we're at ten minutes let's get started on the code just a basics and then the next video will do most of the actual algorithm we'll see if we can put this into two videos so um this obviously my working file but what I'm gonna do actually just copy in this board and just note that all of the code that I write will be on my website there'll be a link in the description and yeah if you want to download anything anything from there feel free if you don't want to write this all out with me but I do recommend you listen because this is really I think it's an interesting algorithm to learn so okay so we have some kind of different steps to our algorithm now let's let's go back to this for one second as we talk about what we're actually gonna need to program so the first thing we need to do is pick some kind of empty square right so we're gonna need a function that does that first given this board in like a 2d array form is what we're gonna do we need to pick some kind of empty square so that's pretty straightforward we'll just loop through and we'll look for someone that's empty or has 0 or something in it okay next is trying all the numbers so we're gonna need a for loop that goes through and for each empty square that we find it's gonna try each number we're gonna have to find if that number is valid so we need some function that's gonna do this that's gonna find if the the number that we put in the square is a valid give in the current board right and then what we'll do is if we find it's valid we repeat this kind of process and then we have this backtracking which is like if it's not valid we go back so essentially like say we put like four here and four is not valid well we need to reset this to zero so that's something we'll have to do as well so those are kind of the steps and that's what we're gonna do now in code form well what I want to start by doing is just being able to print out this board so I'm just gonna make a function that says print underscore board now you don't have to do this but it's nice to get a visual representation and given a board which I'm just gonna call Bo we will print this out now to do this I mean it might look a bit complicated it's not that confusing we're gonna say for I in range the length of board okay what we're gonna say now is you're gonna say if I modulus three and I does not equal zero what we're simply gonna do is just print a horizontal line now the reason we're doing this is just because we want to kind of separate our board into like the different sections that you saw like if I if I run solver we're just gonna be printing this essentially when I is what do you call it divisible by three because after every three rows we want to print this and then same thing like that right that makes sense okay so we'll do that now what we're gonna do is going to do another for loop we're gonna say for J in range and we'll say the length of bo 0 which essentially is gonna get the length of our what do you our roast right because we have a nine by nine grid and it's set up in kind of this form then what we'll do is what we need to print all the numbers we also need to print those horizontal lines so the first thing we're gonna check is we're gonna say if we call it J modulus three equals equals zero and J does not equal zero the reason we're doing this is so that we don't get a line printed on the left side immediately because well if it's the first thing in the row or like the 0th column then we would end up printing something because zero modulus three equals zero so we just gotta check to make sure it's not zero what we'll do is we'll simply print woody coats this so like this will up thing and we're going to say end equals this now what this does just means it doesn't print a backslash n which means you don't go to the next line which is what we want when we're printing out each column or sorry each row so now what we'll do I believe is will say if J equals equals eight then we're simply going to print the number so which is gonna be Bo I J and like that now else what we'll do is we'll print zo I J plus a space now I just need to put this in a string as well and I'll talk about this in a second okay so I think I might have done this correctly I just have to check here and yes that looks great okay so essentially what this is gonna do and I believe we're actually done now is we're just gonna check so every time we're on the third row we'll print a horizontal line then what we're gonna do is for every single what do you call it like position in the row is we'll check if it's sorry these need to go back one put my bad guys so they're not in this if statement will check if it is the third kind of element or like a multiple of three and then we'll draw that horizontal line but we'll just say end is this so that when we draw the next position it's after that and then what we're doing is we're checking if we're at the last position and then we're gonna make sure that we actually do that backslash and to go back to the next line so let's say she just try print board and make sure this works I'm gonna give it a board and let's run working and see if this works okay so we're running into a bit of an issue here let me check oh I forgot to do this we have to just sir and equals this so after you eat print this just to end equals this which just means essentially stay on the same line so when we keep printing things okay so let's run this now uh and okay that's alright we're still running into an issue okay so essentially I forgot to do the I modules three equals equals zero let's add that in my mistake guys and then we might have to do the same for J actually I think it'll be okay so let's try this all right there we go so this now is is what I wanted if we want to get rid of these horizontal on the left side I mean it doesn't really matter to me then we can just do and J does not equal zero which I'm pretty sure I had before but anyways let's run this now and there we go we get the Sudoku board okay so my mistake on that guy's but that's how we print it out and just get a nice visual output for that okay so now we've done print board let's do one more function and then I'll move on to the next video probably insert doing more the complex stuff so let's write the first function that we're gonna need which is gonna be find empty so remember what this is simply gonna do is given a board just gonna find some kind of empty square now we need to just return the position of that square because that's the position we're gonna try different elements in right so what we'll do to find this is simply just loop through the board and if we find a position that is empty and I denote empty by zero you could use a blank space you use whatever you want then we'll just return that position to wherever we're calling from so in this case we'll just say for I in range the length of Bo and we'll say for J and range the length of B of zero which just means the length of each row then what we're gonna do is simply check if that position is zero so what we'll do to do that is we'll say if Bo IJ equals equals zero return and we'll just return a tuple that is the row and the column now we'll just denote that by this because usually return column then rail like XY but we're gonna return Y X so just make sure that we remember that by just adding a little comment there okay so that's all I'm gonna do for this video in the next video we'll finish this all up we're gonna write the whole algorithm we'll do a bunch of tests and talk about why this algorithm is so efficient so if you guys enjoy the video please make sure you leave a like and subscribe and I will see you again in the next one [Music]

Channel: Tech With Tim

Views: 193,503

Keywords: tech with tim, sudoku solving algorithms, sudoku (game), backtracking algorithm tutorial, backtracking algorithm, sudoku backtracking, sudoku backtracking python, sudoku solver python, sudoku solver program

Id: eqUwSA0xI-s

Length: 17min 31sec (1051 seconds)

Published: Wed Apr 03 2019