• 1 day ago
Transcript
00:00Next question, which we will talk about is Sudoku Solver.
00:04We are going to solve a Sudoku.
00:06We have opened a newspaper in my childhood.
00:08I really liked Sudoku.
00:11In my childhood, I came home from the Times of India,
00:13so we would solve it.
00:14Sudoku shows something like this.
00:16I don't know Sudoku rules.
00:19In Sudoku, I have a grid of 9 by 9.
00:23There are many numbers.
00:26These numbers are always 1 to 9.
00:28You will see that you will not get a small number from 1,
00:31or you will not get a big number from 9.
00:33With this 9 by 9, there are also 3 by 3 grids.
00:38This is a 3 by 3 grid.
00:40This is also a 3 by 3 grid.
00:43This is a 3 by 3 grid.
00:45There are small grids and a big grid.
00:48I have a 9 by 9 grid.
00:50In which I have some numbers.
00:52Now I have to place numbers in this way.
00:54So I have to place that if I have some numbers here,
00:58if I have written here,
00:59if I have some numbers here,
01:01so that number will be going to be anywhere in the same row.
01:05The same column in that same column will be anywhere in the same column.
01:08The whole number will be here and here and here.
01:11And then the same grid will be here.
01:20It is like n-queens. This problem is like n-queens, like n-queens, there is rule that it should
01:29be vertically up, vertically diagonal and diagonally right.
01:34The rule is that it should not be the same row, same column and same grid.
01:40We should place queens here and place digits here.
01:44We will place one to nine to nine.
01:47I can give this example.
01:50If I want to place one here, I will not do it.
01:54Because one exists here in this row.
01:57I want to place two.
01:59I will place two.
02:00Because two doesn't exist in row, two doesn't exist here.
02:04And two doesn't exist in this grid.
02:07So, I have to analyze each cell for this cell.
02:12I will place which number in this cell.
02:14I will place my whole Sudoku recursively.
02:19Also, my question is that I will not find all the solutions in this cell.
02:23In this cell, I will check what my Sudoku can be solved or not.
02:28If it can be solved, then I will print one particular solution.
02:32I will not go to all the solutions.
02:34I need only a combination of Sudoku.
02:37I need a combination of Sudoku.
02:38In which I will solve the whole Sudoku.
02:39What will the approach of this solve?
02:40What will the approach of this solve?
02:41Now, I will know that in each cell, I will place the digits in each cell.
02:47So, I will place the choices in each cell.
02:50I will place the choice for each cell.
02:51I will place this cell.
02:52I will place the one.
02:52If I can add one.
02:54Can I add one?
02:55I can add one.
02:55Because one directly comes down.
02:57Then I will place the two.
02:59I will place two.
03:01Two comes in row, column, grid and column.
03:05Then I will place next cell.
03:08I will see if I can add 1 to this column or row or grid
03:16Then I will add 8 to this cell
03:22Next I will see if I can add 1 to this cell
03:25I will see if I can add 1 to this row and grid
03:31So 1 is not here
03:33So is it possible to add 2?
03:34Because 2 is already in this row
03:36Does it possible to add 3?
03:38This row is not in this row
03:40This column is also in this grid
03:43So this possible solution can add 3 here
03:47Now let's talk about 1 here
03:49Because 1 already has the same
03:512 also has the same
03:523 also has the same
03:533 also has the same
03:544 is not here
03:56Because this grid has already been in this grid
04:00Now let's see here 5 can come here, because 5 is already in this grid
04:066 can't come here because 6 is already in this column
04:117 is already in this column
04:14So what can 8 come here? 8 is in this row
04:19The possible solution is that I will write 9
04:21How do I write 9?
04:23It is not in this grid
04:24It is not in this column
04:26It is not in this row
04:27So I will write 9
04:30Now I will go to this cell
04:31I will see that 1 can come here
04:341 is not in this cell
04:342 is not in this row
04:373 is also in this row
04:394 is also in this row
04:405 is also in this cell
04:41I will write 6
04:436 is not in this row
04:466 is in this row
04:476 is in this grid
04:49I will write 6
05:096 is in this row
05:167 is in this row
05:197 is not in this column
05:207 is not in this row
05:217 is not in this row
05:227 is not in this row
05:25Now I will go to this cell
05:261 is also in this cell
05:282 is also in this cell
05:293 is also in this row
05:315 can come here
05:325 is also in this column
05:38So here I will write 5
05:40So I have what pattern observed
05:42That I am going to add 1 and 1
05:431 and 1 and 1
05:441 cell
05:45Which one?
05:46Row is equal to 1
05:47As I am going to add my cell number
05:50I will say row is equal to 0
05:52As I am going to add 1
05:54As I am going to the last cell
05:55I have placed here
05:57Now I am going to change row
06:00Row is equal to 1
06:02Now I will start here
06:05I will start here
06:06I will start here
06:07I will start here
06:09Let's talk about this
06:10In this grid
06:111 and 2
06:121 and 2
06:131 and 2
06:143 and 4
06:143 and 4
06:165 can come here
06:165 can come here
06:175 can come here
06:206 can come here
06:216 is not in this column
06:23Not in row
06:24And in this grid
06:25Not in this column
06:26So here I can click the 6
06:28Next
06:29This is placed
06:30This is placed
06:31This is placed
06:31select to the cell
06:32I will start on this cell
06:35Here I will see
06:361 can come here
06:36Have no
06:37because row and column
06:392 can come here
06:412 can come here
06:412 is already
06:42exists where the grid exists
06:43So it cannot come here
06:443 can come here
06:453 is already
06:45in this column
06:474 can come here
06:484 is already
06:50already in this grid
06:50can we talk about 5
06:53already in this grid
06:546 already in this column
06:597 already in this column
07:007 already in this grid
07:058
07:068
07:078
07:088
07:098
07:098
07:158
07:168
07:179
07:179
07:179
07:1710
07:2411
07:2912
07:3112
07:3212
07:3312
07:3312
07:3312
07:3912
07:3912
07:3912
07:4013
07:4114
07:4415
07:4415
07:4415
07:4415
07:4415
07:44I will place the digits in each cell. When I am going to increase in the last column?
07:49As I have placed the digits in the last column, then I will increase the row.
07:53Then I will increase the same column in row 1. Then I will increase the last column in row 1.
08:00What do I have to do in every cell? I have to check that for I is equal to 1
08:07to 9.
08:08Do I have to place any number? I have to check whether it is safe to place this number.
08:17If it is safe to place this number in Sudoku, then I will place it.
08:23Then I will call for next cell. Next cell will be placed where I have placed the next column.
08:30Then I will check whether I can solve Sudoku.
08:34When I am backtracked, if the solution exists further, then I will return true.
08:39As a function has returned true, I will also return true.
08:42This means that I have got my Sudoku solution.
08:45What do I have to do in my recursive function?
08:47I have to check until I is equal to 1 to 9.
08:50Do I have to place this digit in this particular cell?
08:58If it is safe to place this digit, then we will place it.
09:00We will place it in the next level.
09:01We will place it in the next level.
09:02We will place it in the next level.