Welcome back, everyone, let's tackle our Sudoku, solve our algorithm to begin with.
How do we recognize that this question needs backtracking as a solution?
This is where you need to think about the question, sometimes the question itself will give it away.
Other times you need to start thinking about how you could solution and realize that backtracking is
one of the possibilities.
And the way it works is that if you need to solve all the solutions or if you need to solve all the
valid solutions or even just solve for one valid solution, these are all different things that tell
you that backtracking could be a possible option for you.
The reason why this happens is when you need to generate all possible solutions, if all of the solutions
are not correct, meaning that looking at this Sudoku board, we could fill in these values with any
number we could fill them, even with the numbers, one to nine only.
But as long as we're not obeying all of these rules, then automatically we know that that solution
is absolutely incorrect and all the possible solutions involved with certain violations of rules should
not be contained.
So, for example, imagine that we placed a five here and from five on there are numerous other values
to fill.
However, whatever value you fill in for the rest of exploring, filling out this board, as long as
five is here, you are violating this constraint of needing unique values in a row because there are
two fives here.
So we can say that no matter what value you fill in these squares, as long as five is placed here,
this is going to be incorrect.
So from here, what you'll notice is that this is exactly what backtracking tries to do.
Backtracking says that if I place a value the moment that I realized that placing that value violates
one of these rules, I know that any possible solution that I fill in for the rest of this board is
automatically going to be incorrect.
So why even waste the resources generating out those options?
And that's exactly what backtracking helps us do.
It realizes that in order to solve the problem, we need to generate all of the possible solutions that
could exist.
However, some of those solutions, if not most of them, are going to be invalid.
If that's the case, I don't want to waste any resources generating those solutions.
I want to throw them away instead.
That's when you can tell that backtracking helps you out.
So the other thing about backtracking is that backtracking is a brute force solution.
What I mean by brute force solution is that a brute force solution is typically known as one that isn't
really finished.
There's no real algorithm here that makes it more efficient.
We are literally going to compute every possible option until we've computed one.
That's correct.
It's a brute force.
There's no optimizations here.
Yes, the throwing away of certain paths, you can consider an optimization.
But generally speaking, the main structure of the algorithm is that it wants to force all of the answers
through what you would consider just what you would logically do to solve the problem.
So by realizing it's a brute force algorithm, you can probably glean a lot of insights about how to
write and set up the algorithm by just thinking about how you would do this problem logically.
So to start Sudoku is a game that people have played for a really long time.
This means that you can easily play this game without the context of using a computer.
If we were to play this game, the way that you would start is you would pick a cell and you would fill
it out.
So you would say, OK, I know that I cannot repeat values in the row, in the column and in the square.
So I'm going to look inside of the square and find values I can use here.
The three, five, six, nine and eight are taken so I can use one, two, four and seven.
I'm going to start with the lowest volume, so one, and then I am going to make sure that I'm not violating
the row and that I'm not violating the column, I'm not.
OK, so let's move on to the next square inside of this square.
I see that I have one seven nine five, but I've already used one three, five and seven.
The next value that I could use is four.
So let me try and use four and put it inside of the square.
Then let's move on.
Here, I've already used one, three, five, four and seven.
So what I could put here is another value that I haven't seen yet, maybe two, two is the smallest
value, so I put two in because I'm not violating the ROE.
I'm not buying the column.
I'm also not violating the square.
When we look at this value now, what you'll notice is that the next smallest value we can put in,
that's not one, two, three, four, five is six.
So we know that six is one of the remaining values we have to put in, but six can go into any of these
three squares.
But regardless of where it goes, it's going to violate the rule about this three by three grid because
there's already a six here.
So automatically what we need to do is we need to back track back somewhere where we can change the
value.
So what we can do is we can go back to this value and put a six here instead.
From this point on, we can continue with filling out the rest of the values and what you'll notice
is that let's say we keep filling out the values and going down to the next row, filling out values.
If we get to this value and the only value we can put in here, we notice, is a one in order for it
not to violate the rules.
What you'll notice is that maybe we have to continue backtracking through more than just going back
one last value, we might have to keep going all the way back until possibly the very front, because
by the very nature of how the border state is currently, there's no possible way for one to be here.
What this means is that you might have to explore every possible number of combinations that we could
have had all the way back to this point.
This is a possibility, but backtracking doesn't care.
Backtracking says that's perfectly fine.
That's the way that I solve problems.
I am going to extensively try one value at a time.
And if I reach a point where I have to go back to see and that doesn't work, just keep going back,
keep going back and exploring options until we're able to proceed past this point.
That's backtracking and that's why it's based out of brute force.
So continuing from there, let's think about the next thing about backtracking, which is the fact that
it's a recursive based solution.
As we know with recursion, what we do is we want to recursively call the same function but proceed
along the path of solving the problem.
In our particular case, you can see solving the problem as if we're filling in these values according
to a traversal pattern.
Let's say the traversal pattern we pick goes left to right and then top down.
So it goes left to right, constantly trying to fill in the values inside of the grid cells.
So the first value we would fill in is the first one.
And what we're going to do is we're going to attempt every value from one to nine.
So the first thing we would do is try one.
So this would be our first function, call F of one.
I'm just going to keep the number here so you know what we're talking about.
We put in the one we see, does it duplicate in the row, no.
Does it duplicate in the column?
No.
Is it duplicated in the square?
No.
OK, so that's good.
We then move on to the next value in our traversal pattern here.
Once again, we want to try the one.
So this is where you would recursively call from within this original function call where we place the
one the next function call recursively for the value of of one.
We're going to try the one right here.
We place the one and then we check, OK, do we violate rules?
We do.
We have a one already in the row and we have a one in the square.
So this means that we want to pop off this F of one.
We want to finish hit a base case right here.
We broke one of the rules.
So we're going to exit and come back up to F of one.
So we're going to remove that value.
And then from F of one, we're going to try the next value, which is to say we're going to place the
two at once again.
We check our rules.
Do we violate our row?
No.
Do we violate our column?
No.
Do we violate our square?
No.
OK, so F of two is perfectly fine.
Then we keep on going to the next value.
So at this place, once again, we call F of one for this square.
We place the one and we check.
Are we violating rules?
Yes, we violate the row rule.
So we're going to once again pop this off and backtrack back up to the last previous valid state, which
was when we place the two.
From here, we're going to try another value, so we're going to place a two.
We're going to call off of two as the next recursive function call in this squares F of to call.
What we're going to see is that, OK, we place the two, do we violate the rules?
Yes, there's already a two in this row.
So once again, we backtrack, we end this call stack.
And we remove the value and then we try something else, we try three, so we call EVA three.
Then once again inside of here we do our check for constraints.
We see that we violate a rule.
Once again, we backtrack again.
We go back to the last valid state, which is evolve to.
And we try the next value, so we try for a four for does for violate the rules, No.
Four is perfectly valid.
So here we notice that it's OK, we continue.
And what you'll notice is that that's what we're going to do.
We're just going to keep reiterating the step in this recursive manner, one to nine, one to nine,
one to nine, one to nine going down this call stack.
But the moment we realized that we've gone through the values or there's a value that doesn't work,
then we go up the cost that if none of those values work, we go up the cost stack again.
We keep going up the call stack until we try all of the values in the next level that work.
And then from there, we can continue and continue.
And you can see how we're mimicking this extensive, extensive brute force process while utilizing the
recursion to keep track of where we can backtrack to.
This is how we utilize recursion to mimic our brute force solution that's incorporated backtracking.
So this is just the high level analysis of what backtracking is.
It's a combination of brute force and recursion.
In the next video, we're actually going to code it out.
So if this is even still a little confusing, don't worry, we'll code it out together and it will make
more sense.
So let's move on to the next video.