Coding a Java Sudoku Solver - Java Programming

hi everyone in today's video we're going to  solve traditional sidoku puzzles that look   like this basically what you have is you have a  9x9 grid and you've got a total of 81 different   cells within here in each cell of the puzzle you  have to put a number 1 through n and then each row   of the puzzle needs to have a distinct number  each column needs to have a distinct number   and each box needs to have a distinct number  so those are the three main constraints in a   traditional puzzle today we're going to start  with an incomplete puzzle and we're going to   solve it algorithmically using Java let's go  ahead and pull up intellig and take a look   so the first thing we're going to do with our  code is we're going to have our input data so   let's go ahead and think about how we want to  format it it's going to be an integer of some   sort and it's probably going to be an array or  a list I'll just go ahead and make it an array   to start and now what we want to do is we want to  make a two-dimensional array and that's because   we're modeling a square here so we have an array  of arrays which models a square where each array   is a row and then you essentially have a array of  rows that you're adding so we'll call this board   and then I'll set this to a board that has not  been solved yet all right can you see how this   maps to a sidoku board so this is going to be  the first row or the zeroth row this is going   to be the second row third row Etc so you can see  here that this would be the top left box and all   of these zeros these just indicate that there's  currently no value present I could just as easily   do-1 I could do FF doesn't really matter you just  need something that is different from 1 through n   so that the code can differentiate when you don't  have a value in place so I mentioned that there   are three different rules you have to follow when  you're placing a number let's go ahead and write   methods to check all three of those things so  for the first one let's go ahead and check for   distinctness within a row uh let's go ahead and  say private static Boolean we'll have it return   a Boolean if it's allowed or not allowed in row  so we want to pass in the board we want to pass   in the row and then we want to pass in the number  so what we want to do here is we'll say for INT   I equal 0 I less than we'll just say nine for  a second i++ we can say if board row I equals   number so let's think about what this is doing  here for a second so what we're doing is we're   iterating over each column within the particular  row so effectively we're looking at the whole row   right here if the number is there then it's not  allowed we have to return false other otherwise   we return true here now I don't love that I  have to use this nine I think what I want to   do is I want to create a few constants so the  first constant I'm going to make is the box size and that has a length of three and there are  also three boxes in a grid so now I can say grid size and then I can say that that is box size  times box size the idea here is that you'd have   a grid size which always has to be a perfect  square and then your box size doesn't have to   be a perfect square but it's typically going to  be an integer that's greater than or equal to two   so the typical size is three with a grid size of  9 by9 so in this case we would say we want to go   over the grid size and you can see here what we're  looking for is we want to go with the current row   and every column if the number already exists in  the row then it's no longer allowed otherwise it   is allowed and we can return true in that case  there is however a more succinct way that you   can code this if you use Java 8 streams so I'm  going to go ahead and do that so what I can do   is I can say return instream range and then just  like the for loop I want to go zero to grid size   and then I want to make sure that none match  over all the columns I want to do board row   column equals number so if this is true then  I know that there are no entries within the   current row whose number equals number all right  so that was the first rule the second rule is now   we want to apply the same logic to columns so if  I copy the code and I say allow in column instead   of row I want to put column and then now I can  say for each row in each column I can do that   so let's double check this logic so I'm going to  look over the whole grid and then for each row I'm   going to make sure that within the current column  I'm going to check every row if the number exists   and if none of them are there then it is outow in  the column as well all right now for the last rule   number three which is a good bit more difficult  to code and that is when you have a box you want   to verify that the box has distinct values as well  so let's say that I wanted to replace the middle   value in this top left box what I would need to  do is I would need to check this 3x3 box right   here so probably the easiest way to do that is to  take a look at the coordinates of the entry that   I am trying to replace and then find which box it  belongs to so to find the box that it belongs to   what I want to do is I want to find the top left  entry within the box so that would be here here or   here within the top row here or in the middle row  it could be either this one it would be this one   or that one and then for the bottom row it would  be here it be here or be here so to do that what   I can do is I can take the row and column number  currently here and then I can subtract off of it   to get to the top left element within each box  so worst case let's say that I'm in the bottom   right cell right here I would want to subtract  two from the row and the column number if I am   in the middle it would be one and one versus I'm  already in the spot it would be zero so every time   it's going to be less than the length of the  box so what I need to do is I need to take the   original row and column position here and then  I need to subtract something less than the Box   length and what it's going to be is it's going  to be the position here minus the position mod   the Box length I'll go ahead and write that code  here shortly so that you can see it so let's go   ahead and make another method private static  Boolean allowed in box this time we want to   take the board we want to take the column number  and we want to take the row number and we want   to take the number that we are checking against a  lot of variables to pass in so basically here what   we want to do is we want to have two different  starting variables so the first one is we're   going to say box column and that's going to equal  the current column minus the column mod box size   so at most with a 3X3 grid let's say that our  column number here was 2 it would be 2 - 2 mod   3 which is going to be 2 so 2 - 2 is 0 or if it's  in position five here then it would be 5 minus 5   Mod 3 which is 2 so then that would be 5 - 2 = 3  so that looks like that's what we want to do so   let's copy this line of code and copy it for row  we can say Box Row equals row minus Row mod box   size and now what we can say is we can do 4 in i  = 0 I is less than the box size i++ for J equal Z   J is less than box size j++ and now here what we  can say is we can say if board box row plus I and   box column plus J equals number then we found it  which means that it's not allowed we didn't find   it we can return true so basically what we're  doing here is we're finding the dimensions of   where the Box boxes and then we're iterating over  the rows and Columns of the box and then here is   where we find where on the board we are with the  current box and then we compare it to if it's the   number that we're looking for and then we return  either false or true depending on if we found it   honestly there's probably some way that you could  convert this code into a stream probably with flat   maps and again with in streams in this case I  don't really see the readability benefit so I'm   going to go ahead and leave it it as is all right  now let's go ahead and put a singular method that   checks whether all three of these conditions are  true so we can make this a private static Boolean   as well we can just say is allowed and we'll want  to take the board column row and number just like   last time and then we'll want to check all of them  so we can say allowed in row that be board row   number and allowed in column board column number  and allow it in box board row column number Sweet   so now we are checking for whether at a given  position we could insert a particular number so   now let's get into the meat of the real algorithm  here you might want to think well I could just put   the first number that goes here and then I would  find the next number that goes here and so on   and so forth but if you've played enough soku you  know that wouldn't work because let's say that you   put a one here because it's allowed you put a two  here but these aren't ones and twos just because   they're allowed during the first pass doesn't  mean that they're going to be allowed when you   put other numbers in that are actually correct so  what you need to be able to do is you put in the   first number that you find that's valid and then  you keep going through the puzzle trying to solve   it until you find a number that cannot have a  number inserted meaning that you had invalid   numbers earlier what you do then is you need to  backtrack so we're going to add this backtrack   type functionality via recursion let's go ahead  and get into it so let's make a private static   Boolean solve method and we'll go ahead and just  have this take the board so now what we want to   do is we want to iterate over every row and column  of the board so we'll do that with two different   for Loops so for row equals zero row is less than  grid size row plus plus and then we'll do the same   idea for columns lot of for Loops in this code now  we're at a particular cell within the board if we   scroll back up to the board let's say that we're  here we have a zero so what we want to do is we   want to try to insert a number here if we were to  have landed on the seven we would skip it so what   we can do is we can add an if check so we can say  if board row column equals our Sentinel value of   zero now we want to do some extra code here here  otherwise if we already have a value and we've   already solved everything we're going to want to  return true here at the end now in the case where   we need to fill in a number we're going to have  yet another for Loop that's going to say int num   equals 0 num is less than grid size num Plus+ now  that we're in here we need to check if the number   is allowed so you can say board and I don't like  how I have column in row switched here I'm going   to go ahead and fix that so let's fix that here  row and column and then I'll switch these around   row column and number so now we have an allowed  number within our cell so what we can do is we can   say board at the current row and column equals num  so let's say that a value of one is valid in the   top left cell and we just put a value of one here  so now here's where we're going to use recursion   and we're going to try to solve the board again  further and then if we can continue to solve   it then we're going to return true if we can't  solve it then we got a bail we're going to say   row column and we're going to have it equal zero  again and then one last case we have to account   for is if we've iterated over all the numbers and  no numbers are allowed here so let's say we've   reached here then we're in trouble we're going to  have to return false okay so let's double check   our logic cuz recursive functions are notoriously  hard to get right so here We're looping over the   board and if the current cell we are on doesn't  have a value yet which will be the case for the   first cell that we enter when we enter this  method the first time then we need to look at   the set of numbers and actually I do have a logic  error we want to look at numbers so we want to   look through 1 through 9 rather than 0 through 8  and now in this case if we're looking through 1   through 9 we want to make sure if the numbers 1  through n are allowed so in this case a value of   one is allowed so we replace the value with one  and then we call solve again with the board that   we just updated so now we go back up here we're  iterating through again and note that we're going   to skip the first cell because it has a value of  one not of zero so now we're going to go to the   next cell and then we're going to try to find a  number for it let's say eventually we hit a cell   that doesn't have a value We're looping over the  numbers 1 through n and none of them are allowed   then what you'll do is you'll hit false which  means that you'll instead of returning true here   solve is going to return false and you're going to  replace the number that you had put in previously   and then it'll go in and it'll check to see if  there is a new one that can be put there and if   there isn't then that will return false and what  you'll do is you'll just keep backtracking until   you find a valid value you can put instead so I  think this looks good because then at the bottom   if all is good then we were turn true meaning  that none of the elements in our board had a   value of zero so we're getting close to testing  this out what we can do is we can say if solve board yay else oops so the oops could either mean we  have a coding error or it could be that let's   say we were given invalid input data and  the original sidoku puzzle wasn't actually   valid to start with let's run the code and  see what we get sad so I've got a bug so I   think what's going on is I'm probably swapping  row and column somewhere uh oh right here okay   so this should be the row and this should be  the column because when we call allow in box   we call row column okay let's go ahead and try  it again and there we go perfect we'll just go   ahead and pretend that I intended to introduce  that bug to prove that when it doesn't work it   correctly shows it not working we'll just  pretend so now I want a method that prints   out the result when it's successful so we'll  just call it print result board let's have   the IDE help us out a little bit here and now  we can do is we can say for row over the grid and for column over the grid then we'll say column Plus+ now  we can do CIS out except instead of   print line let's just do print and then let's do board row and column but I want the print  logic to be dependent on whether the cell   value is zero or not so we'll say cell value  equals the current value at the board if Cell   value equals zero then we're going to want to  print empty otherwise we'll print cell value   and I also want to add a space before and after  so that the numbers aren't quite so condensed   so the other thing I need to do is at the end  of each row I need to add a new line and then   sometimes what I want to do is depending  on the row position I want to print out   some dashes so let's go ahead and if row uh mod  box size equals zero but row also doesn't equal zero so in this case what I want to do  just add a few more extra parentheses I   want to add a little bit of formatting in  this case so I'm just going to add some   dashes here that will help us delimit  the different uh boxes within the grid   okay so this is all right so now I want  to add some some sort of bars in between   the columns we'll follow the same sort of  logic that we did here and we'll look at column column then this time we don't want to  add a new line character and we only want to   add that little separator right there and then  I want to add a few more dashes here let's run   it and see how it's looking sweet so we solved  the sodoku and now we're formatting it as well   so feel free to try out this code on your own  try this out on different sodoku puzzles maybe   go ahead and introduce a sidoku puzzle that  doesn't have a solution and verify that it   correctly doesn't find a solution or maybe if  someone's stuck on a puzzle you can solve the   puzzle on your computer and then you can give  them some hints maybe something to think about   and that was a sidoku solver using a backtracking  algorithm that uses recurs verion within Java if   you enjoyed today's video please do smash that  like button I'd really appreciate it thank you   for watching I hope you have a good rest of  your day and I hope to see you next time take care

Channel: Will Tollefson

Views: 2,413

Keywords:

Id: 81E0hGmVaeY

Length: 21min 12sec (1272 seconds)

Published: Fri Nov 17 2023