One of the most important concepts in algorithmic learning and data processing in python code is recursion and writing programs that utilize backtracking to process all possible answers! Code available here: https://github.com/plemaster01/sudokuRecursion
This video shows start to finish how to take a matrix of the values given at the start of a sudoku, and process that data through two functions checking every space for validity against every possible number!
In the sub function 'valid' we check every row, column and 3x3 grid of blocks against the numbers 1-9 to see whether or not a certain number works in that space, and then in the 'iterate' function utilizes recursion by checking each space only until a valid number is found then goes to the next space and until it finds a space where no valid solution can be found then it begins backtracking until no additional solution is possible.
If you have any questions on what you saw in this video or want to see something specific in the future just let me know about it in the comments below!
Be sure to like and subscribe and check out the rest of the channel for over a hundred more great tutorials!
Thanks for watching and Good luck with your code!
what's going on guys welcome back to the
channel and today's video is going to be
creating an automated sudoku solver
inside of python
[Music]
okay so the idea behind a sudoku puzzle
is you end up with the numbers one
through nine in every row every column
and every three by three block of nine
values um and so as a person solving
this you typically would look for blocks
that have fewer white spaces um and
maybe more crossing values and start
with the easy one but to create a
program that does it it has to be a
little more orderly a little more
structured than that
and um so
what we're going to do is we're going to
create a program that iterates through
the pi
through the sudoku puzzle that we give
it and it checks what numbers are valid
for what squares and it'll create a
solution at the end
so i think the process of how this makes
sense from a code standpoint is going to
make more sense if we just get into it
so let's just get into it
so i took the liberty of grabbing two
examples from the internet
you can grab whatever puzzle you want or
you can use the exact same ones i have
but i already typed them out in a grid
matrix format so this is basically just
a list of lists um and i suggest if you
have a specific puzzle that you want to
follow along with you type it in in this
format as well because that makes it
kind of the easiest to iterate through
it really is a matrix a sudoku puzzle is
just a nine by nine puzzle
and so one more thing that i'm just
gonna do right in the beginning is i'm
gonna import numpy
and the reason for that is if you saw
this puzzle even after we solved the
puzzle we're going to want to display it
in the terminal for the user and if you
print out something that looks like this
it doesn't print out as a nice matrix it
prints out
just as one long row but you if you use
the numpy built-in matrix tool and then
feed it in the puzzle it's a really nice
formatted
matrix so it looks a lot better we're
going to use this format for displaying
the outputs so
that's just one more thing about that if
you don't want to import numpy for some
reason or you can't i guess you don't
have to you'll just have one long row
with all the information in it and it
won't look as good um
but let's actually start writing some
code so one thing that we're going to do
for every block in the puzzle is check
if it's a valid result so
what i said before and actually i'm
going to pop over to a quick display
here
if you have a sudoku puzzle the way our
program is going to work we'll start
with the top left and you saw in the
matrixes i made any value that we don't
or any space that we don't already know
the solution for when we started up i
put a zero in there um in instead of a
blank space you could put a blank space
in there but i put a zero in as a
placeholder and our program is going to
go through the matrix in any space that
has a zero
it's gonna start checking to see based
on row column and three by three block
if each number is available so it'll
start by checking is one okay and it'll
see that there's a one in the row or one
in the column depending which one you
put first it'll say no and they'll go is
two valid and it'll check for the row
it'll check for the column i'll check
for the block and then if two is valid
it's going to move on
and it's gonna hold a two in there but
then it's going to check the next space
for the exact same series
and it's going to do one no i can't do a
1. it could i be a 2. and now it's going
to see no i can't do a 2 because it's
going to read that there's a 2 there
can't do 3 can't do 4. but as soon as it
gets to a block which if if every number
that was selected isn't the right number
it was just valid at the time then
what's going to happen is the code is
going to start clicking backwards and
then so say theoretically the first
number that was valid for this one was
two and you got all the way to the last
number in your puzzle um and that one
there was no valid solution one through
nine because this was a two instead of
the next available number which would be
like a 5.
well this code is going to click all the
way back
until it finds a solution that is valid
and so if it has to go all the way back
to the first loop as long as you set
this up to be recursive code then it's
gonna come all the way back to the top
one increment to a three and then keep
moving on that'll make a lot more sense
i think once we program it so let's just
start programming it
so a valid check is going to be check
that the row the column and
we're going to pass in what value we
want to check it for and we're going to
do this because we're asking it to check
through all of the possible numbers for
each space inside the sudoku
so we're going to
let's just say right in here check row
column
then three by three
block okay
and so we were given everything we need
to check all of this data as long as we
call the actual puzzle inside this
function you could pass it in and you
could return it but if you just make it
a global inside of your function then
you can use it the whole time
so
let's go ahead and say
let's uh start by checking the whole row
so 4i in range and we're going to do 0
to 9 and if you don't know about python
for loops it's
it's non-inclusive on your endpoint so
it's this is actually saying we're gonna
do i is equal to zero one two three four
five six seven and eight but not nine
which is perfect because in code
counting starts from a zero not a one
and so even though there are nine
columns that actually means we have zero
through eight
um
okay so
for i in uh range zero through nine and
what we're going to check is if puzzle
at rho so we're gonna hold the row
constant and we're gonna iterate through
using that index value
and we're checking to see if that's
equal to the value that we're checking
it against so
say we wanted to see if the top left was
valid for a 2 we're going to go through
the row and check at position zero one
two three four five six seven oh and we
hit a two if you hit a spot that's equal
to that um value then what we need to do
is we need to return false
and instead of doing like an else return
true we're gonna go on and check the
next condition because it's not just
um it's not just well as long as there's
nothing else in that row it's if there
is something in that row it's false
otherwise we have to check these other
conditions
so next is going to be pretty similar
for i in range and then we're going to
check 0 through 9 again
but this time we're checking columns and
so it's a little bit different if puzzle
at position but we're not going to do
column then i we're going to do i
then column
because the way you address a specific
item inside of a list
is with row and then column you give it
two index values and so what we're
saying now is okay hold the column
steady and then iterate through the
whole
through every row
so
now it's the same condition though if
that value is equal to whatever we just
looked up in the table then we have to
return false okay and so row and column
are really the easy ones in this uh in
this programming
a more complicated one is going to be
finding the x start and the y start
because
if you think of the box that you're
checking
if we give them a value let's pull one
of these up if we want to check a value
here the x start position is zero but if
we give a position here the x start
value is also zero so zero one and two
in the terms of columns or rows are all
supposed to start from position zero
zero as you check your box and it's only
supposed to go three and then
three four five or the next one and six
seven eight check the third one so
essentially we need something that
corresponds zero one and two all to the
value zero and then three four and five
all to the value one and then uh six
seven eight all to the value of two but
then it actually has to start from zero
three or six so
luckily python has a
piece of math that's built in that we
can use called floor division
so um and i'm just going to program it
and then talk about it real quick but if
we look at the column divided by 3 floor
divided by 3 which is the forward slash
twice
this is saying division rounded down to
the nearest integer
so this is a super handy tool that
python happens to have built in but what
we're saying is divide the column by
three and then round down and so if you
think about the columns zero one and two
they're all going to round down to zero
and then the column three four and five
divide by three are all going to round
down to one so that's super useful but
the actual x start position remember was
that times three
so
um that's how we're going to figure out
where to start for the x and then we're
going to do the exact same thing with
the y's just with row instead of column
and we're going to create a variable
called y start
and then those are the two positions
that you're going to start in
and then we're going to create another
for loop to check for valid conditions
and we're going to say for i in range
0 to 3
and
we're gonna check if
puzzle
at positions
y start
plus
i
and then
j x x start sorry you gotta be
gotta be careful with your typing and
getting the x's and y's right and x
start plus j
oh i'm sorry this is a this is a nested
for loop so we need for i in range 0 to
3 and then for j
in range
0 to 3.
and we need to nest that for loop in
there because we're going one two three
and then going to the next row down one
two three and then the next row down one
two three and checking uh
you know nine different values but it's
really three values in three different
rows so it's three columns inside three
different rows and that's why we use an
i and a j index or variable
and we're checking to see just like the
previous two if those are equal to the
value that we're checking against and if
they are then we're going to return
false and now we have finally checked
all of the conditions that could cause
failure and so if none of those returned
us out of the program with false then
we're going to return true because that
means the value is valid
okay so um we're going to go ahead and
move on to actually solving the puzzle
because so far we've created
a way to check if an individual space is
valid for an individual number but we
haven't created the code that's going to
actually go through the entire grid and
check each space against each possible
value
so to do that i'm going to create a
function that i'm going to call iterate
and i'm calling it that because it's
going to iterate through this loop
numerous times
each time it finds a valid number it's
going to go on to the next space
and iterate through that one unless it
doesn't find a valid number then it's
going to actually click back one space
and iterate to the next value in there
and so i'm calling it iterate you can
call it solve whatever you want this is
the actual main driving loop of the
program
and just like our previous function i'm
going to call the global puzzle
and then for i in range
0 to 9 so just like before
global puzzle put that on its own line
and then for i in range 0 to 9
and
for j in range 0 to 9. so we have
another nested loop here
and the reason we're doing this is we're
saying we're going to check through
every single space in the function so
we're checking
zero through nine
over and over and over again nine times
so again i already said this but in the
ranges it goes zero to nine not zero to
eight because it's not end inclusive so
you do need to go one higher than the
actual total number of loops
okay
but now what we're saying is if puzzle
at position that's going to be i by j
is equal to
and we're going to
check if it's equal to 0 because those
are the ones that we need to solve for
and when you do equals two you do two
equal signs
and we're checking that's equal to zero
and now let's set up a loop that's
actually going to call that valid
checker so we're saying if we've found
an empty space which is a zero in the
sudoku
for number in range and now instead of
doing zero to nine we're going to do
values one through ten so just like
before what we actually want this to
check for is the numbers one two three
four five six seven eight or nine so to
do that we're actually telling it start
at one go till nine you have to go one
higher because it's not inclusive so
then
we're going to say okay for all of those
values check if
it's valid at row and then column and
then number right so those are the three
things that it needs to get so we're
going to say well what's our variable
that's row it's i what's our variable
that's column it's j and then what's our
variable that's the value it's num so
that's our number placeholder
and
what we want to do now this gets to the
point of doing like nested function
calling so this is the way of doing like
backtracking recursive code
if we do find a valid number it's time
to go on to the next one so what we're
going to do is we're going to set puzzle
at that position i j that we just
checked
we're going to set that equal to that
number for the time being and then we're
going to go through and iterate again
and the beautiful thing about this
function is it's going to look through
for a zero value so as long as we set
this value
equal to that new number and then call
iterate again that number is no longer
going to get checked because now it has
a placeholder being held for it
and then what we need to do is if
iterate does ever complete but we
haven't solved the puzzle we need to set
that variable
puzzle at position i j we need to set
that back equal to zero so that the next
time it clicks back a level and runs
iterate again it'll check that space
again because now what we've said is hey
the function finished and there are
values that are
not valid and there are still unsolved
values
um and so we've run through the entire
realm of possibilities and we don't have
a solution so we need to punch backwards
and keep setting one variable at time or
one space at a time back equal to an
empty until we find a valid loop
so i've probably done a lot of talking
that maybe was more confusing than the
code we wrote but i hope that that makes
sense and so once we've done that for
all of the values we return and at the
end of all of this
i'm going to actually remove the print
statement from before we run everything
and i'm going to put it in here so back
at this initial for loop where we
started the iterations that's where we
want to print the solution once it
finishes and then the only other thing
we have to do is actually call the
function to start up when we run our
program
so let's see why am i getting a
i forgot a colon
okay
so i think that you can let it
automatically reformat if you want i
think that this should work so let's
just go ahead and run it let's take a
look again we're running it for this
puzzle which has got uh
zero zero zero four zero one so that's
this puzzle let's just run our function
and take a look
okay so we get 928-431-576
you can see if you were to print this
out or stencil it into the um draw those
numbers over top of it six one three
five eight
yeah this looks good we don't have any
repeats in any rows or columns that i
can see
if you notice a problem with it let me
know in the comments below let's go
ahead and check it against one more
puzzle so i'm going to go ahead and
rename this one just puzzle
and then change this guy to puzzle two
so uh now it'll check against the other
puzzle which is zero zero zero two eight
that should be this one
yep four one five seven six three nine
two eight four one seven eight six three
two five nine yeah okay so we just
created a program which really was i
mean the actual functional part of this
code was not even 40 lines of code like
a lot of these lines are just holding
the puzzle
and we created a solution that can solve
any sudoku so hopefully you found this
useful if you have questions about
specifics in
this or things that you'd like to see in
a future video just let me know about in
the comments below i'll try to get back
to you as soon as i can or make a video
on that topic if there's enough people
asking for it
this is kind of the basics of how most
recursive looping programming is going
to work so understanding the sort of
concepts we covered here are going to be
super super important for your
programming
um and if you ever want to impress on
and they don't know that you wrote this
program just ask them to give you a
really hard sudoku and punching into
this and give them a solution back in
like 40 seconds so
hopefully you found that useful i hope
you found it fun i hope uh your python
programming journey is going well and if
you have found this or anything else on
the channel useful i really appreciate
it subscribe to the channel like on the
video it helps me out a ton helps me
continue making great content so thank
you all for your support and as always
thanks for watching and good luck with
your code thanks bye