Implement A Sudoku Solver - Sudoku Solving Backtracking Algorithm ("Sudoku Solver" on LeetCode)
HTML-код
- Опубликовано: 30 июл 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement a Sudoku solver. (a classic Sudoku board is 9x9)
The Rules of Sudoku:
We are working with numbers 1 thorugh 9.
Each number can only appear once in a:
Row
Column
And one of the 3 x 3 subboxes
Approach 1 (Brute Force)
Try every possible assignment to empty entries and then at the end validate if the sudoku board is valid or not.
With no constraints, given a 9x9 board we have at max 81 spaces where in each space we can place the number 1-9 (but on a normal board many spaces will already have a number before we even start solving)
This means that there are 9^81 total arrangements of the board (as a loose upper bound). This is 1.9662705 * 10 ^ 77 boards just for a 9 x 9 board.
This would take too long.
Approach 2 (Apply The Constraints)
The backtracking approach.
We can traverse and place an entry in empty cells one by one.
We then check the whole board to see if it is still valid.
If it is we continue our recursion.
If it is not we do not even follow that path.
When all entries have been filled, we are finished.
The 3 Keys To Backtracking:
Our Choice
What we place in an empty cell that we see.
Our Constraints
Standard Sudoku constraints. We cannot make a placement that will break the board.
Our Goal
Place all empty spaces on the board. We will know we have done this when we have placed a valid value in the last cell in our search which programmatically will be the bottom right cell in the 2D matrix.
Validating Placements Before We Place Them
INSIGHT: We could traverse every row, column, and 3x3 subgrid to perform validation but at every decision point we know that we are adding onto a grid that is already valid.
So we just check the row, column, and subgrid of the item that has been added.
Whenever backtracking we know that every decision that we made stayed within the constraint that we started with being that the board was valid.
Complexities
Since Sudoku is traditionally 9x9 we can't really discuss complexities because nothing can scale.
Solving Sudoku generalized to n x n boards is a NP-Complete problem so we know for sure that our time complexity is exponential at the very least.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.9 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. 
Наука
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
Where is the code?? There is NO code in the description!
thank u so much!! but where's the code exactly?
very clear to illustrate the hard part of this problem. Great job man, you deserve more subs, and keep going!
thx
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?
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
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
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.
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.
What if in the middle of the grid validation check fails? What do you do then?
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
I love your videos. They are very helpful and you explain each problem clearly. Thanks
I love u
U aren't yelling this shows ur passion towards the problem don't change the tone
thanks haha
U R A LEGEND ! KEEP IT UP 💪
no u
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
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
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
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
Why you have two 9s in ROW number 3? Is that correct?
How i can apply vanilla backtracking on this problem for at-least 10 iterations
not sure
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...) ;)
Can some one point we to the link of the code ?
Loved it more when you are loud:) such energy is contagious!
Thanks a lot man, you're helping tons of people.
Hope you have a great day
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)
Hi Sri,I couldnt find your code in the description below.
The repository is deprecated - we only maintain backtobackswe.com now.
Wow.. brother thank you... You made this really easy
sure
Where can I find the code?
how do you learn all these difficult algos for yourself.....
I'm a student and I just use the internets.
Reading
Excuse me anyone please tell me where is the code
I can't see the coded solution in your description😢
Where i can find the code!! Not finding in description.
The repository is deprecated - we only maintain backtobackswe.com
1:04 Double "Our Choice" on screen ? :))
OOPSIE!
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
Code in the description?
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 RUclips thinks it sucks ass
I actually prefer the yelling and passionate approach. You’re the best!
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.
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.
Good job, but where's the code?
Great Explanation! Thank you Brother!
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
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.
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.
thank you very much sir, very helpful
bro you deserve million views and subscribers.thnk u!!
haha thanks
Hello, why filling in empty spaces is row by row ?
wym
Nice explanation, I find easier to understand the reasoning behind the approach
nice
love you man!!
u 2
Great Video,
Was just wondering where is the code...
thanks and the repository is deprecated - we only maintain backtobackswe.com now.
Man you are amazing!!
thanks - im normal
ruclips.net/video/rJ9NFK9s_mI/видео.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.
It's always safe to like your video at the very start.
lol
I can't find the codeee
Thank you guys this video helped me in my assignment
Thank you again
Where are you from guys?
maryland usa
Such a simpler and great explaination....and u are not yelling man😆....thanks it was very helpful...👍
thanks, ok, and great
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.
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.
Great! Thank you!
glad it helped
Where is the code link? I don’t see in description
Hi, the repository is deprecated - we only maintain backtobackswe.com now
This is the third succesful classic algorithm I learnt from you. Absolutely love your way of teaching ^_^
great and thanks
ruclips.net/video/rJ9NFK9s_mI/видео.html Valid Suduko (Explained like a champ)
where is the code??????????
depdeceted repo, no longer used
your explanation is best ,best teacher ever
thx
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.
Very clear.
Thanks for your wonderful explanation sir..
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 😀
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
I was interested in hearing about backtracking part which is not there in this video.
where's the code?
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 👌🏾
absolutely love the way you explain everything... has helped me a lot.
great!
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?
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
This is brilliant. Thank you!
sure
um hey where is the code??
The repository is deprecated - we only maintain backtobackswe.com now.
Can u have a code for tentaizu game
yes and yes
Where is the code?
The repository is deprecated - we only maintain backtobackswe.com
Where is the link to the code?
The respository is deprecated - we only maintain backtobackswe.com
Can u have a code for tenutio game
yes
I could not find the code.please help
THe repository is deprecated but stil on my gituhb
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
Thank you 😊😊😊 ben
sure
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
ruclips.net/video/rJ9NFK9s_mI/видео.html Valid Suduko (Explained like a champ)
Can u please provide the code?
The repository is deprecated - we only maintain backtobackswe.com now.
Go back to yelling please : )
Now - what about an algo which traverses every square and adds in the correct number only for those squares which have 1 possible entry. That loop runs continuously on the same grid until it stops making additions to the grid. At this point the grid is either solved or we use the recursive backtracking algorithm to produce the solved grid(s).
Would doing that be faster?
Ok. and not sure, that is an idea. it could come to a lock where no cells are single possibility so you'd have to prove the algorithm terminates.
Thanks for leetcode discuss 😇. Finally, found a great channel.
hahaha
why am i watching this im still doing intro c++ lol
hahahahahahahaha no idea
@@BackToBackSWE if you had to guess, what year of computing science is this?
@@bishwhat6554 I understand the intent of this question but I don't think it has an answer. It is...any year? You'd just understand this when you understand it? A 10 year old could understand this if they had proper precontext....it just happens that age brings such precontext.
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.
where is the code?
The repository is deprecated, it is on my github but no longer maintained
Where i find the code ??
All the codes are available here - backtobackswe.com/ 🎉
Where is the code in the description?
We maintain the code on backtobackswe.com
Bro..
Please be loud
Excited teacher is effective teacher. :)
co-pilot sent me here for some reason lmaoooo
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
Awesome explanation. Backtracking makes sense now. Thank you
great
Cute, but still hugely inefficient, and still unmanageably exponential in complexity. For instance, if the bottom right cell is forced, your program won't find out until it reaches that last cell, thus having to reject most solutions it found up til then.
:-(
ok