Python Sudoku Solver Tutorial with Backtracking p.1

Key Takeaways

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 sodoko now this is actually a really fun project and I really personally enjoyed writing this before doing this video but what I'm going to be doing kind of in this I don't know how many videos it's going to 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 on and getting all of the uh everything kind of working now the code is not super complicated for this and 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 going to try to break it down for you guys in this video and understand exactly what it does uh but it's really useful and this is a really cool project and it looks great on a resume as well uh especially if you're a student that you made something cool like this so I'll show you guys uh my working kind of solver right now now so essentially this is the code it's nothing too long just 100 lines and most of it's cosmetic anyways in terms of printing out and like the board and everything so it's not anything too complicated uh 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 uh but this is how it works happens pretty well instantly ly 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 uh oops I did not mean to do that I guess I had my Eraser on uh 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 uh where you know like we have a valid Soko 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 uh but I'm just going to 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 spelled like that um but essentially what this is is the way 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 going to be very slow is just try every single possible combination of numbers so what I mean mean by that is just try like 1 2 3 4 5 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 um this algorithm works fine in fact 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 uh 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 um to subtract but essentially if you have what a 9x9 grid that's uh 81 squares with nine possibilities so I believe uh we end up getting something like 9 to the 81 different possible combinations of solutions now I don't know if you guys know anything about exponentials 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 would 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 to 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 nine to like the nine is still a massive number right so you get the point in that doing that is just not efficient at all so what we want to do is use something called back tracking 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 going to do is you're going to pick some kind of empty Square so step one uh pick I should have left myself more room on the side here pick empty okay so what you're going to do is you're going to pick some kind of empty Square so what we'll start off by doing and I'm just going to go from left and down to like like that okay uh is just pick this Square that's our first step pick some kind of empty square and now what we're going to do is try all all numbers okay uh 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 going to 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 uh find one that works okay uh just yeah I know you probably can't even read that cuz I didn't really leave my myself enough space to do this but let's try this okay so the what we'll do is we'll go we're going to try one we'll look in this row and we're going to validate and see if one works does one work well no it doesn't cuz one's right here I'm assuming you guys know how to place Soko 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 have haven't found one that works yet so now we'll try two does two work well is two in in the row no it's not is two in the column no it's 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 going to go to this step here and we're going to try one does one work no it doesn't we'll try two does two 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 9 425 um 3 1 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 everything you're correct but there's another step we're going to add in a second um that you will see so what we'll do now is we go two five okay um and now we'll 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 two no it doesn't three no four no it doesn't five no six does six work um I believe six does work yes it does okay so six works so now we have these this is our current solution 25 six then obviously everything else that's in here all right so next Square let's try this again don't worry I'm going to get to the backtracking part in just a second but 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 Eight's right here so that's not a valid solution so what do we do now well what we do now is we backrack 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 going to go back to the previous step and we're going to try we're going to continue from the previous step so we had tried six right so what we'll do now is we'll try seven does seven work no it doesn't cuz Seven's there we'll try eight does eight work no it doesn't cuz Eight's 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 2 five and there's nothing that can go in this Square because remember we tried what is it like seven uh or whatever number or we tried six which was here and then the next position after that didn't work so we know now after trying 7 89 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 9 now we're going to go back to five and we're going to try something else so now we'll go to five and we'll try six and we'll see does 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 going to end up with uh 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 does 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 going to 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 going to continue solutions that currently work and then if they don't work we'll backtrack to the last step and try something again and that's essentially how the backtracking algorithm works I hope that my illustration gave 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 going to be a lot faster than trying every single possible combination because if we tried every single combination what we do is simply generate um 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 okay so here we are we're at 10 minutes let's get started um on the code just the basics and then the next video we'll do most of the actual algorithm we'll see if we can put this into two videos so um this is obviously my working file what I'm going to do actually is 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 uh 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 going to need to program so the first thing we need to do is pick some kind of empty square right so we're going to need a function that does that for us given this board um in like a 2d array form is what we're going to 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 some one that's empty or has zero or something in it okay next is trying all the numbers so we're going to need a for Loop that goes through and for each empty square that we find it's going to try each number um we're going to have to find if that number is valid so we need need some function that's going to do this that's going to find if the uh the number that we put in the square is valid given the current board right and then what we'll do is if we find that 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 going to do now um in code form well what I want to start by doing is just being able to print out this board um so I'm just going to make a function that says printor 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 going to call B uh we will print this out now to do this I mean it might look a bit complicated it's not that confusing we're just going to say for I in range the length of board okay and what we're going to say now is we're going to say if I modulus 3 and I does not equal zero what we're simply going to do is just print uh a horizontal line now the reason we're doing this is just cuz we want to um kind of separate our board into like the different sections that you saw like if I if I run solver we're just going to be printing this essentially when I is uh what do you call it divisible by three because after every three rows we want to print this uh and then same thing like that right that makes sense okay so we'll do that now what we're going to do is going to do another for loop we're going to say 4J in range and we'll say the length of Bo which essentially is going to get the length of our uh what our rows right because we have a 9 by9 grid and it's set up in kind of this form then what we'll do is well we need to print all the numbers but we also need to print those horizontal line so the first thing we're going to check is we're going to say if uh what you call it J modulus 3 equal equal 0 and J does not equal Zer the reason we're doing this is so that we don't get uh a line printed on the left side immediately because well if it's the first thing in the row or like the zeroi colum then we would end up printing something CU Z modulus 3 equals 0 so we just got to check to make sure it's not zero what we'll do is we'll simply print um what do you call it this so like this little up thing and we're just going to say end equals this now what this does just means it doesn't print a back sln which means you don't go to the next line uh which is is what we want when we're printing out each column or sorry each row so now what we'll do uh I believe is we'll say if uh J equals equals 8 then we're simply going to print uh the number so which is going to be b o i j and like that now else what we'll do is we'll print b o 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 uh and yes that looks correct okay so essentially what this is going to do and I believe we're actually done now is we're just going to check so every time we're on the third row we'll print a horizontal line then what we're going to do is for every single uh what do you call it like position in the row is we'll check if it's sorry these need to go back one my bad guys so they're not in this if statement we'll 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 going to make sure that we actually do that back slash n to go back to the next line uh so let's actually just try uh print board and make sure this works and we'll 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 uh let me check oh I forgot to do this we have to do sorry end equals this so after we print this just do 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 all right we're still running into an issue ah okay so essentially I forgot to do the I modules 3 equal equal Z let's add that in my mistake guys uh and then we might have to do the same for Jay actually I think we'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 lines 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 sodoko board okay so my mistake on that guys but that's how we print it out uh and just get a nice visual output for that okay so now that we've done print board let's do one more function and then I'll move on to the next video probably and start doing more of the complex stuff uh so let's write the first function that we're going to need which is going to be find empty so remember what this is simply going to do is given a board uh just going to find some kind of empty Square now we need to just return the position of that square because that's the position we're going to 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 could 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 4 I in range the length of Bo and we'll say 4 J in range the length of b0 which just means the length of each row then what we're going to do is simply check if that position is zero so what we'll do to do that is we'll say if b i j equal equal Z return and we'll just return a topple that is the uh row and the column now we'll just denote that by this cuz usually you return column row like XY but we're going to return YX uh so just make sure that we remember that by just adding a little comment there okay so that's all I'm going to do for this video in the next video we'll finish this all up we're going to write the whole algorithm we'll do a bunch of tests um and talk about why this algorithm is so efficient so if you guys enjoyed the video please make sure you leave a like And subscribe and I will see you again in the next one [Music] oh