Welcome back, everyone.
In the last video, we figured out what the recursive function signature looks like for backtracking
in this video.
Let's actually start to apply it to solving the Sudoku problem.
The thing that we want to mention is that inside of our pseudocode, we know how to iterate through
the different numbers we have.
We know how to add a value to a 2D grid if we have the row in the column indexes.
What gets more challenging is the decision making step because we need to make sure we are able to capture
the constraints in a validity check here.
Let's think about what we know when it comes to the constraints we add of value into the grid cell that
we're looking at.
So let's say it's this zero five grid.
So we add a value here.
How do we determine if it's valid or not?
We need to check if there are any repeated values in the row and a repeated values in the column or
any repeated values in this little square.
So this means the three things we need to solve.
How do we keep track of what values are already in the row if we have the R value?
It's very easy for us to instantiate some type of rows data structure.
Maybe it's an array that holds hash maps and inside of the hash map it tells us whether or not we've
already seen that value.
So let's say, for example, we add in a three, then we can say that the three is equal to true and
all we would do is just check the rows for this corresponding index value.
So let's say this is zero.
Then we check the hash map and see if the actual value we just added already exists in it.
If it does, then we know that we're repeating ourselves.
If it doesn't, then we add it in and we can proceed on to the next one.
And as you can see inside of this rows array, there would just be a hash map for every corresponding
row inside of the board.
One would map to one to what map to two, three would map to three, et cetera, et cetera.
So we would do the exact same thing for columns, because we have a similar column index, so if we
had the exact same situation and we added it here, then we would just check at column index five inside
of our column data structure, we check out five, which would be down here, and we would see if the
value we just added already exists in the Hashmat.
If it doesn't, then we can proceed and we want to add it into this hash map and then do the next check,
which is for the actual box.
This is where it gets challenging because we still want to utilize this structure or something similar
in order to keep track of what values we've added into one of these boxes.
So here, what we want to do is we want to think about this structure.
If we're able to keep track of all of the values in each box, we need to figure out how we can capture
every box.
So what if we assigned a similar index to every single box so the values could be zero?
One, two, three, four, five, six, seven, eight.
If we were to do that, how do we get the corresponding values?
Well, let's break this down.
If we were to segment these long rows together, then what we see is that the indexes of the boxes,
zero to two, are in the first segment, zero one and two.
Three to five would be the next segment, three, four and five.
Six to eight would be the third segment six, seven, eight, so we need to figure out what values we
have to begin with.
We have a real value and we have a column value.
These are the index values.
We want to figure out how to combine them, to turn them into these corresponding indexes for these
boxes.
So let's logically break down what the row gives us and what the column gives us.
The row can tell us which segment we're in, whereas the column will tell us which of the actual boxes
in the segment we're in.
So how do we capture that?
Well, let's think about it like this.
If we were to treat each box in each segment as some index on its own, so let's say we look at the
indexes by themselves zero, one and two, regardless of what segment we're in, this left handed box
is index zero.
This middle box is index one.
This third box is index to.
Now, let's think mathematically, what do we need to add at every segment to zero one and two to give
us the correct index of the box in that segment?
When it comes to this first segment, it's going to be zero because these indexes already correspond
to the correct placement.
Zero plus zero gives us zero zero plus one, gives us one zero plus two, gives us two.
What about the next segment?
We want three to five.
So this means that three plus zero gives us zero three plus one, gives us four, three plus two gives
us five.
So three is the value that we need to represent from the row values three, four, five in order to
capture the correct segment.
Similarly for the last segment, what do we need to add?
We need six six plus zero gives us six six plus one, gives us seven six plus two gives us eight.
So we need to figure out how to transform the corresponding row values to their corresponding correct
base that we add similarly to the corresponding column index, transform to the column value that we
want to add and together they form the correct index.
So let's define this as a function.
We'll say that const get baulks ID because that's what we're getting is equal to a function that receives
the row and receives the column.
Now, let's think about how we can do that with the most basic one, which is going to be the column,
we can easily take whatever value we get and divide it by three and then round down even in our worst
case, six, seven, eight, eight divided by three is two point sixty six.
If we round down, then it's two.
So this gives us two.
Five divided by three is one point six seven.
Round it down is one two divided by three is zero point six of it rounded down is zero.
So then that means that the const column value that we need to add is equal to the column.
Flawed, divided by three.
And that gives us our column value.
What about the row value?
Well, here with the row value, what we notice is that each corresponding place is just triple the
value that we derived here.
So we're just going to do a very similar thing except multiply by three afterwards.
So we're going to say the row value is equal to math floor.
Of our row, divided by three, multiplied by three.
And then all we need to return to get the correct box index is just the column value plus the row value.
And that's it.
Now we know how to store the Rowe values, the column values and the box values for the corresponding
values that we add in every Griselle.
So my challenge to you is actually to try and coat out the actual solution.
You need to instantiate something that will keep track of the values in those rows and the columns and
the grid cells that we get to.
And you also need to figure out how to build out the board state following this general recursive pattern.
So try it out yourself and then we'll do it all together completely in the next video.