Hey there and welcome back!
We have already developed a good understanding of backtracking, and we have solved a lot of problems
to solidify our learning.
In this video, let's get started with a hard question which is called Sudoku Solver.
And you will see that with the learning that you have already acquired, this question is going to be
very easy.
So let's get started.
The question says write a program to solve a Sudoku puzzle by filling the empty cells.
A Sudoku solution must satisfy all of the following rules.
Each of the digits 1 to 9 must occur exactly once in each row.
Each of the digits 1 to 9 must occur exactly once in each column, and each of the digits 1 to 9 must
occur exactly once in each of the nine three into three sub boxes of the grid.
The character dot indicates an empty cell.
So this is the question and we are given an example.
So let's say the board is over here.
So notice that the board which is provided to us is a 2D array.
And each row is an array.
So you have five then you have three.
Then you have ..7.
So you have five three empty empty seven.
And it goes on in this manner.
Now we need to fill this Sudoku board over here.
And when we fill this board the input array would change to what we have over here.
Because notice there are no empty spaces or no dots in this 2D array.
So this is the question.
And again let's quickly try to go through the rules of the Sudoku puzzle.
So it says each of the digits 1 to 9 must occur exactly once in each row.
So for example this is a row.
So notice that in this row you have each of the digits 1 to 9.
So you have a one over here a two over here.
Then you have 3456789.
And notice that each of the numbers only occurs one time.
Similarly, in each column you have the numbers from 1 to 9 occurring once.
So for example in this column notice that you have a one.
You have a two, you have a three.
Then you have four, five, six, seven, eight and nine.
And this is true for each box as well.
So over here notice that this is a sub box.
This is another sub box and this is another sub box.
So if I were to draw it over here.
Notice that this Sudoku board actually consists of nine sub boxes.
So for example, this sub box is what we have over here.
And each sub box consists of nine cells.
So the third rule over here says that every digit from 1 to 9 must occur exactly once in each sub box.
So for example in this sub box you have one, you have two, you have three, four, five, six, seven,
eight and nine.
And each digit occurs only once.
So these are the three rules when it comes to the Sudoku puzzle.
Now remember in coding interview questions, once you are presented with a question, it's always important
to ask clarifying questions to ensure that you and the interviewer are on the same page.
Now, a possible question that you could ask over here is what if there is no solution to the board
which is given to us?
Now, let's say the interviewer replies that it's guaranteed that there will be a solution.
Now, another question could be can there be multiple solutions to the board which is given?
Now let's say the interviewer says there is only one unique solution to the board that's given to you.
Or let's say the interviewer could also say just find any solution in case there are multiple solutions.
All right.
So we have understood the question and we have clarified any questions that we wanted to ask and get
clarifications on.
So now we are ready to start solving this question.
Let's do that in the next video.