- 1 day ago
Transcript
00:00So for this, let's write recursive function.
00:02In the main function, I already have made Sudoku.
00:06How is it made?
00:07In a 2 by 2 matrix form.
00:09So we can see it directly and make Sudoku.
00:14How will my recursive function look like this?
00:16It will be a recursive function of public static boolean type.
00:18Because this function will tell your parent function
00:21if it has found out the solution or not.
00:25Let's give it a name as Sudoku Solver.
00:28In Sudoku Solver, I am going to pass my integer Sudoku.
00:36What will I pass on in the next one?
00:37I will pass on which row and which column.
00:42So i will be row and j will be column.
00:45In fact, I can write row here and column here.
00:49What is my work?
00:51I have two recursive functions.
00:53One is my base case.
00:54The other is my actual recursive function.
00:57My actual recursive function is that I will go to digits.
01:00Int digit is equal to 1.
01:03Until my digit value is less than or equal to 9.
01:07I will do digit plus plus.
01:08Every time I will place this digit to my cell number row, column.
01:18The next thing, I will place my number of columns.
01:20So that I will put the number of columns and so on.
01:21I will try to place this function.
01:22We will complete this function later.
01:24First, we will set up the basic recursive function.
01:27Let's set up to you.
01:28Does it need to raise rows and columns on Sudoku.
01:31This four parameters should be checked.
01:34If it is safe to put it, what do I do? First I will put it in place. I will
01:39place this digit in my Sudoku.
01:41I will assign this digit in row, column. Then I will call Sudoku solver for my Sudoku.
01:48The value of row will be plus 1. In fact, I have to calculate next row.
01:55How do we calculate next row? My int is next row.
01:58I am going to increase the previous row. My next column will be equal to column plus 1.
02:03What do I do every time? I will increase the same row in Sudoku.
02:10Every time I have to increase the column, I will keep the same row in the same row.
02:13When will I increase the row? When will I increase the row?
02:16When will I increase the value of my column plus 1 is equal to 9.
02:21I mean, I will go out of Sudoku. I will increase the same row in the same row.
02:27I will increase the next row in the same row.
02:30In this case, my next row will be equal to row plus 1.
02:34What will my column be? My next column will be equal to 0.
02:38Because I have to start with next row in the same row, I will start with 0.
02:41In this case, the next row will be equal to next row and next column.
02:51I will increase the next row in the same row.
02:51In this case, my column is equal to 1.
02:53In this case, my column is plus 1 in Sudoku.
02:54In this case, my next row is equal to 9.
02:56In this case, I will make the next row in row plus 1 and make the next column.
03:00I will create the next row in the same row.
03:05And my next column.
03:08So, I have called the call.
03:10Now, this function will be either true return or false return.
03:13If this function has true return,
03:16that means, solution exists.
03:20If the solution exists, I will return true here.
03:22And the solution will already exist in my integer 2D array.
03:27In Sudoku, I have placed digits on this level.
03:32I have placed digits on this level.
03:33In this level, I have placed digits on this level.
03:33In the next level, another digit will be placed on this level.
03:35In the next level, another digit will be placed on this level.
03:36So, the solution is already in Sudoku.
03:38Now, I will just return true.
03:40But if it has false return,
03:43then I will make this row, column again.
03:47What will I do?
03:48I will make it as 0.
03:50So, I will not place my element here.
03:53And these elements, when I have to place them?
03:56I will place them only when I have to place them.
03:58When I have to place my element already.
04:00Meaning, if my Sudoku is written here,
04:03then I will not add 8.
04:05If I have already written here,
04:07then I will not add 5.
04:08Then I will place new digits when I have to write 0.
04:12So, I will write the condition.
04:14If my Sudoku of row, column.
04:19If my Sudoku is not 0,
04:21then what will I do in this case?
04:22In this case, I will not do all this.
04:24In this case, I will place the call to the next level.
04:27I will place the call to the Sudoku Solver.
04:30For next row and next column.
04:36And this call to the other one,
04:38I will place the value as a return.
04:40If I have to return the true return,
04:42then I will return the false.
04:44So, I will return the false.
04:45This will be the condition for the already set elements.
04:48And this is the condition for the elements.
04:51I will place the digit to the new cells.
04:54If I have to get the answer,
04:56then the true return will happen.
04:57If I have to return the false.
05:00So we have written such basic codes for Sudoku solver. I have written these steps for recursion.
05:05There are two other things. One is my base case and one is my save function.
05:09When the base case comes? When the base case comes, when my row values are increasing and increasing.
05:15What will happen? The final row. It means 9 equals and my column values are increasing and 9 equals.
05:20In this case, my row values will be 9 and my column values will be 9.
05:27In this case, I will return true. Here I have the final solution here.
05:33If there is such a case, what is my row values? What is my row values?
05:36The row values are just 9. The column values are increasing.
05:40But if the row values are just 9, then I will return false.
05:44In this case, I have seen all the rows in Sudoku. Now I have come to the next row.
05:48Now the solution exists. Now I have written false.
05:52I have written false. This is my base case too.
05:54Now we will talk about recursion.
05:56I will check for any Sudoku cell.
05:59I will check whether it will be safe to place a digit on this cell or not.
06:03If I think that the cell will be safe to place it on this cell,
06:08then I will check the first column.
06:12I will check the second row.
06:14And the third thing I will check for my grid.
06:18I mean, for a grid of 3 by 3.
06:20First, let's write the condition of column.
06:23What is the condition of column?
06:24In the condition of column, my column number is constant.
06:28The row number is increasing.
06:30So my loop will go.
06:32For int i equals 0 to 8.
06:36Here I will traverse 9 rows.
06:38This row is 1, 2, 3, 4, 5.
06:41So here there is value.
06:42Here there is value.
06:43Here there is value.
06:43Here there is value.
06:43Here there is value.
06:44Here there is value.
06:44I have to go to 8.
06:46In this case, I have to go to 8.
06:46In some cases, Sudoku of i, column.
06:51Which is my fixed column.
06:53If its value is equal to digits.
06:54It is equal to 8.
06:55So, already the digit is placed.
06:57I will return false.
06:59In this case, if I want to check for row,
07:01I will traverse the column here.
07:05I will write for int j is equal to 0 to 8.
07:09Where I have 9 columns.
07:11If the digit exists already for row j,
07:17what is the case?
07:19I will return false.
07:22So, the condition of column is checked.
07:23If I want to check for row,
07:23it will be broken.
07:24Let's check them.
07:26Then we will discuss the grid.
07:27So, I will create a safe function.
07:31I will create a new function.
07:34Public static boolean type.
07:36If it is safe, then it will return true.
07:38If it is not true, then it will return false.
07:40We will name it is safe.
07:41In this case, I will have Sudoku and row and column.
07:46With this, I will have a digit.
07:48So, I will check this digit.
07:50I will place it safe.
07:52So, first of all, I will see the condition of column.
07:56For int i equals 0, i less than or equal to 8, i++.
08:10So, if I will return false.
08:15If I will return false.
08:17For int i equals 0, j equals 0, j equal to 8, j++.
08:23If already, if I can choose a Sudoku of row, j equal to 0, j into certain values.
08:31The value is equal to digit.
08:35In that case, I will return false.
08:38I will check the column and row.
08:40Now, I will check the third thing for grid.
08:43How will we check the grid?
08:44We will check the grid and see the grid.
08:53Let's talk about the grid. If I want to see this cell that will be the grid, then what will
08:59I do? I need to identify that this cell is in this 3x3, then I need to identify that this
09:15cell is in this 3x3.
09:18If I want to identify that cell, I need to identify that cell in which one cell, then I will
09:27remove the starting row and the starting column.
09:32If I have this cell, then it will be starting row and starting column.
09:37If I have this grid, then it will be starting row and starting column.
09:42If I have any row and any column, I need to remove the starting row and starting column.
09:53There is a particular way to remove it. The way to remove it is that my starting row is equal
09:59to row divided by 3 multiplied by 3 and starting column is equal to column divided by 3 multiplied by
10:073.
10:07If I want to divide by 3 and multiply by 3, then the answer is equal to 1.
10:19Why?
10:20Because it means row is equal to 3. When a division of row is equal to 3, then there will
10:27come from 4.
10:27If i want to divide by 3, then there will come from 1.
10:30If i want to divide by 3, then there will come from 3.
10:33And the one will always multiply by 3 by 3.
10:38So, it will not always come from row to equal, so you don't confuse it from this value to row
10:43or column.
10:43it will always be equal to the column, it will be different. How will it come? I will also see
10:46it.
10:47The basic principle of removing this thing is the basic principle. How will it come?
10:53How will it come? How will it come? How will it come?
10:56First of all, I have to identify that my 3x3 grid is where it lies.
11:03Does it lie in the row? Does it lie in the first section?
11:07Or does it lie in the second section?
11:10Or does it lie in the third section?
11:11It will lie in the third section.
11:12So which row?
11:13In the first section, in the second section, in the third section?
11:17What can I say?
11:18The row number is 0, 1, or 2.
11:22This is 0, this is 1, this is 2.
11:24If I divide them from 3, then it always comes to 0.
11:28The row number is 3, 4, and 5.
11:32If I divide them from 3, then it always comes to 1.
11:36The row number is 0.
11:37The row number in the third section has the row number.
11:40It always comes to 1, 2, and it's a term.
11:40The row number is 3, 7, 7, 8.
11:41When I divide it from 3, the row number also comes to 3.
11:47After I multiply it from 3 in 3 a moment again, the answer is 0, 3, and 3.
11:55The row number is 6.
11:57I have a little recap.
11:58How did I know that when I divide these 3 rows from 3, the answer is always 0.
12:05If I pick any row from 3, the answer is always 1.
12:10If I pick any row from 3, the answer is always 2.
12:15And when I multiply this 2 with 3, the answer is always 6.
12:19So from this division, I know that which part of my grid lies.
12:27If row divided by 3, there are 3 possible values.
12:321 can be 0, 1 can be 1, 1 can be 2.
12:35If this is 0, it means this part.
12:371 means this part.
12:392 means this part.
12:40Now we can identify column-wise.
12:43If column divided by 3, there are 3 possible values.
12:461 can be 0, 1, 1, 2.
12:48If 0 comes to this part.
12:501 comes to this part.
12:522 comes to this part.
12:53I know that for me, in any value, I will analyze this cell.
12:59I will analyze this cell.
13:00I will analyze this cell.
13:02For this cell, I have my row that is equal to 0, 1, 2, 3, 4.
13:09And my column is equal to 0, 1, 2, 3, 4, 5.
13:13So my row is 4 and column is 5.
13:16So what will be starting row?
13:18It will be starting row.
13:20It will be row divided by 3 multiplied by 3.
13:23Which is equal to 1 multiplied by 3, 3.
13:26So starting row will be 3.
13:27What will be starting column?
13:29Starting column is 5 divided by 3 multiplied by 3.
13:33That is equal to 3.
13:35So starting column is also equal to 3.
13:37So what can I say?
13:38The grid will be starting column and starting row.
13:42It will be 3 by 3.
13:44Where is the 3 by 3?
13:44Where is the 3 by 3?
13:45The 3 by 3 is here.
13:46So the starting column and starting row has been identified.
13:50So this cell has a grid.
13:52This cell has a grid.
13:54The starting row is 3.
13:56The starting column is 3.
13:58Let's take another example.
14:00Let's consider that I have to calculate this cell.
14:02I have to calculate this cell.
14:03For this cell, what do I have to do?
14:06What do I have to do?
14:06I have to do row 1, 2, 2.
14:08Or I will say this.
14:100 and 1.
14:111 is row.
14:12What do I have to do?
14:12Column number is?
14:130, 1, 2, 3, 4, 5, 6, 7.
14:16Column number is 7.
14:18What do I have to do?
14:19What do I have to do?
14:191 divided by 3 multiplied by 3.
14:22This value will be equal to 0.
14:24So starting row will be equal to 0.
14:27Now what do I have to do?
14:29What do I have to do?
14:29It will be equal to 7 divided by 3 multiplied by 3.
14:32This will be equal to 2 into 3.
14:34That is equal to 6.
14:35So my starting column will be equal to 6.
14:38Now if I have to identify 0, 6.
14:41So this is my row 0.
14:43This is my column 6.
14:44So this will be 0, 6.
14:47So what can I say?
14:48For this cell,
14:50the starting point of 3 by 3 will be 3 by 3.
14:53And what is the grid?
14:54The grid is this.
14:55The starting point will be plus 3.
14:58the column will be equal to you.
15:00Plus 3 and then the row will only be equal to 0.
15:02So this is my starting point of 3.
15:04So here,
15:04the column will lead to volume here.
15:06The next level.ma
15:07information is one which equals 9. So
15:09this is the starting point of post time. Then
15:10I have to call it plus 3. The
15:12total grid is to choose 5 , then
15:15I will doậm yeah? only
15:24have the total grid to those degrees.
15:25I know from row divided by 3 is the 0th, 1st or 2nd part
15:29Then multiply it by 3 and I start the starting point
15:32I know from column divided by 3 is the 0th part, 1st part, 2nd part
15:37Then multiply it by 3 and I know what is the actual number of column
15:43Let's write the code for grid wise calculation
15:45What do I need to do in the grid?
15:47First I start the starting row
15:49This is going to be equal to row divided by 3
15:53Multiply by 3
15:54Then start the starting column
15:56This is going to be equal to column divided by 3
15:59Multiply by 3
16:00This is going to be equal to column divided by 3
16:02Let's write the formula for the grid
16:04If my row starts from starting row
16:06And where do I go?
16:08I go to starting row plus 3
16:10I++
16:11Now I'm going to travel in 2D fashion
16:143 by 3 small grid
16:17Column wise, J's value will start starting column
16:19J less than starting column plus 3
16:24J++
16:25What did I say?
16:26I'm going to travel row wise here
16:28I'm going to travel column wise here
16:29This is the nested loop
16:32Which thing?
16:33To traverse 2D arrays
16:35What is my size of 2D array?
16:37What is my size of 3x3 grid
16:40It's a small grid
16:41So here
16:42If I get any point of this
16:45Sudoku of
16:46I, J
16:47But already my digit exists
16:51So I'll return here
16:52False
16:54So I've written a condition for column
16:55And row
16:56And now I've written a condition for grid
16:58And here
16:59False
17:00Not yet
17:01It means
17:01It's safe to place the row, column
17:04To the cell
17:05So I'll return the true
17:07So
17:08This is my
17:11Is the safe function
17:12This is my
17:13Sudoku solver function
17:15In which
17:17I've written my base case
17:20Recursions
17:22And with that
17:23I've completed this safe
17:24Now what I'll do
17:26With the main function
17:27Sudoku
17:27I've created a call
17:30Sudoku solver
17:32Sudoku solver
17:33Sudoku solver
17:33I'll pass my
17:34Sudoku
17:35With that
17:36I have to start from row number 0
17:37And column number 0
17:39If this value
17:41I have a true return
17:42In which case
17:43It will be true return
17:44I'll print it
17:46Solution
17:47Exists
17:48And now
17:49I'll print it
17:51Sudoku
17:52This
17:53For this
17:53To write a function
17:54And when
17:55This recursive function
17:57Me
17:57False
17:58Returns
17:59Sudoku solver
18:00I'll return
18:01In this case
18:02I'll print it
18:03Solution
18:05Does
18:06Not
18:06Exist
18:07Now
18:09Let's write a function
18:10Sudoku
18:11Public
18:12Static
18:13Void
18:13Print
18:14Sudoku
18:15I'll print it
18:30I'll print it
18:33I'll print it
18:45And
18:45Simple
18:46Finally
18:52Tap
18:52My 코�
18:52This
18:54Nich
18:55I'll check that
18:55The first
18:56Time
18:56It's十
18:56정도 Now
19:06Sudoku solver function is a boolean type, it means true return or false return, it means
19:11Sudoku passed, row passed, column passed, base case says that if your row value is 9, column
19:18also 9, in this case we will return true, but if the row value is 9, then I will return
19:26false, it means that there is no solution here, next row, by default row, next column
19:35is column plus 1, but at any point you know that column plus 1 value is 9, so next row
19:40I will return to row plus 1, next column I will initialize again with 0, so every time
19:46if my Sudoku of row comma column is 0, then I will return to next row and next column
19:55I will return to next row and next column, I will place digits from 1 to 9, I will check
20:02what is safe for Sudoku to place row, column per digit, so what did I do? I placed digits
20:09after that I checked that if the solution exists for the next level, if the solution exists,
20:15then I have returned to my solution, no, then I have placed 0 there again, and if there
20:22will not exist, so in this case I will return false, I will return to this save function
20:27on this save function, what did I have calculated? First of all, I checked the column
20:30that row wise, where my digit exists, if it exists, then I will return false, then row wise
20:37I checked the row wise, J is equal to 0, from 8 to 1 column, that my digit exists, if
20:43it exists,
20:44then I returned false, and what did I have done in grid? First of all, I have released initial
20:50starting row, starting column, every time I started starting row, I went to starting
20:56row plus 3, then starting column, I went to starting column, I went to starting column
21:00plus 3, and every time I checked if my digit exists here or not, what did I have done here?
21:06The mistake is that we need to change the case in the base case, if I think that row is
21:13equal to
21:149 and column is equal to 9, what will it be in the same way? Because if I take this
21:19Sudoku example, let me consider this Sudoku, let me find out, what did I have done?
21:25Our J value is equal to 8, I have added row, row is equal to 8, so in the beginning
21:33row is 9, and J is equal to J, and J is equal to 0, and J is equal to
21:410, this means that
21:42I have all the digits to find out, after this last cell, now I have this value to
21:49as I have this value, I have the final answer, but in this case, my row is 9, and J
21:56value
21:56will be equal to 0, and J value is 0, and J value is not, so 9 will never happen,
22:03because J
22:03row is equal to 9 and column is equal to 9 conditions will be false, after that row is equal
22:09to
22:099 conditions will be false, so that is what we have written in the base case, we have
22:19true, now we have the condition, and J value is equal to 0, so that I will return
22:26true. So we have a condition, as J value is equal to 0, and here I will go to the
22:34column
22:34value, and as I will write the value, when the column value is equal to 0,
22:38the mean that I have got the answer, so I will return true, now I have to change this
22:41As the value of row is 9, the value of column is 0.
22:45I will remove this condition because it will never come.
22:48So I will return true.
22:51Let's save it and run it.
22:55What happened?
22:56Now this solution exists and the whole Sudoku is printed.
22:59In fact, this column is equal to 0.
23:01I don't need to keep this condition.
23:03Because as my row of value is 9,
23:05my Sudoku will completely solve and I will get a solution.
23:08If I change the condition of column,
23:11then there will be a good solution.
23:13I have solved the same Sudoku.
23:15In fact, you can pause it and analyze it.
23:19Now this Sudoku solution is actually right.
23:22We can pick any element randomly.
23:25If I look for this 2,
23:27does this row exist or does it exist?
23:30Does it exist within the column?
23:33No.
23:33Does it exist within the grid?
23:36No.
23:36So these two are completely placed.
23:39For the right Sudoku solution,
23:41you can pick any element and analyze it.
23:44For row, column and grid.
23:47So this is how we have solved Sudoku solver.
23:51And what was the whole concept of backtracking?
23:54What did we learn about backtracking?
23:56The simple thing is that
23:57Backtracking is when we have to find many solutions.
24:00We have to find out any solutions.
24:01We can take any choice on every level.
24:04We can take any choice.
24:05We are growing up on a solution.
24:06And we realize that
24:08I don't get a solution here.
24:09So I go backtracking back.
24:12I change our choices.
24:14We call backtracking using recursion.
24:17In Sudoku questions,
24:19I have taken my choice
24:20that I have to write 4 digits on this cell.
24:22But later, I realized that
24:24there will be no final solution.
24:26So I have retraced my steps
24:28and backtracked.
24:29And now I can change my choice here.
24:32My choice was to place 4 on this cell.
24:35Now I can place 5 on this cell.
24:37In this case,
24:38I work with backtracking
24:40with the concept of backtracking.
24:41And backtracking
24:42we are using a lot more in the graphs.
24:44When we traverse the graphs
24:45from notes to notes,
24:48it will be very interesting
24:49the whole concept of backtracking.
24:51So we have done a lot of classical questions.
24:54And these questions are enough
24:55to build a strong understanding
24:58when it comes to backtracking.
25:00So let's take a look.