Table of Contents: The Problem Introduction 0:00 - 0:44 More Information On The Problem 0:44 - 1:52 The Brute Force Approach (Complete Search) 1:52 - 3:09 The Backtracking Approach (3 Keys To Backtracking) 3:09 - 3:30 Our Choice 3:30 - 4:18 Our Constraints 4:18 - 6:28 Our Goal 6:28 - 7:41 Time & Space Complexity 7:41 - 9:11 Conclusion 9:11 - 9:34 The code for this problem is in the description (with many comments for teaching purposes).
@@raghavkakar8092 here is the simplest solution using the approach from the video if you really need it - github.com/orishko-py/codewars/blob/master/sudoku-solver.py
I was hoping you would do a dry run on the example input board, just like you do for most of your other videos. That really helps in firming the understanding, more than the code.
What happen when the program has picked a number for a cell and later needs to change it due to other cells constrains? I mean it could be valid at the time it picks a number but may need to be changed later?
Yes, if that is the case that choice will take us down a path that will hit a "dead end". We will backtrack to the same decision point and make the next decision from that same cell into a new path of exploration.
Nice solution. I followed your approach but I did a bit of an update on it. Instead of checking everytime if a character can be placed in row or column or region at O(n^2) runtime, you can do that in constant time by saving keeping track of the content of each region, each row, and each column, then you can backtrack on it. after trying any character.
@@SunFoxPL1 It's still on his github though it is no longer maintained. The solution is also available on a variety of other websites. It makes sense that you should pay for new content (and it's much cheaper compared to other coding schools) since he is taking so much time to prepare and constantly update the materials when he could be working a SWE job and making a SWE salary. We should be thankful that he still has his original videos up.
@@mangekostorm9211 Oh I don't mind him getting money for what he is doing, just the fact that he posts video on youtube which is just half done (there is no code, and when someone asks about the code he just says that you need to go to the webpage and pay) is very unprofessional.
cannot believe it, I first search Sudoku Solver in youtube, I did not found your video. Then I watch other guys video which make me confused but I saw a leetcode link under that video comments. Then in the leetcode discuss, I saw your video link, that's how I found it.
One question I have is how we can figure out which valid value to use. For example, when we are looking at the second blank spot, you put a 2 there and proceed with the assumption that it is valid. However, how did you know that the second blank could not be a 6 instead. There are no 6's in that row, column, or sub-matrix?
When I place the 2 I just randomly choose that number, no methodology behind it. Check out the code in the description. What really happens is that we try numbers 1 to 9 using a for loop and if a placement ends up not working we backtrack and remove it from the board.
I don't understand whats all the dislike..what amazing explanation. he basically told you the approach. the coding part is easy. the check if can place part is basically the previous question ValidSudoku. I actually prefer this kind tutorial rather that just given me the code upfront.
yeees, I am not a better person but I love your energy and now I know how to solve and that makes me a better engineer. Thank you! And please don't change your style.
Hey mate, love your videos, but I have a question about the line 35: board[row][col] = EMPTY_ENTRY; why does it work with it and why doesn't it work without it? I mean, you set a value for a cell, and then you set it to EMPTY_ENTRY, why?
I got this same question in an interview, and the problem I faced was in checking if placing an element breaks a sub grid or not (It's relatively easy to check rows and columns). I believe that's the only important thing missing in this video. Otherwise I'm a huge fan of your channel ❤️
One of the problems I'd have with this is that the 1 at the start might not be the correct answer. The first empty cell could be 1,2 or 4. You don't know which it will be until you solved a certain number of the rest of the puzzle. I'm guessing the code keeps passing thru, but while you're there you could just find ALL the answers the position could be before you move on. I get that 1 has a 1 in 3 chance of being correct, but I'm not sure if that's the best approach.
@@BackToBackSWE I haven't written any code for Sudoku puzzles, but it seems that having info on what a given cell can and can't be, helps to eliminate other paths so that you don't have to do a full check. In other words, knowing that a given cell can only be 1,2,4 you can use that knowledge to reduce the number of checks in the 3 sections (horizontal, vertical, 3x3 local grid). That should narrow down what the other one can be. I'd have to run thru your code, but seems like it's not taking advantage of complete knowledge of all paths. In other words, if you have 6 paths and you reduce that to 3 paths, you cut the amount of time needed to find the final solution. Much like the "find the hidden word" puzzle. If you see "Applz" you don't have to check it again, you know it's not a word, it can't make a word, you can mark that branch as a dead end branch using DP. I'd have to write the code to see if it's any better or doing the same thing.
Nice video and great explanation. I have brought our course but all videos are not there, what I meant is that some videos that are there on youtube are not in the course. why so?
Hi! The intention is that some videos here are lower quality and don't explain the problem how I see it best explained. Also bad gear like microphone kept some videos out of the service as well tabled for a reshoot.
Being you answered all of the questions asked of you, I would like to know if I use a blank board how many different puzzles can I create? Your video is far beyond my comprehension so I will not say you are a poor teacher, but you are the first person to answer all of the questions on your site. I asked a relative that question (he had a doctors degree in math) and he did not or could not answer my question. I enjoy the puzzles but not as a math problem. For me that takes the fun out of the hobby.
How many different sudoku boards? Well, that's hard. The total invalid boards is 9*9*9*9*9*9*9*9*9*9*9...basically n^n which is 9^9 which is 387,420,489 boards. Valid boards? That is harder to count.
maybe? Technically I can only directly make videos requested by patrons but I'll consider it. (if someone sees this comment in 1-3 years and the Patreon doesn't exist ignore this)
Hey thanks for the vid! I was looking over the code and the comments really help make everything clear but the one thing I didn’t get was in the valid char placement method when you check if its a valid placement in the region, the formula for int I,J and topLeftOfRow,Col how did you derive those?
int regionSize = (int) Math.sqrt(board.length); // gives us the size of a sub-box In a 9 x 9 board, we will have 9 sub boxes (3 rows of 3 sub-boxes). int I = row / regionSize; int J = col / regionSize; The "I" tells us that we are in the Ith sub-box row. (there are 3 sub-box rows) The "J" tells us that we are in the Jth sub-box column. (there are 3 sub-box columns) Integer properties will truncate the decimal place so we just know the sub-box number we are in. int topLeftOfBlockRow = regionSize * I; // the row of the top left of the block int topLeftOfBlockCol = regionSize * J; // the column of the tol left of the block That multiplication takes us to the EXACT top left of the sub-box. We keep the (row, col) of these values because it is important. It lets us traverse the sub-box with our double for loop. Each coordinate we touch will be found by an offset from topLeftOfBlockRow and topLeftOfBlockCol. For 20 minutes I debated what to name these things and I literally couldn't think of a very clear name so left them alone. The fact you had to ask this means the code is too opaque. It is my fault and I will rename things to make things more clear.
Hey man, this was probably the best coding explanation, so glad I've found this video because I have the same problem waiting to be solved. The only difference is that the given board (also 9x9) is completely empty, no placement of any number whatsoever. Is there any change in the "choice" part? P.S. The code is not here anymore, any information on that? P.P.S. Keep it up, don't stop whatever you are doing!
Is there any change in the "choice" part? No P.S. The code is not here anymore, any information on that? The repository is deprecated - we only maintain backtobackswe.com. P.P.S. Keep it up, don't stop whatever you are doing! Thanks.
There is a problem man you said that you just need to check if our replacement doesn't break the board but sometimes it will happen that every single digit will break the board so from there we need to backtrack u didn't explain that part
That is a bit sad. I see a nice presentation, then jump to the description to see the code and find nothing but an ad for "service" with a "pricing" link ... Don't like that.
He didn't actually explain the backtracking, did he? What happens when you do break the board? vertices have multiple options and its very likely that you will break the board at some point.
you have not told how backtracking works in suduko solver. You should take a smaller board may be 4x4, place numbers then backtrack(This will explain the logic of backtracking)
This method of checking a value exists in the row, column or sub-board will not work. you have in the first row 5, 3, 1, 2, 7, and let's say you place 4 next so that will be 5, 3, 1, 2, 7, 4 so will not be able to place 6 in the top right board because 6 is already there. You mentioned backtracking but you didn't talk about. I am pretty sure backtracking can solve it
The funny thing about this problem is it is inherently a useless algorithm if solved with backtracking, though it is the acceptable solution for leetcode. If the top row is empty, but should be '987654321', you will max out the time complexity to where it takes horribly long to solve.
Table of Contents:
The Problem Introduction 0:00 - 0:44
More Information On The Problem 0:44 - 1:52
The Brute Force Approach (Complete Search) 1:52 - 3:09
The Backtracking Approach (3 Keys To Backtracking) 3:09 - 3:30
Our Choice 3:30 - 4:18
Our Constraints 4:18 - 6:28
Our Goal 6:28 - 7:41
Time & Space Complexity 7:41 - 9:11
Conclusion 9:11 - 9:34
The code for this problem is in the description (with many comments for teaching purposes).
Where is the code in the desc?
The repository is deprecated - we only maintain backtobackswe.com now.
Hello, why the filling in empty spaces is row by row ?
@@raghavkakar8092 here is the simplest solution using the approach from the video if you really need it - github.com/orishko-py/codewars/blob/master/sudoku-solver.py
Where the fuck is code in description?
Hey bro, you are not yelling. I can feel a strong passion from your voice!
Nah...I'm yelling haha
@@BackToBackSWE no you are not
thank u so much!! but where's the code exactly?
Where is the code?? There is NO code in the description!
I actually prefer the yelling and passionate approach. You’re the best!
I was hoping you would do a dry run on the example input board, just like you do for most of your other videos. That really helps in firming the understanding, more than the code.
yeah
What happen when the program has picked a number for a cell and later needs to change it due to other cells constrains? I mean it could be valid at the time it picks a number but may need to be changed later?
Yes, if that is the case that choice will take us down a path that will hit a "dead end". We will backtrack to the same decision point and make the next decision from that same cell into a new path of exploration.
@@BackToBackSWE How do I locate the number which caused the problem?
If you keep this up, as you started at the very young age at college, I am sure you will go very far. :)
I will haha, this is the next launch twitter.com/thebigoguide, then I'll be back to tend to this channel
Thanks a lot man, you're helping tons of people.
Hope you have a great day
U aren't yelling this shows ur passion towards the problem don't change the tone
thanks haha
Nice solution. I followed your approach but I did a bit of an update on it. Instead of checking everytime if a character can be placed in row or column or region at O(n^2) runtime, you can do that in constant time by saving keeping track of the content of each region, each row, and each column, then you can backtrack on it. after trying any character.
nice
very clear to illustrate the hard part of this problem. Great job man, you deserve more subs, and keep going!
thx
your explanation is best ,best teacher ever
thx
Hmmm, am I the only one who can't find the code? He said that in the description box there is a link to the code
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE So if we want to see the code we need to pay? That's... really ugly. I mean it's really ugly marketing move.
@@SunFoxPL1 It's still on his github though it is no longer maintained. The solution is also available on a variety of other websites. It makes sense that you should pay for new content (and it's much cheaper compared to other coding schools) since he is taking so much time to prepare and constantly update the materials when he could be working a SWE job and making a SWE salary. We should be thankful that he still has his original videos up.
@@mangekostorm9211 Oh I don't mind him getting money for what he is doing, just the fact that he posts video on youtube which is just half done (there is no code, and when someone asks about the code he just says that you need to go to the webpage and pay) is very unprofessional.
github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/SudokuSolver/SudokuSolver.java
I love your video. It's one half Sudoku tutorial and one half inspirational speech. Backtracking can solve many problems.
lmao, old video, apologies
@@BackToBackSWE Quality trumps age. (You know what I mean...) ;)
Great explanation. I've checked out a lot of your videos past few days. You are doing a great job. Wish my algorithms professor was like this.
thanks
cannot believe it, I first search Sudoku Solver in youtube, I did not found your video. Then I watch other guys video which make me confused but I saw a leetcode link under that video comments. Then in the leetcode discuss, I saw your video link, that's how I found it.
hahahahahaha, yeah, this channel is new and TH-cam thinks it sucks ass
Good job, but where's the code?
One question I have is how we can figure out which valid value to use. For example, when we are looking at the second blank spot, you put a 2 there and proceed with the assumption that it is valid. However, how did you know that the second blank could not be a 6 instead. There are no 6's in that row, column, or sub-matrix?
When I place the 2 I just randomly choose that number, no methodology behind it. Check out the code in the description. What really happens is that we try numbers 1 to 9 using a for loop and if a placement ends up not working we backtrack and remove it from the board.
bro you deserve million views and subscribers.thnk u!!
haha thanks
Loved it more when you are loud:) such energy is contagious!
3:50 row, column traversal
4:40 we cannot break the board (dont do an n^2 check)
6:30 how do i know im finished
It's always safe to like your video at the very start.
lol
I love your videos. They are very helpful and you explain each problem clearly. Thanks
I love u
This is the third succesful classic algorithm I learnt from you. Absolutely love your way of teaching ^_^
great and thanks
th-cam.com/video/rJ9NFK9s_mI/w-d-xo.html Valid Suduko (Explained like a champ)
When did you actually explain backtracking though...
dont remeber this vid
he didn't at all. kind of weird. i clearly see how to solve this problem from what he did say but only because of my background
What if in the middle of the grid validation check fails? What do you do then?
I don't understand whats all the dislike..what amazing explanation. he basically told you the approach. the coding part is easy. the check if can place part is basically the previous question ValidSudoku. I actually prefer this kind tutorial rather that just given me the code upfront.
Hahah, the video's quality is kinda bad.
Great Explanation! Thank you Brother!
How i can apply vanilla backtracking on this problem for at-least 10 iterations
not sure
I am addicted to your teaching style, I can watch your lecture whole day 😄
Can some one point we to the link of the code ?
yeees, I am not a better person but I love your energy and now I know how to solve and that makes me a better engineer. Thank you! And please don't change your style.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
U R A LEGEND ! KEEP IT UP 💪
no u
Hey mate, love your videos, but I have a question about the line 35:
board[row][col] = EMPTY_ENTRY;
why does it work with it and why doesn't it work without it? I mean, you set a value for a cell, and then you set it to EMPTY_ENTRY, why?
Imagine what is really happening. It doesn't matter if clear it or not. The cell gets overwritten.
Thanks for the great explanation and clean code.You made my day.
nah, you made my day for watching
Mr. Nobody provide code to me too
Excellent Explanation and it can be easily seen , the amount of effort you have done
thanks a lot for this video
sure
I got this same question in an interview, and the problem I faced was in checking if placing an element breaks a sub grid or not (It's relatively easy to check rows and columns). I believe that's the only important thing missing in this video. Otherwise I'm a huge fan of your channel ❤️
thx
It's not hard if row between 1 and 3 and column between 1 and 3 subsection 1 etc
I can't see the coded solution in your description😢
Such a simpler and great explaination....and u are not yelling man😆....thanks it was very helpful...👍
thanks, ok, and great
Wow.. brother thank you... You made this really easy
sure
Where i can find the code!! Not finding in description.
The repository is deprecated - we only maintain backtobackswe.com
how do you learn all these difficult algos for yourself.....
I'm a student and I just use the internets.
Reading
Thanks for your wonderful explanation sir..
Hi Sri,I couldnt find your code in the description below.
The repository is deprecated - we only maintain backtobackswe.com now.
Why you have two 9s in ROW number 3? Is that correct?
In the description box above I can't find the link of your code.
The repository is deprecated and we only maintain backtobackswe.com now.
Bro..
Please be loud
Excited teacher is effective teacher. :)
where is the code for this problem??
The repository is deprecated - we only maintain backtobackswe.com now
github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/SudokuSolver/SudokuSolver.java
Man you are amazing!!
thanks - im normal
th-cam.com/video/rJ9NFK9s_mI/w-d-xo.html Valid Suduko (Explained like a champ)
One of the problems I'd have with this is that the 1 at the start might not be the correct answer. The first empty cell could be 1,2 or 4. You don't know which it will be until you solved a certain number of the rest of the puzzle. I'm guessing the code keeps passing thru, but while you're there you could just find ALL the answers the position could be before you move on. I get that 1 has a 1 in 3 chance of being correct, but I'm not sure if that's the best approach.
The backtracking does that right? Makes a choice, goes deep into it, comes back if infeasible.
@@BackToBackSWE I haven't written any code for Sudoku puzzles, but it seems that having info on what a given cell can and can't be, helps to eliminate other paths so that you don't have to do a full check. In other words, knowing that a given cell can only be 1,2,4 you can use that knowledge to reduce the number of checks in the 3 sections (horizontal, vertical, 3x3 local grid). That should narrow down what the other one can be. I'd have to run thru your code, but seems like it's not taking advantage of complete knowledge of all paths. In other words, if you have 6 paths and you reduce that to 3 paths, you cut the amount of time needed to find the final solution. Much like the "find the hidden word" puzzle. If you see "Applz" you don't have to check it again, you know it's not a word, it can't make a word, you can mark that branch as a dead end branch using DP. I'd have to write the code to see if it's any better or doing the same thing.
Great Video,
Was just wondering where is the code...
thanks and the repository is deprecated - we only maintain backtobackswe.com now.
I could not find the code.please help
THe repository is deprecated but stil on my gituhb
Excuse me anyone please tell me where is the code
Thank you guys this video helped me in my assignment
Thank you again
Where are you from guys?
maryland usa
Hello, why filling in empty spaces is row by row ?
wym
Nice video and great explanation.
I have brought our course but all videos are not there, what I meant is that some videos that are there on youtube are not in the course. why so?
Hi! The intention is that some videos here are lower quality and don't explain the problem how I see it best explained. Also bad gear like microphone kept some videos out of the service as well tabled for a reshoot.
Where is the link to the code?
The respository is deprecated - we only maintain backtobackswe.com
Being you answered all of the questions asked of you, I would like to know if I use a blank board how many different puzzles can I create? Your video is far beyond my comprehension so I will not say you are a poor teacher, but you are the first person to answer all of the questions on your site. I asked a relative that question (he had a doctors degree in math) and he did not or could not answer my question. I enjoy the puzzles but not as a math problem. For me that takes the fun out of the hobby.
How many different sudoku boards? Well, that's hard.
The total invalid boards is 9*9*9*9*9*9*9*9*9*9*9...basically n^n which is 9^9 which is 387,420,489 boards.
Valid boards? That is harder to count.
@@BackToBackSWE Thank you Bro. I figured you would give me a good answer.
@@chetthejet3896 lol, I try
i cant get the code, i cant find the link, where is it? Please help.
The repository is deprecated - we only maintain backtobackswe.com.
I was interested in hearing about backtracking part which is not there in this video.
love you man!!
u 2
Nice explanation, I find easier to understand the reasoning behind the approach
nice
Thanks for leetcode discuss 😇. Finally, found a great channel.
hahaha
Can someone tell me where is the code I can't find it in the description
The repository is deprecated - we only maintain backtobackswe.com now.
Sorry i cant find your code could u give me the link to the code please？thank you ！
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE fuck you.
Code in the description?
Thanks for the video, it's good explanation. Can you make a video about 8 puzzle problems using backtracking, I really hope for it?
maybe? Technically I can only directly make videos requested by patrons but I'll consider it. (if someone sees this comment in 1-3 years and the Patreon doesn't exist ignore this)
Where can I find the code?
Where is the code link? I don’t see in description
Hi, the repository is deprecated - we only maintain backtobackswe.com now
Hey thanks for the vid! I was looking over the code and the comments really help make everything clear but the one thing I didn’t get was in the valid char placement method when you check if its a valid placement in the region, the formula for int I,J and topLeftOfRow,Col how did you derive those?
int regionSize = (int) Math.sqrt(board.length); // gives us the size of a sub-box
In a 9 x 9 board, we will have 9 sub boxes (3 rows of 3 sub-boxes).
int I = row / regionSize;
int J = col / regionSize;
The "I" tells us that we are in the Ith sub-box row. (there are 3 sub-box rows)
The "J" tells us that we are in the Jth sub-box column. (there are 3 sub-box columns)
Integer properties will truncate the decimal place so we just know the sub-box number we are in.
int topLeftOfBlockRow = regionSize * I; // the row of the top left of the block
int topLeftOfBlockCol = regionSize * J; // the column of the tol left of the block
That multiplication takes us to the EXACT top left of the sub-box. We keep the (row, col) of these values because it is important. It lets us traverse the sub-box with our double for loop.
Each coordinate we touch will be found by an offset from topLeftOfBlockRow and topLeftOfBlockCol.
For 20 minutes I debated what to name these things and I literally couldn't think of a very clear name so left them alone.
The fact you had to ask this means the code is too opaque. It is my fault and I will rename things to make things more clear.
Back To Back SWE no worries! Thanks for the explanation
absolutely love the way you explain everything... has helped me a lot.
great!
Hey man, this was probably the best coding explanation, so glad I've found this video because I have the same problem waiting to be solved.
The only difference is that the given board (also 9x9) is completely empty, no placement of any number whatsoever. Is there any change in the "choice" part?
P.S. The code is not here anymore, any information on that?
P.P.S. Keep it up, don't stop whatever you are doing!
Is there any change in the "choice" part?
No
P.S. The code is not here anymore, any information on that?
The repository is deprecated - we only maintain backtobackswe.com.
P.P.S. Keep it up, don't stop whatever you are doing!
Thanks.
@@BackToBackSWE It would be helpful if you put note about the deprecated repo in the description. But thanks for the video though 👌🏾
um hey where is the code??
The repository is deprecated - we only maintain backtobackswe.com now.
I can't find the codeee
There is a problem man you said that you just need to check if our replacement doesn't break the board but sometimes it will happen that every single digit will break the board so from there we need to backtrack u didn't explain that part
ok
th-cam.com/video/rJ9NFK9s_mI/w-d-xo.html Valid Suduko (Explained like a champ)
Can u please provide the code?
The repository is deprecated - we only maintain backtobackswe.com now.
That is a bit sad. I see a nice presentation, then jump to the description to see the code and find nothing but an ad for "service" with a "pricing" link ... Don't like that.
co-pilot sent me here for some reason lmaoooo
where is the code?
The repository is deprecated, it is on my github but no longer maintained
1:04 Double "Our Choice" on screen ? :))
OOPSIE!
This video is much better. I like the toned down style. Good job.
I like toned down too :)
Where is the code in the description?
We maintain the code on backtobackswe.com
He didn't actually explain the backtracking, did he? What happens when you do break the board? vertices have multiple options and its very likely that you will break the board at some point.
you have not told how backtracking works in suduko solver. You should take a smaller board may be 4x4, place numbers then backtrack(This will explain the logic of backtracking)
yo I dont see the code in the description
anyways nice video :)
The repository is deprecated - we only maintain backtobackswe.com now. and thx
@@BackToBackSWE how can i get the code if that's possible?
thank you very much sir, very helpful
Great! Thank you!
glad it helped
Is this solution supposed to be working for any Sudoku Grid?
Besides that - this is great channel - I am just preparing for the coding interview at Facebook, as a VR dev- and you're helping me a lot! Thanks!!!
Yes, it can easily be generalized to any Sudoku grid (forgot the exact dimensions though).
Nice, sure no problem.
Where i find the code ??
All the codes are available here - backtobackswe.com/ 🎉
This method of checking a value exists in the row, column or sub-board will not work. you have in the first row 5, 3, 1, 2, 7, and let's say you place 4 next so that will be 5, 3, 1, 2, 7, 4 so will not be able to place 6 in the top right board because 6 is already there. You mentioned backtracking but you didn't talk about. I am pretty sure backtracking can solve it
Thanks for sharing
Can u have a code for tenutio game
yes
Thank you 😊😊😊 ben
sure
Where's the code?
The repository is deprecated and no longer maintained. It is still on my github though
Please can you share it so I have a look?
Hey bro thank you for your video. I couldn't get the code to look at how it was implemented
It is on my github but the repsoitory is deprecated
Back To Back SWE ok thank you.
The funny thing about this problem is it is inherently a useless algorithm if solved with backtracking, though it is the acceptable solution for leetcode.
If the top row is empty, but should be '987654321', you will max out the time complexity to where it takes horribly long to solve.
ye
inspiring ! (you compelled me to comment :)
nice
i love this man so goddamn much holy shit
no u
why? he left out the most important part of the algorithm and then pulled the code. he's trash.
Very clear.
The board is invalid from the beginning :D