1 00:00:00,260 --> 00:00:02,300 Hey there and welcome back! 2 00:00:02,300 --> 00:00:09,290 We have already developed a good understanding of backtracking, and we have solved a lot of problems 3 00:00:09,290 --> 00:00:11,840 to solidify our learning. 4 00:00:11,840 --> 00:00:18,170 In this video, let's get started with a hard question which is called Sudoku Solver. 5 00:00:18,170 --> 00:00:23,960 And you will see that with the learning that you have already acquired, this question is going to be 6 00:00:23,960 --> 00:00:24,770 very easy. 7 00:00:24,770 --> 00:00:26,150 So let's get started. 8 00:00:26,150 --> 00:00:33,080 The question says write a program to solve a Sudoku puzzle by filling the empty cells. 9 00:00:33,290 --> 00:00:38,150 A Sudoku solution must satisfy all of the following rules. 10 00:00:38,240 --> 00:00:43,610 Each of the digits 1 to 9 must occur exactly once in each row. 11 00:00:43,880 --> 00:00:53,090 Each of the digits 1 to 9 must occur exactly once in each column, and each of the digits 1 to 9 must 12 00:00:53,090 --> 00:00:59,870 occur exactly once in each of the nine three into three sub boxes of the grid. 13 00:00:59,870 --> 00:01:03,440 The character dot indicates an empty cell. 14 00:01:03,440 --> 00:01:06,440 So this is the question and we are given an example. 15 00:01:06,440 --> 00:01:09,350 So let's say the board is over here. 16 00:01:09,350 --> 00:01:13,640 So notice that the board which is provided to us is a 2D array. 17 00:01:13,640 --> 00:01:16,280 And each row is an array. 18 00:01:16,280 --> 00:01:18,410 So you have five then you have three. 19 00:01:18,410 --> 00:01:20,300 Then you have ..7. 20 00:01:20,300 --> 00:01:23,240 So you have five three empty empty seven. 21 00:01:23,240 --> 00:01:25,190 And it goes on in this manner. 22 00:01:25,190 --> 00:01:29,390 Now we need to fill this Sudoku board over here. 23 00:01:29,390 --> 00:01:35,420 And when we fill this board the input array would change to what we have over here. 24 00:01:35,420 --> 00:01:41,300 Because notice there are no empty spaces or no dots in this 2D array. 25 00:01:41,300 --> 00:01:42,800 So this is the question. 26 00:01:42,800 --> 00:01:48,050 And again let's quickly try to go through the rules of the Sudoku puzzle. 27 00:01:48,050 --> 00:01:53,720 So it says each of the digits 1 to 9 must occur exactly once in each row. 28 00:01:53,720 --> 00:01:55,700 So for example this is a row. 29 00:01:55,790 --> 00:02:00,230 So notice that in this row you have each of the digits 1 to 9. 30 00:02:00,590 --> 00:02:02,990 So you have a one over here a two over here. 31 00:02:02,990 --> 00:02:07,340 Then you have 3456789. 32 00:02:07,340 --> 00:02:12,170 And notice that each of the numbers only occurs one time. 33 00:02:12,170 --> 00:02:17,600 Similarly, in each column you have the numbers from 1 to 9 occurring once. 34 00:02:17,600 --> 00:02:20,930 So for example in this column notice that you have a one. 35 00:02:20,930 --> 00:02:23,150 You have a two, you have a three. 36 00:02:23,150 --> 00:02:27,530 Then you have four, five, six, seven, eight and nine. 37 00:02:27,530 --> 00:02:30,920 And this is true for each box as well. 38 00:02:30,920 --> 00:02:34,730 So over here notice that this is a sub box. 39 00:02:35,640 --> 00:02:39,570 This is another sub box and this is another sub box. 40 00:02:39,570 --> 00:02:41,820 So if I were to draw it over here. 41 00:02:42,850 --> 00:02:50,590 Notice that this Sudoku board actually consists of nine sub boxes. 42 00:02:50,590 --> 00:02:55,000 So for example, this sub box is what we have over here. 43 00:02:55,210 --> 00:02:59,620 And each sub box consists of nine cells. 44 00:02:59,620 --> 00:03:08,080 So the third rule over here says that every digit from 1 to 9 must occur exactly once in each sub box. 45 00:03:08,080 --> 00:03:14,410 So for example in this sub box you have one, you have two, you have three, four, five, six, seven, 46 00:03:14,410 --> 00:03:15,310 eight and nine. 47 00:03:15,310 --> 00:03:18,280 And each digit occurs only once. 48 00:03:18,280 --> 00:03:23,500 So these are the three rules when it comes to the Sudoku puzzle. 49 00:03:23,590 --> 00:03:31,300 Now remember in coding interview questions, once you are presented with a question, it's always important 50 00:03:31,300 --> 00:03:37,600 to ask clarifying questions to ensure that you and the interviewer are on the same page. 51 00:03:37,600 --> 00:03:43,810 Now, a possible question that you could ask over here is what if there is no solution to the board 52 00:03:43,810 --> 00:03:45,010 which is given to us? 53 00:03:45,010 --> 00:03:50,890 Now, let's say the interviewer replies that it's guaranteed that there will be a solution. 54 00:03:51,420 --> 00:03:56,910 Now, another question could be can there be multiple solutions to the board which is given? 55 00:03:56,940 --> 00:04:03,810 Now let's say the interviewer says there is only one unique solution to the board that's given to you. 56 00:04:03,810 --> 00:04:10,380 Or let's say the interviewer could also say just find any solution in case there are multiple solutions. 57 00:04:10,380 --> 00:04:11,040 All right. 58 00:04:11,040 --> 00:04:18,090 So we have understood the question and we have clarified any questions that we wanted to ask and get 59 00:04:18,090 --> 00:04:19,410 clarifications on. 60 00:04:19,410 --> 00:04:23,760 So now we are ready to start solving this question. 61 00:04:23,760 --> 00:04:25,920 Let's do that in the next video.