Create a Sudoku Solver In Java In 20 Minutes - Full Tutorial

in this video we are going to create a sudoku solver in java it's going to be a full tutorial we're going to start from scratch and show the full process we're going to walk through the code in a way that is easy to understand so you'll be able to write it yourself my name is john and i do a new java tutorial video every single week so be sure to hit the subscribe button so you don't miss each week's video i also have a full java course available in the link down in the description if you're interested as always the full source code for this program is available in the link down in the description so go and get it if you're watching this video you're probably already familiar with the rules of sudoku but just in case let's go over them very quickly what you have is a nine by nine grid of numbers split out into nine three by three squares the goal is to fill out the grid with numbers following some simple rules the rules are just that each row each column and each three by three square must contain all numbers between one through nine basically what that amounts to is you can't have the same number twice in any given row column or three by three square first of all the game board that we're going to start with the grid we're going to use a two-dimensional int array so that's just int double array and we'll just call it board equals and this is the only part i'm going to paste in because i don't feel like typing it all out but this is the syntax you're going to want to use it's a two-dimensional array and with this layout you can kind of see what the board looks like and this board layout is just from a sudoku game generator that i found online so as you can see at the top we have like seven blank two blank five etc that corresponds to over here we have seven zero two zero five here since we have a 2d array of ins we have to use some number here so we'll just use zeros as the placeholder for blanks so now we have our starting sudoku board another thing that we're going to need many times in the algorithm that we write is just the the size of the grid so in this case we have a nine by nine grid so we're going to need that length of nine in a lot of places so let's just create a constant for that so that'll just be a private static final int grid size equals nine the next thing that we're going to need is some helper methods when we place a number in order to see if it's a valid placement we're going to have to see if that number already appears in that row of that column or that 3x3 square and if it does we can't place that number there so to do that we're going to need three helper methods for whether that number already exists in the row column or 3x3 square so let's just start with the first one for seeing if that number already exists in the row so we'll just have a private static boolean this is a boolean so we can return true if that number already exists in the row and false if it doesn't is number in row and we're going to need to take in a few parameters the first one is the board itself so an int two-dimensional array called board and next an int for the number that we want to check is in the row and then one more int for the row number itself technically in this case zero through eight because we're going to be dealing with array indexes so for this we're going to want to create a for loop for int i equals zero i less than the grid size which of course is nine i plus plus what we'll do is say if the board in that row that was passed in at the current column of i that we're iterating through if we find that number that we're checking then we want to return true and if we get through that whole for loop and never find the number we know we can return false because we did not find that number in the row so that should do it for our is number in row method now let's create a similar method for is number in column so we still want a few parameters we want the board that stays the same we want the number that we're looking for in that column that stays the same but of course instead of taking in the row as a parameter we're going to take in the column that we're looking at as a parameter and a lot of this method does stay the same that we copied from the row method but instead of looking at the board at row row and column i we're going to be looking at the board at row i and column column for example if we pass in 0 as the column it's going to look at the board at position 0 0 1 0 2 0 3 0 etc all the way up to 8 0 to check if that number exists anywhere else in that column and if we do find it again we return true and if we loop through that whole column and don't find it we know we can return false that number does not exist in that column so those two methods are relatively simple but the method for checking whether that number exists elsewhere in that 3x3 box is a bit more complicated but again we'll start with a copy of the column method and make our modifications we'll just call this um is number in box of course we want to take in the board we want to take in the number that we're looking for but instead of just taking in the column or the row we're actually going to take in both so we can get the exact coordinates of the number that was passed in so we'll just add int row here this one's a little tougher to visualize how we're going to do it but let me see if i can make it make sense for example let's say we need to check if we can add the value 1 to this spot here you know we already have the code that checks the row or the column we see that one doesn't exist there so we need to check this local 3x3 box so the method is going to get passed in the coordinates of this box that we're looking at and in that case that would be row one zero one so the row would be one and the column would be zero one two three four so it would pass in one for the row and four for the column what we want to do is get the coordinates of the top left corner of that local 3x3 box so that we can easily traverse that 3x3 box to check if that number already exists anywhere in there but that part is the part that's a little bit tricky how do we do that so we're actually going to need a couple of variables so let's create an int let's call it local box row for example here we come in with a row of 1 but we want to start at this position here so we need to get the row of this position how do we do that well what we can do is take the row that's passed in and then subtract row mod so mods if you're not familiar takes the first number and divides it by the second number and gives you the remainder so in our example we have a row of one divided by three as zero with a remainder of one so what we get for our example is one minus one and our local box row will be zero which is exactly what we're looking for same thing for the column int local box column equals column minus column mod three again in our example the column that was passed in was 4 so that would evaluate to 4 minus 4 on 3 which is 1. 4 minus 1 so the local box column will have the value 3. so our local box row and column will be 0 3. so the zeroth row is this first row here and the fourth column one two three four so that successfully gave us the location of the top left corner of the three by three box we were looking at and this little formula works for any box in the grid all right so now that we have that top left location how do we use it well we need to do a clever little nested for loop we'll say for int i equals local box row go while i is less than local box row plus three i plus plus so that iterates through the three rows in that grid and the same thing for the columns so we'll do four and j equals local box column j less than local box column plus three j plus plus so this will loop us through that exact three by three grid that we want to and then we want to do basically the same thing we did before we want to check if the board at row i and column j if that spot matches the number that we're looking for if we find it we return true and if we get through this entire nested for loop and never find it we know it's not in that three by three box so we can return false all right so now we have our three checks for whether the number is in the row in the column or in the three by three box for convenience when we're writing our algorithm let's write one method that checks all three of those so we can just call it to see if a certain placement is valid so we'll have another private static boolean is valid placement and for that we'll need to take in the board again of course the number that we're going to put in that spot and the coordinates where we want to put it so int row and int column basically here we just need to call those three methods and if they all return false then we know this is a valid placement so we can just say return not is number in row and we need to pass in the board the number that we're looking for and the row and not is number in column pass in the board the number and the column and not is number in box where we pass in the board the number the row and the column okay now with all of those methods in place we can get to the real meat of the algorithm here that's going to be the method that does all the recursion and the backtracking and all the magic that makes this sudoku solver work let's quickly talk about how the algorithm we're going to use works if you've ever played this yourself it's going to be very different from how a human would play it but for a computer it works great this is the start state of our board right what we're going to do is traverse the board row by row and for each square what we're going to do is if it doesn't already have a number in it for that cell we're going to look at all the numbers between 1 and 9 and check whether each of them is valid to add in this space so for the second spot for example between the 7 and the 2 we're going to loop through the numbers 1 through 9 until we find a value that is valid for this cell so can we set this value to 1 well no because one is already here in this three by three grid can we set it to two no same reason two is already present in three by three grid can we set it to three yes three isn't anywhere else in this row it isn't anywhere else in this column and it's nowhere else in this three by three grid so we set this value to three and move on and the process will start over recursively from the beginning we loop through the whole grid until we find a value that is not populated yet and it finds this first empty cell and it says okay is the number one valid in the space and yes it is because it doesn't appear anywhere in the row column or three by three square so you might be thinking what happens if we go through each of the numbers between one and nine in a given square and none of them are valid well that's where the backtracking comes in so let's say where for example we were evaluating this square here and we went through all the numbers one through nine and none of them are valid they're all present somewhere in the column the row or the three by three grid well what we do is we backtrack back to the last number that we set in this case this three here and since this number being three didn't result in us being able to solve the board we clear that out and keep trying all the rest of the numbers in that spot between 1 and 9. so can we put a 5 here no it's in the row a 6 is also in the row a 7 is in the grid but an 8 is valid in this spot so we set the cell to eight and move on again and the next iteration would again traverse this whole grid until it finds a blank spot and in the first blank spot it encounters it tries all numbers between one through nine and it keeps going through this process over and over again until it fills out the entire grid with valid moves so for that let's create a new method we're going to have a private static again it'll return a boolean and we'll just call it solve board and it'll take in as a parameter just the 2d into array board so to get started we are going to have a nested for loop so that we can loop through the entire grid so it's just for int row equals zero while the row is less than the grid size which would be nine of course row plus plus and nested inside that four in column equals zero column also less than grid size column plus plus since we're using zeros for the blanks this is a representation of the board kind of how the computer sees it so when we loop through this grid what we're looking for is a space that hasn't been set yet so in our case a blank is a zero so we just want to say if the board at that row and column is equal to zero we are going to do some stuff what does our algorithm say that we do when we encounter a blank well what we do is we start trying every number between one through nine and see if it's valid so let's write the code that loops through all the numbers between one through nine and tries all of them that'll just be another nested for loop yes there are a lot of nested for loops in this algorithm int number to try because it's the number that we're currently trying in this spot we're going to start it at 1 and we're going to go while that number to try is less than or equal to that grid size which is nine number two try plus plus so we're looping through every number between one and nine for this spot and we have to check each of those to see if that number in that place is valid luckily we have this nice convenient is valid placement method to do that so we can just say if is valid placement we need to pass in the board the number we're trying the current row that we're looking at and the current column that we're looking at and if that is a valid placement we place the number there to do that we just say board at that row add that column set that equal to the number that we're trying and of course if the first number it tries isn't a valid placement it just goes to the next one so now that we've placed this number that we're trying in this spot this is where the recursion of this algorithm comes in and recursion is sometimes weird to understand but bear with me what we need to do is call this solve board method recursively here passing in that same board so it'll go through all of this code again when it's called recursively so let's talk through an example to see what exactly is happening so let's pretend in this second spot here we tried one it was invalid we tried two it was invalid we tried three and said okay it's valid that's here in this code we saw that it was a valid placement and so we set the number three in that spot so we've set this number three and then we recursively call our solve board method and what it's going to do is again traverse the entire grid finding the first blank spot so now it skips these because they've already been set and the first blank spot that it finds is here and it does the same thing it did before it tries every number between one through nine to see if it's valid first it tries one and that's not in the row it's not in the column it's not in the square so this is a valid placement so again it'll recursively call that solve board method and do the same thing over and over again filling out this whole grid but it won't work yet with exactly what we have here what happens if we're checking a given spot and we go through all the numbers through this for loop here one through nine and none of them are valid well what we actually want to do in that situation is return false returning falsier pretty much just means i can't solve this board it was unable to put a valid number in a certain spot on top of that here though where we're recursively calling this solve board method we need to say if that recursive solve board call returns true so just if solve board board then we want to return true here so basically if we tried this number at this spot and then the recursive call to solve board succeeded which means that all the recursive calls beyond that also succeeded and bubbled back up then we can return true here too this placement resulted in the whole rest of the grid being filled out successfully in the recursive calls but if it didn't and this recursive solve board call returned false we want to have an else here that actually clears out this placement that we tried so board at row and column we want to set back to zero so let's think about what that is actually doing we found that a certain number at a certain spot was valid and we tried placing it there and then we tried to solve the rest of the board and discovered that there was no way it could do it it couldn't figure out how to solve the rest of the board with this number that it was trying so that means that this number that we were trying doesn't actually work even though it's valid here right now we can't solve the rest of the board with this number set in this position so we clear it out and set it back to zero and then it just goes through the next iteration of this for loop here and tries another number there's one last little thing we need in this method and that is at the very end and that is at the very end if it gets through this outer for loop completely then we do want to go ahead and return true if you're struggling to understand exactly how this algorithm is working trust me when i say it is not just you if you're new at all to recursion or especially if you're new to java in general this kind of algorithm with the complexity that we're looking at can take a while to sink in so just give yourself some time to allow that to happen work through it in your head look at the code walk through parts of it step by step and after a while it'll become clear to you how this is working all of this crazy looking logic that we added in here it gives it the ability to basically walk through this entire grid trying out each number in each spot but if eventually it runs into a situation where it can't successfully place any valid numbers in a spot it allows it to backtrack and try different numbers in previous spots and it'll keep going backtracking whenever it has to to perhaps change numbers that it said before that resulted in it being impossible to solve but eventually if you start with a valid solvable board this will come up with a solution and it'll do so very quickly now that we've created this giant monster of a complex method we aren't calling it anywhere yet so let's go back to our main method and call that method to solve this board so we can just say if solve board board if that solve board method returns true then we know that that board was successfully solved so we can just print out system.out.printline solved successfully and if not it's most likely because the board that was entered wasn't a valid board in the first place there are some combinations of numbers that you can put on a starting board where it's actually impossible to come up with a solution so we can just say system.out.printline unsolvable board sad face now after this runs we should have a solved board but we aren't printing it out anywhere so we have to actually print it out to prove that we've solved the board so let's just whip up a quick method uh to print the board pass in our board and we're going to use the helpful stuff any clips to automatically create this method that doesn't exist yet and it gives us this auto-generated method stub so here again we'll just do a nested for loop for int row equals zero row less than the grid size row plus plus same for the columns and column equal zero column less than grid size column plus plus we're going to do system dot out dot print not print line the board at that row and column and then also after each row we want to print a new line so we aren't just printing out all the numbers on one giant line so system.out.printline we don't even need any parameters here we just want the new line and print line with no parameters gives us that so now the moment of truth let's run this program and see if it solves the sudoku board here we go okay it's all successfully and it looks like they are all correct awesome one more thing though this printout kind of stinks it's not laid out in the nice sudoku way it doesn't have all the lines and everything it's fine but it's just not up to my standards yet so what i want it printed out like is like this where we have the the lines between each subgrid basically what we want to do is after every third row we want to put in this line of hyphens to get this line here and here and after every third column we want to put in one of these pipes one of these vertical bars so first let's deal with these horizontal lines after every three rows so back in our print board method just inside this first uh for loop we'll say if row mod 3 equals zero so for every third row and the row is not equal to zero if we don't include this part here it'll also put a row of hyphens at the very top before the first row and we don't want that so for every third row except for that very top one we just want to do system dot out dot print line uh basically we want a whole bunch of hyphens and a new line so how many do we need here looks like 11 of them one two three four five six seven eight nine ten eleven okay let's go ahead and run that and make sure that part of the printout looks good and it does now let's go ahead and do the same thing with the columns where we put that pipe character between every third column so it'll look very similar we'll just say if the column mod 3 equals zero and column not equal zero because again we don't want the pipe before that first column we just want it in between those other sections do system dot out dot print that pipe character run it again and see how it looks beautiful so right now we're just printing out the board at the very end i think it would be really cool if we could print out the board at the beginning too before we solve it so we can see the before and after that's really easy to do we just go up here before we call the solve board method and call our print board method so we're printing it out before it's being solved run it again we should see the before and after and we do that is pretty awesome pretty neat right i think this algorithm is is really interesting if you've ever played sudoku yourself before in the newspaper or on your phone or whatever you would never think about solving a sudoku board like this it would be an absolute nightmare you do it a completely different way doing it as a human but as a computer that can try out just billions of numbers super fast this makes total sense it is really easy for a computer to do it can absolutely take some time to understand exactly how it is working but just give yourself some time to do that follow along and write out the code yourself or go to the link down in the description to download the full source so you don't have to type it out and just take some time to walk through it and play around with it and go online to a sudoku generator plug in the appropriate values here to the board and see how it works if you did enjoy this video or learned something please let me know with a like and be sure to hit that subscribe button so you don't miss each week's video and i really do appreciate you taking the time to like and subscribe it's the only way these videos get out to help more people and so i really do appreciate that thank you so much for watching i will see you next time

Channel: Coding with John

Views: 10,278

Keywords: java, codingwithjohn, coding with john, java beginner lesson, java sudoku solver, java sudoku, java sudoku backtracking, sudoku backtracking algorithm java, sudoku backtracking algorithm, sudoku java program, sudoku java recursive backtracking, java sudoku recursive backtracking, java sudoku recursive, sudoku, programming

Id: mcXc8Mva2bA

Length: 20min 25sec (1225 seconds)

Published: Thu May 13 2021