For anyone who is confused with the valid function (as I and many others were), wait until he creates the solve function and actually uses it. Then, it makes a lot more sense.
I watched this video last year over and over but couldnt get my head around it, I finally clicked to watch it again today determined to succeed, and satisfyingly, I did just that! Thanks Tim
I would start with implementing a solver using the method you would use when solving a sudoku by hand. You'd first look at fields for which there can only be a single valid number. Once you implement this, you can solve easy and medium-hard sudokus. After that, look again at what Tim is doing with the back-tracking algorithm and it may make more sense.
@@langrock74 Sorry to revive this a year later but what you're talking about is heuristics which would be the next step in making this even faster than what it is currently
When I came here I didn't know how to use backtracking really, and even less I know how to play Sudoku. Now I know both, after taking apart your code I can say it is brilliant example. Subscribed.
Confusing moment when I did understand how x/y is handled here. Damn that was painful to go through in the valid() function part! This is brillant! Thanks !
Really cool! I've been pondering over solving the sudoku solver problem for a long time and did not think of recursion as an option! Thanks for making this video...
Hi Tim, First, great job. I enjoyed the videos. It is easy to understand for beginners, short code. For fun I am doing a sudoku module, and yes, it does have more bells and whistles. But just the bactracking and my sudoku grid object takes about a hundred lines of python code more than yours. I do see one single problem with your solution: Your code can find if a grid has no solution or has a solution, but it does not figure out if the solution is unique. That is an important part of a puzzle. On the other hand, like you, I have a grid that I use to test. I found it randomly online, I cannot even tell you exactly where. But with that grid, your code is not as immediate. You can try it. In my machine (2017 laptop with i5 processor) it took 15 seconds to find a single solution. About half the time it took my code to find that it was the only solution. I post the matrix here. grid = np.array([ (6, 0, 0, 0, 0, 0, 0, 5, 1), (0, 0, 0, 3, 0, 0, 9, 0, 0), (0, 0, 8, 0, 0, 0, 0, 0, 0), (0, 4, 0, 7, 0, 0, 5, 0, 0), (0, 0, 0, 0, 9, 0, 8, 0, 0), (0, 0, 1, 8, 5, 0, 0, 3, 7), (5, 0, 2, 6, 0 ,0, 0, 0, 4), (3, 0, 0, 0, 0, 7, 0, 2, 9), (0, 0, 4, 0, 0, 0, 0, 0, 0) ]) Again, even with this comment, great job. Once you graduate, you should teach. You are good at it. Believe me, I am a college professor.
I did find bits confusing and poorly explained (lines 17-20 for example) but overall you explained the concept of backtracking pretty well and this gave me good insight into what it is. Thanks!
Really good tutorials! @2:20 isn't necessary, since we haven't written the selected number to the blank cell yet at this point. The code works with or without this second condition.
Spends a week trying to make a back tracking algo by myself* Finds this video, follows along, everything makes sense, and finishes a project in 20 minutes* Man I love programming :')
I came here to learn more about backtracking, and I did. I knew of the channel before, but now I'm a subscriber - please make more videos like this. Thank you!
hey tim, i got to say: your content is pretty awesome. i'm here from brazil learning a lot with your videos, dude. this video is from a some time ago but i keep following you every day. a great hug man
Love the code. Integer division great trick. Thanks for sharing! Inspired me to write my own and try for less than 100 lines before watching this seeing what you did!
Thanks a lot. The recursion bit was a bit hectic but this was a really good explanation especially for self-taught developers who don't know some of this concepts from a classroom.
@Tech With Tim your video is a good step by step guide but to truly distinguish yourself from the dozens other sites with a lot more content and more experienced teachers, you have to help answer the question "how can I come up with the same thought process that Tim did in his video". You are teaching what to think and do, but not how you came up with the what in the first place. What if you can draw a mindmap of your entire thought process without ever showing the code? The recursion step is perfect for some visual illustration, maybe starting with the last 3 numbers to be filled in, a trivial board state.
edit: im pretty sure I figured it out, this should help any beginners understand and answer anything not understood. its calling the functions wether they are true or not, so everytime we make it to if solve it basically goes into a new solve, but once we reach when valid is false it goes to a return false for solve, which ends the current solve then goes back to the last called solve function and continues to set it to 0 but then how does it recall solve from there, someone said it continues the loop so if the loop was at 5 originally it will set it to 0 and the for loop picks it back up, but this doesnt work if the loop is already at 9 it would just end, but it then could go back to previous one again until it find a loop it can continue , so the only way it would fail is if the starting loop ends up at a 9 and the next loop needed to be reset which shouldn't happen if it runs thru each one from 0 and only back tracks when needed and when it back tracks it starts at the number it left off and if it fails completely at 9 begins the previous function which can happen as many times as needed so only the very first number can only be changed 9 times and once its at the correct number it should never have to be changed as every other number would get changed first and run thru every possibility so theres no way for a false positive to cause a change, so every number except the first number can be reset from 0 multiple times and since its a sodoku puzzle its set with correct numbers so once you find a correct number in the beginning its impossible to fail
Thank you very much for the ideia and explanation, i did it java because i'm trying to be fluent that language and works spectular. Keep making good content :)
Fun fact. If you precede the backtracking algorithm by one that fills in all the 'obvious' choices, the fields for which there is only a single possible number, you can speed the code up by over a factor of 15 for 'hard' sudokus. This preconditioning algorithm will actually also solve 'easy' and 'medium' hard sudokus without the recursive backtracking algorithm. For those interested in coding a solver, start with that one instead of the back-tracking one.
The idea of backtracking is very clear and obvious, what is not clear and obvious at all is how that process is fulfilled by the presented form of recursion. Now I know that when you start thinking about recursion too much, your brain starts to hurt, however if someone could find a better way to explain how recursion is actually implementing backtracking here that would be really helpful. What is somewhat puzzling to me as well is why the output of the solve_sudoku() function is True or False, instead of simply the solution to the sudoku puzzle. A fun fact: adding a guess number counter and trying to solve an "extreme" level sudoku (from among levels: easy, medium, hard, expert and extreme), the code needed to make about 80 mil guesses and took about 7 minutes to solve. When I altered the initial board a bit to make the puzzle unsolvable, the number of guesses increased to 180 mil and the time required was 12 min.
ye im confused to, its calling the functions wether they are true or not, so everytime we make it to if solve it basically goes into a new solve, but once we reach when valid is false it goes to a return false for solve, which ends the current solve then goes back to the last called solve function and continues to set it to 0 but then how does it recall solve from there, this is the only way I can understand recursion but then leaves me wondering how solve restarts from there and if the functions just starts going backwards that doesnt make sense either
@@big123lak I wonder who is the actual author of the code. This same form of recursion to solve Sudoku appears in a number of tutorials, but is never properly explained. I would think if Tim himself actually came up with the code he should be able to explain what kind of thought-process led him to it, and then we would understand how the recursion works in this case better. However I do not think he is the actual author. Anyway, since no one of those geniuses out there offered any real explanation, I tried out Google's Bard and finally received an explanation that made it a lot clearer. Here is the relevant part of it: BARD: In essence, the recursion allows the function to explore different possibilities systematically, while backtracking ensures it can recover from incorrect guesses and try alternative paths until a valid solution is reached. QUESTION: I wonder whether you could provide a more detailed explanation of the last paragraph. The given code looks extremely simple yet what it is doing is rather complex, i.e. it somehow has to remember what guesses have been made so far at different single empty cells of the sudoku and it always has to determine how far back it needs to backtrack when it hits a dead end. Now, how this is happening is rather difficult to understand. BARD I'll provide a more detailed explanation of how the code remembers guesses and determines backtracking: 1. Recursion as Implicit Memory: Each recursive call of solve_sudoku(puzzle) represents a decision point. The function doesn't explicitly store guesses in a separate data structure. Instead, the nested nature of recursive calls implicitly stores the state of the puzzle and the guesses made so far. Each recursive call has its own local scope, along with its own version of puzzle. This means changes made to puzzle within a call don't affect previous calls. 2. Backtracking Through Function Returns: When a guess fails (either invalid or doesn't lead to a solution): The function returns False to the previous call, signaling a dead end. The previous call then backtracks by trying a different guess for the cell it was working on. This process repeats until a valid solution is found or all possibilities are exhausted. Illustrative Example: Imagine the function calls itself recursively three times: solve_sudoku(puzzle) solve_sudoku(puzzle) (within the first call) solve_sudoku(puzzle) (within the second call) If the third call encounters a dead end, it returns False to the second call. The second call then tries a different guess for its cell. If all guesses in the second call fail, it returns False to the first call, and so on. Remember: Backtracking is a depth-first search approach. It explores one path fully before backtracking and trying another. The recursive calls and their return values implicitly manage the search and backtracking process, eliminating the need for explicit memory structures. I thought what Google's AI produced here was remarkably good.
Vorturo, you are correct. There is no need to write "return None" in the function, since by default if there is no return statement, it returns None. However, it is a good coding practice is that you add a "return None" statement to the function if you are going to use that value. For example, if you are just calling a function to print text to the console, and you are not going to use the returned value from the function, there is no need for a return statement. But, if you are going to use the None value returned from a function, then it is recommended to add a return None statement. This is mainly for good code readability.
hmmm, i don’t think i can use this on my cv anymore, i was close to the solution by myself but i think this might have helped too much, curse your excellent explaining :(
Good stuff! The only thing that was not clear is why you used the len of the first row in the find_empty function. for j in range(len(bo[0])) You could have done this... for j in range(len(bo[i])) which would have made a little more sense. I know the length does not change from row to row.
I don't understand this part: 2:15 I don't understand why we put: "and pos[1] != i" can someone please help. I have no idea why we have to put this there at all.
Since you traverse the board in a particular order, then you can check if the board is full by checking only the bottom-right value. The solution you have now is O(n^2) where n is the length of the board for every call to solve, just to check if the board is full.
Just a question (I'm not sure if this is right). If we only check the bottom right value, we won't be able to get the coordinates of the first occurrence of an empty cell. So isn't it true that what he is doing (checking full length of board) has dual purpose of 1) checking if game is solved or not and 2) if it isn't solved, what is the position of '0'
I have read that book and I agree with you. The algorithm gets cleaner if, for example, you use "row" and "col" as variable names instead of i and j. But I really like the video. Good explanations.
Thank you Tim! I have a question though. In the script, we iterate over the number for a give "0" (any) and once it is legit, we go further. However, what I cannot quite get is how come python goes back to the previously assigned value (i) and changes it if the current loop over len(1, 10) is False. In other words: let's say that the current attempt to fill in "0" spot with value from the len() is not possible. How python goes back to the previously made decision and changes it (example: from 5 to 3)? You did not write the specific explanation to into the script. From what I saw I expected your code to run a backtracking algorithm to the current "0" position. But what I cannot understand (because there is no explanation in the script) is how it changes the previous one. If you can explain, it would be amazing! I should say that your explanation so far was perfect! (The only missing part is above)) Many thanks in advance!
It happens automatically with the magic of recursion. Every time you call solve() again, it creates a whole new variable space, so you can have different values in your variables from the parent instance. So each new call to solve() tries to fill in another cell. If we reach a dead-end where nothing will work, it returns false, which tells the parent call that it was a dead end and it has to try the next value. Each call of solve() has it's own value for find_empty(), which is the cell it is attempting to solve. That is how each call of solve() knows what cell to change back. You probably just need a more solid understanding of stacks and how they work and you'll likely understand what's happening.
In the solve(bo) function there is a for loop, so when it recursively returns to the same stack, we assign 0 to that value (bo[row][col] = 0) so that we can change it to another valid value using the for loop (range 1, 10).
so its kinda like recursion and inception, solve function would be ran inside itself until the last cell is filled or there are no more valid numbers, then it would return false and backtrack until it finds a valid number???
Could you explain: when solve function return false, and the bo[row][col] is reset to 0, how does the program know next try it should use a different number than what it was used before that did not pass the valid function? How does the program avoid trapping itself in a infinite loop without any solution at all? Thank you very much!
Before the program backtracks, it actually tries to solve further squares recursively. Therefore the square tried this time would be different from previous ones (not the same call for function solve). It would only be caught in a "loop" if that is the only empty square remaining, which would only happen if there is a fault with the actual puzzle.
I understood it this way as the row and column is inside the solve function they are different variables every time function gets called . Lets take an example suppose if we go on solving solve for 1st empty 2nd empty and reach 3rd empty where we cant find a value that so the solve function returns false it traces back to the if statement of 2nd empty where the row and col are that of the 2nd empty space and sets it to zero and the for loop continues form where it left off and so on...
@@mp-ng I don't quite see the recursion and the backtracking. for i in range(1,10): if valid(bo, i, (row, col)): bo[row][col] = i if solve(bo): return True bo[row][col] = 0 does the if statement calls solve(bo) instead of just checking if "solve(bo)'s boolean state is True? and when it calls solve, it goes into the next level of recursion? Edit: Looks like someone answered it below. Thanks.
'pos' is a tuple returned from the find_valid() function. Hence pos[0] is the first element and pos[1] is the first element of that tuple, referring to row and column indices.
@@langrock74 @Techwithtim I guess you mean find_empty function, pos[0] is the first element of what? is it the list of tuples returned from the find empty() function or what? please could you clarify, Also pos[1] assuming you have a tuple (2,6) do you mean pos[ 1 ] would be 2 please i would appreciate it if you could use an example
Nice algorithm, I like particularly how you just make the first spot and then make it recursive, really clever. Could this be implemented on making schools timetables? For classrooms, teachers and students?
I wrote all the code out along w you and it runs but doesn't give me a solved board, just a second starting board. Also getting "NameError: name 'bo' is not defined" now for the first print_board func which was working before. If I'm using Jupyter notebooks do I have to be careful what order I run the cells in?
is there a limit on how many times u can go back 14:00 line 29. To me there seems like there is a limit because we don't save the previous positions? Can someone plz help
what if i wanted to get a board from a csv file? how can i do it? will it still work? cause you just gave pre made board to the solver whereas i want to give the solver some other values like from a dataset or so.
@@langrock74 s=25 def alter(s): s += 6 return True alter(s) print(s) If I execute this program the value of variable "s" is not altering it is just printing 25. Please help me I understood the whole backtracking concept in this video but I can't understand this point.
@@HiVikas You are correct, it doesn't in this case, since the integer you assigned to 's' is not mutable. It is hence being passed by copy. 'board' is a list of lists and hence mutable. It is being passed into the function by reference, like a pointer.
Sorry but I'm new to python, I need some insights that will this code be useful to make a program quite similar to this; calcudoko? or can i somehow alter the code and make that program? P.S You're a LEGEND GUY Tim, an inspiration.
For the solve(bo) function, it is possible to indent the 'bo [row] [col] = 0' line equally as much as the 'return False' statement (outside of the for loop)?
Even more important to then precondition the board by iteratively filling in the fields with only a single valid solution before calling the recursive algorithm.
Hi Tim! Great video and very clean code. The given code will find the first valid solution. Challenge: how would we change the code to find all solutions. I've been wondering about this and I think what is necessary is to keep looping and backtracking until we've tried all values in each free cell, i.e. all counters have are at 9, instead of the first value that yields a valid board.
Hey Tim, are these pos[1] != i, pos[0]!=i, (i,j) != pos, absolutely required? I believe that this is going to false every time. Because the first condition, i.e. bo[pos[0]][i], bo[k][pos[1]], bo[i][j] will never evaluate to "num" for the candidate position to be filled. It is going to zero. This is one of the reason why the it is a candidate position to be filled, i.e. because it is zero. Is my understanding correct?
great video! may I ask why you used return False at the end of the solve() function? From the way I see it, it would work just fine without it still. Thanks
When I tried to run this code with a different sudoku puzzle I didn’t get the answer. Instead I was returned the same question I gave the program. Pls help
Why do I print out two boards that are identitical(unsolved) rather than one on the top being unsolved and the one at the bottom being solved? I used the exact code.
what is ` if bo[pos[0]][i] == num and pos[1] != i:` doing .is pos[0]][i] == 00,01,...08 and pos[1] != 1,idid not get it.canyou explain how it is looping every element
13:47 line 29, what I don't understand is why if I do not reset the current cell to zero (i.e. remove line 29 from the code), the code does not work? Anyone?
That’s because you set it to the attempted value, if it doesn’t work at that value when you recursively backtrack you need to reset it. So the next time it reaches that cell it tries all the possibilities again and isn’t already filled with a value that didn’t work previously.
@@TechWithTim Thanks for the prompt reply! But suppose I am filling up the first empty cell on the board now. And let's say the value '1' is valid. That would bring me to line 26, which will call the solve function again. This time, since the first empty cell was filled with '1', I am essentially trying to solve for the second empty cell. Suppose now the second empty cell is invalid for values '1' through '9'. That would bring me to line 31, which will return False to the (called-again) solve function of the first empty cell. That would bring me to line 29 to reset the first empty cell to '0'. And according to the flow of the code, that would cycle back to line 22 and try value '2' for the first empty cell. So then again, still trying to understand why I have to reset the first empty cell back to '0' since I'm going to cycle it through '2', and so on if need be.
@@winstonong9593 you cant use the first cell as an example. Try doing the process with 4 cells already filled in. You could in theory go back more than one cell in any backtrack. Later cells could go through the cycle of 1-9 an infinite amount of times. So you need to reset because lets say we are at a state in which 4 cells are filled and now we cannot find a value for the 5th cell. Following our backtrack and changing the value of cell 4 we cannot find anything past its current value that works. This means we now need to change cell 3, and reset both 4 and 5. So that when we find a value for 3 and continue we start trying 1-9 for cell 4 and 5 because now cell 3 is a different value from before. So we must check all values for the next cells again, hence why we reset them.
@@TechWithTim Thanks again for the prompt reply! I think I answered my own question while thinking about it in the shower :D I would prefer having the resetting to '0' (i.e. line 29) outside the for loop which cycles through '1' to '9'. The code works fine either way, but it makes more sense in my head if its outside the for loop :P Line 22: for i in range(1, 10): Line 23: if valid(bo, i, (row, col)): Line 24: bo[row][col] = i Line 25: Line 26: if solve(bo): Line 27: return True Line 28: Line 29: board[i][j] = 0 Line 30: Line 31: return False
What I'm really confused about is the valid function's and pos != i part. Why would we be concerned about this exception if we loop through it only once. I mean, once we confirm that the valid function returns True, we insert the number into our specified spot and then we call a brand new valid function where the 0 is in the next spot. Long story short, I deleted all three "and pos !=" statements from all three valid function's parts and am still getting the same solutions.
i had a question , why would it try next value while backtracking instead of the same one ? like if the solution is like 4567 and it backtracks to 6 what stops it from choosing 6 again ?
It’s kinda hard to understand at first, but it keeps track of the number it was at. Pretty much it starts at the very end and makes it way to the top. So let’s say 6 wasn’t the right digit 3 square later, well it goes back to that to the recursion it was in when it chose 6 and will try 7, since it was at 6 back then. Kinda hard to explain, but that’s how it works. Pretty much, it already knows whats gonna work and whats not.
Hey so I didn't understand the point of having (pos[1] != i), (pos[0] != i) and ((i,j) != pos) in the valid function so I removed them and my sudoku solver is working perfectly! Could anyone please explain in detail why did we keep (pos[1] != i), (pos[0] != i) and ((i,j) != pos) in the valid function? And why after removing it, my sudoku solver was working
We don’t want to check our initial position which is pos, what we want to do is check if any row or column has pos, but not the position that we’re currently at
For anyone who is confused with the valid function (as I and many others were), wait until he creates the solve function and actually uses it. Then, it makes a lot more sense.
I watched this video last year over and over but couldnt get my head around it, I finally clicked to watch it again today determined to succeed, and satisfyingly, I did just that! Thanks Tim
Beautiful. Simply put. This is the best video I ve found for Sudoku backtracking. Its also amazing how little space you need for the whole code.
8:34
Tim : to do this, it is actually very straightforward
Me : oh okay
Tim : we're gonna do it recursively
Me : (°-° )
I would start with implementing a solver using the method you would use when solving a sudoku by hand. You'd first look at fields for which there can only be a single valid number. Once you implement this, you can solve easy and medium-hard sudokus. After that, look again at what Tim is doing with the back-tracking algorithm and it may make more sense.
LOL That got me
@@langrock74 Sorry to revive this a year later but what you're talking about is heuristics which would be the next step in making this even faster than what it is currently
@@theomichail9818here I am, a year later, could you please tell me more about how that would improve the speed os this algorithm?
🤣🤣🤣🤣🤣🤣😂
When I came here I didn't know how to use backtracking really, and even less I know how to play Sudoku. Now I know both, after taking apart your code I can say it is brilliant example. Subscribed.
Confusing moment when I did understand how x/y is handled here. Damn that was painful to go through in the valid() function part!
This is brillant!
Thanks !
Ya he could have used x for rows and y for columns
Could you do one more episode of this where you make a gui of this
Really cool! I've been pondering over solving the sudoku solver problem for a long time and did not think of recursion as an option! Thanks for making this video...
Hi Tim,
First, great job. I enjoyed the videos. It is easy to understand for beginners, short code. For fun I am doing a sudoku module, and yes, it does have more bells and whistles. But just the bactracking and my sudoku grid object takes about a hundred lines of python code more than yours. I do see one single problem with your solution: Your code can find if a grid has no solution or has a solution, but it does not figure out if the solution is unique. That is an important part of a puzzle.
On the other hand, like you, I have a grid that I use to test. I found it randomly online, I cannot even tell you exactly where. But with that grid, your code is not as immediate. You can try it. In my machine (2017 laptop with i5 processor) it took 15 seconds to find a single solution. About half the time it took my code to find that it was the only solution. I post the matrix here.
grid = np.array([
(6, 0, 0, 0, 0, 0, 0, 5, 1),
(0, 0, 0, 3, 0, 0, 9, 0, 0),
(0, 0, 8, 0, 0, 0, 0, 0, 0),
(0, 4, 0, 7, 0, 0, 5, 0, 0),
(0, 0, 0, 0, 9, 0, 8, 0, 0),
(0, 0, 1, 8, 5, 0, 0, 3, 7),
(5, 0, 2, 6, 0 ,0, 0, 0, 4),
(3, 0, 0, 0, 0, 7, 0, 2, 9),
(0, 0, 4, 0, 0, 0, 0, 0, 0)
])
Again, even with this comment, great job. Once you graduate, you should teach. You are good at it. Believe me, I am a college professor.
I did find bits confusing and poorly explained (lines 17-20 for example) but overall you explained the concept of backtracking pretty well and this gave me good insight into what it is. Thanks!
Really good tutorials! @2:20 isn't necessary, since we haven't written the selected number to the blank cell yet at this point. The code works with or without this second condition.
Yeah! That was confusing and after running and debugging I found that is not necessary.
Dude one year have passed and i came back here to do this algorithm translating him do c# and damn this still pretty awesome. thank u a lot
Bro, you just saved my advanced programming homework, i had to do a board similar to sudoku and i didnt know how to do it, your video saved my life :)
Spends a week trying to make a back tracking algo by myself*
Finds this video, follows along, everything makes sense, and finishes a project in 20 minutes*
Man I love programming :')
i cannot express how legendary you are for these vids. thank you man
I came here to learn more about backtracking, and I did. I knew of the channel before, but now I'm a subscriber - please make more videos like this. Thank you!
Thanks mate! Its fun to code these algorithms because i remember coding a maze algorithm with recursive algorithm and memories begin flashing my eyes.
hey tim, i got to say: your content is pretty awesome. i'm here from brazil learning a lot with your videos, dude. this video is from a some time ago but i keep following you every day. a great hug man
Love the code. Integer division great trick. Thanks for sharing! Inspired me to write my own and try for less than 100 lines before watching this seeing what you did!
Keep up the content bro, i'm learning a lot!
Thanks a lot. The recursion bit was a bit hectic but this was a really good explanation especially for self-taught developers who don't know some of this concepts from a classroom.
super explanation and marvelous code you made it short i tried box with definingeach and every position in thew box array
Its awesome to watch how easy things can be Easy if taught by great teachers, Hats off to you !!
The explanation is very straightforward to the point where it is unbelievable!
Thank you Tim, it was so nice. I just want to say if you print out every part to see what happen, it was so understandable for me which is beginner.
@Tech With Tim your video is a good step by step guide but to truly distinguish yourself from the dozens other sites with a lot more content and more experienced teachers, you have to help answer the question "how can I come up with the same thought process that Tim did in his video". You are teaching what to think and do, but not how you came up with the what in the first place. What if you can draw a mindmap of your entire thought process without ever showing the code? The recursion step is perfect for some visual illustration, maybe starting with the last 3 numbers to be filled in, a trivial board state.
Couldn’t wrap my head around 2D arrays until this, thanks 🙏🏽
Pretty simple when you break it down like this!
Continually impressed by your videos ! Your explanation make coding simple. Keep up the good work
You helped me a lot to understand the recursion and baCKTRACKING! aWESOME VIDEO ! tHANK U BUDDY
5:33
3//3 is 1.
function solve(bo) doesn't return the board.... how is the global variable 'board' being modified?
edit: im pretty sure I figured it out, this should help any beginners understand and answer anything not understood. its calling the functions wether they are true or not, so everytime we make it to if solve it basically goes into a new solve, but once we reach when valid is false it goes to a return false for solve, which ends the current solve then goes back to the last called solve function and continues to set it to 0 but then how does it recall solve from there, someone said it continues the loop so if the loop was at 5 originally it will set it to 0 and the for loop picks it back up, but this doesnt work if the loop is already at 9 it would just end, but it then could go back to previous one again until it find a loop it can continue , so the only way it would fail is if the starting loop ends up at a 9 and the next loop needed to be reset which shouldn't happen if it runs thru each one from 0 and only back tracks when needed and when it back tracks it starts at the number it left off and if it fails completely at 9 begins the previous function which can happen as many times as needed so only the very first number can only be changed 9 times and once its at the correct number it should never have to be changed as every other number would get changed first and run thru every possibility so theres no way for a false positive to cause a change, so every number except the first number can be reset from 0 multiple times and since its a sodoku puzzle its set with correct numbers so once you find a correct number in the beginning its impossible to fail
Thanks, it was so helpful
I, ll go through each line of code and try to learn it. Good job sir
Thank you very much for the ideia and explanation, i did it java because i'm trying to be fluent that language and works spectular.
Keep making good content :)
this is an amazing video!
i hope you hit one million subscribers in the future
literally so well explained bro. Nice job
Fun fact. If you precede the backtracking algorithm by one that fills in all the 'obvious' choices, the fields for which there is only a single possible number, you can speed the code up by over a factor of 15 for 'hard' sudokus. This preconditioning algorithm will actually also solve 'easy' and 'medium' hard sudokus without the recursive backtracking algorithm. For those interested in coding a solver, start with that one instead of the back-tracking one.
Very impressive work here, Tim
Thank you bro, i have learnt a bunch of great and interesting thing from you.
Thanks Tim! This helps me a lot to understand logic in coding
Really helped. Would love to see more in the future
Great set of training videos. Well done Tim
The idea of backtracking is very clear and obvious, what is not clear and obvious at all is how that process is fulfilled by the presented form of recursion. Now I know that when you start thinking about recursion too much, your brain starts to hurt, however if someone could find a better way to explain how recursion is actually implementing backtracking here that would be really helpful. What is somewhat puzzling to me as well is why the output of the solve_sudoku() function is True or False, instead of simply the solution to the sudoku puzzle.
A fun fact: adding a guess number counter and trying to solve an "extreme" level sudoku (from among levels: easy, medium, hard, expert and extreme), the code needed to make about 80 mil guesses and took about 7 minutes to solve. When I altered the initial board a bit to make the puzzle unsolvable, the number of guesses increased to 180 mil and the time required was 12 min.
ye im confused to, its calling the functions wether they are true or not, so everytime we make it to if solve it basically goes into a new solve, but once we reach when valid is false it goes to a return false for solve, which ends the current solve then goes back to the last called solve function and continues to set it to 0 but then how does it recall solve from there, this is the only way I can understand recursion but then leaves me wondering how solve restarts from there and if the functions just starts going backwards that doesnt make sense either
@@big123lak I wonder who is the actual author of the code. This same form of recursion to solve Sudoku appears in a number of tutorials, but is never properly explained.
I would think if Tim himself actually came up with the code he should be able to explain what kind of thought-process led him to it, and then we would understand how the recursion works in this case better. However I do not think he is the actual author.
Anyway, since no one of those geniuses out there offered any real explanation, I tried out Google's Bard and finally received an explanation that made it a lot clearer. Here is the relevant part of it:
BARD:
In essence, the recursion allows the function to explore different possibilities systematically, while backtracking ensures it can recover from incorrect guesses and try alternative paths until a valid solution is reached.
QUESTION:
I wonder whether you could provide a more detailed explanation of the last paragraph. The given code looks extremely simple yet what it is doing is rather complex, i.e. it somehow has to remember what guesses have been made so far at different single empty cells of the sudoku and it always has to determine how far back it needs to backtrack when it hits a dead end. Now, how this is happening is rather difficult to understand.
BARD
I'll provide a more detailed explanation of how the code remembers guesses and determines backtracking:
1. Recursion as Implicit Memory:
Each recursive call of solve_sudoku(puzzle) represents a decision point.
The function doesn't explicitly store guesses in a separate data structure. Instead, the nested nature of recursive calls implicitly stores the state of the puzzle and the guesses made so far.
Each recursive call has its own local scope, along with its own version of puzzle. This means changes made to puzzle within a call don't affect previous calls.
2. Backtracking Through Function Returns:
When a guess fails (either invalid or doesn't lead to a solution):
The function returns False to the previous call, signaling a dead end.
The previous call then backtracks by trying a different guess for the cell it was working on.
This process repeats until a valid solution is found or all possibilities are exhausted.
Illustrative Example:
Imagine the function calls itself recursively three times:
solve_sudoku(puzzle)
solve_sudoku(puzzle) (within the first call)
solve_sudoku(puzzle) (within the second call)
If the third call encounters a dead end, it returns False to the second call.
The second call then tries a different guess for its cell.
If all guesses in the second call fail, it returns False to the first call, and so on.
Remember:
Backtracking is a depth-first search approach. It explores one path fully before backtracking and trying another.
The recursive calls and their return values implicitly manage the search and backtracking process, eliminating the need for explicit memory structures.
I thought what Google's AI produced here was remarkably good.
10:48 find_empty returns none anyways, there is no need to write it.. or am I wrong??
Vorturo, you are correct. There is no need to write "return None" in the function, since by default if there is no return statement, it returns None. However, it is a good coding practice is that you add a "return None" statement to the function if you are going to use that value. For example, if you are just calling a function to print text to the console, and you are not going to use the returned value from the function, there is no need for a return statement. But, if you are going to use the None value returned from a function, then it is recommended to add a return None statement. This is mainly for good code readability.
hmmm, i don’t think i can use this on my cv anymore, i was close to the solution by myself but i think this might have helped too much, curse your excellent explaining :(
Really like the video, just as I do all of your content! Would be cool to see a tutorial of something like a chess AI of you :)
Good stuff!
The only thing that was not clear is why you used the len of the first row in the find_empty function. for j in range(len(bo[0])) You could have done this... for j in range(len(bo[i])) which would have made a little more sense. I know the length does not change from row to row.
Ya you’re right, oversight on my part but really not an issue as we know the length of each is the same.
@@TechWithTim thanks again for taking the time to put this together. Keep up the great work.
I don't understand this part:
2:15 I don't understand why we put:
"and pos[1] != i" can someone please help. I have no idea why we have to put this there at all.
Excellent & Elegant solution & code
Thanks 💓 . Please do more like this
Since you traverse the board in a particular order, then you can check if the board is full by checking only the bottom-right value. The solution you have now is O(n^2) where n is the length of the board for every call to solve, just to check if the board is full.
Just a question (I'm not sure if this is right).
If we only check the bottom right value, we won't be able to get the coordinates of the first occurrence of an empty cell. So isn't it true that what he is doing (checking full length of board) has dual purpose of 1) checking if game is solved or not and 2) if it isn't solved, what is the position of '0'
The video is great, but I recommend you to read "clean code" book. It's a beautiful help to you and to us !
I have read that book and I agree with you. The algorithm gets cleaner if, for example, you use "row" and "col" as variable names instead of i and j. But I really like the video. Good explanations.
@@merover99 oh thats what i did. It makes it easier to read. I learned that in my days where i coded in python.
Robert Martin or Jim Lewis ...which "clean code" book?
@@jaylynnemuzik The uncle bob, Robert Martin
Thank you Tim! I have a question though. In the script, we iterate over the number for a give "0" (any) and once it is legit, we go further. However, what I cannot quite get is how come python goes back to the previously assigned value (i) and changes it if the current loop over len(1, 10) is False. In other words: let's say that the current attempt to fill in "0" spot with value from the len() is not possible. How python goes back to the previously made decision and changes it (example: from 5 to 3)? You did not write the specific explanation to into the script.
From what I saw I expected your code to run a backtracking algorithm to the current "0" position. But what I cannot understand (because there is no explanation in the script) is how it changes the previous one. If you can explain, it would be amazing!
I should say that your explanation so far was perfect! (The only missing part is above))
Many thanks in advance!
It happens automatically with the magic of recursion. Every time you call solve() again, it creates a whole new variable space, so you can have different values in your variables from the parent instance. So each new call to solve() tries to fill in another cell. If we reach a dead-end where nothing will work, it returns false, which tells the parent call that it was a dead end and it has to try the next value. Each call of solve() has it's own value for find_empty(), which is the cell it is attempting to solve. That is how each call of solve() knows what cell to change back. You probably just need a more solid understanding of stacks and how they work and you'll likely understand what's happening.
In the solve(bo) function there is a for loop, so when it recursively returns to the same stack, we assign 0 to that value (bo[row][col] = 0) so that we can change it to another valid value using the for loop (range 1, 10).
so its kinda like recursion and inception, solve function would be ran inside itself until the last cell is filled or there are no more valid numbers, then it would return false and backtrack until it finds a valid number???
Thanks bro you explain it very well!!
Could you explain: when solve function return false, and the bo[row][col] is reset to 0, how does the program know next try it should use a different number than what it was used before that did not pass the valid function? How does the program avoid trapping itself in a infinite loop without any solution at all? Thank you very much!
bo[row][col] = 0 is inside the for loop for iterating 1 to 10. So lets say 1 failed, then the for loop tries 2 to 10
Before the program backtracks, it actually tries to solve further squares recursively. Therefore the square tried this time would be different from previous ones (not the same call for function solve). It would only be caught in a "loop" if that is the only empty square remaining, which would only happen if there is a fault with the actual puzzle.
The for loop continues from where it left off.
If 5 didnt work and it has backtracked to this loop again, the loop will next try 6 (if 6 is valid).
I understood it this way as the row and column is inside the solve function they are different variables every time function gets called . Lets take an example suppose if we go on solving solve for 1st empty 2nd empty and reach 3rd empty where we cant find a value that so the solve function returns false it traces back to the if statement of 2nd empty where the row and col are that of the 2nd empty space and sets it to zero and the for loop continues form where it left off and so on...
@@mp-ng I don't quite see the recursion and the backtracking.
for i in range(1,10):
if valid(bo, i, (row, col)):
bo[row][col] = i
if solve(bo):
return True
bo[row][col] = 0
does the if statement calls solve(bo) instead of just checking if "solve(bo)'s boolean state is True? and when it calls solve, it goes into the next level of recursion?
Edit: Looks like someone answered it below. Thanks.
fantastic video, very useful please make more projects!!!!!!!!!!!!
So clear. Genius
love this one! good job bro
what is pos[1] and pos[0] in the above code? Please explain. Thanky you!
'pos' is a tuple returned from the find_valid() function. Hence pos[0] is the first element and pos[1] is the first element of that tuple, referring to row and column indices.
@@langrock74 @Techwithtim I guess you mean find_empty function,
pos[0] is the first element of what? is it the list of tuples returned from the find empty() function or what? please could you clarify,
Also pos[1] assuming you have a tuple (2,6) do you mean pos[ 1 ] would be 2
please i would appreciate it if you could use an example
awesome teaching style.
Nice algorithm, I like particularly how you just make the first spot and then make it recursive, really clever. Could this be implemented on making schools timetables? For classrooms, teachers and students?
Probably!
super bro,very good solution.
I don't understand anything in this tutorial. how does the valid() function work, also what is pos[]?
Looks very good - now try do this in C++ using a stack :) :) :)
Superb one 👌
I wrote all the code out along w you and it runs but doesn't give me a solved board, just a second starting board. Also getting "NameError: name 'bo' is not defined" now for the first print_board func which was working before. If I'm using Jupyter notebooks do I have to be careful what order I run the cells in?
Great video, keep doing this kind of problem
is there a limit on how many times u can go back 14:00 line 29. To me there seems like there is a limit because we don't save the previous positions? Can someone plz help
what if i wanted to get a board from a csv file? how can i do it? will it still work? cause you just gave pre made board to the solver whereas i want to give the solver some other values like from a dataset or so.
You are the best !
Thanks a lot !!
how the function "solve" is altering the values of the variable board when it has no access to it?
In Python, mutable arguments are passed by reference. The functions are hence accessing the elements of the 'board' variable and not a copy.
@@langrock74
s=25
def alter(s):
s += 6
return True
alter(s)
print(s)
If I execute this program the value of variable "s" is not altering it is just printing 25.
Please help me I understood the whole backtracking concept in this video but I can't understand this point.
@@HiVikas You are correct, it doesn't in this case, since the integer you assigned to 's' is not mutable. It is hence being passed by copy. 'board' is a list of lists and hence mutable. It is being passed into the function by reference, like a pointer.
@@langrock74 thank you...
Sorry but I'm new to python, I need some insights that will this code be useful to make a program quite similar to this; calcudoko? or can i somehow alter the code and make that program?
P.S You're a LEGEND GUY Tim, an inspiration.
For the solve(bo) function, it is possible to indent the 'bo [row] [col] = 0' line equally as much as the 'return False' statement (outside of the for loop)?
how does line 29 bo[row][col] = 0 execute if there is an if statement before it that is constantly being checked?
Tim you could have mentioned about DFS similarity and have given some algo base too.
Amazing video very helpful
Thanks,Tim, your are a great inspiration to go to advanced python programming for us beginners.
Have you tried solving larger grids? I.e. 16x16, 25x25, 36x36. They get more challenging as you recursive function call stack is limited.
Even more important to then precondition the board by iteratively filling in the fields with only a single valid solution before calling the recursive algorithm.
Thanks for the video.
Can you please make a series of hard problems of LeetCode
Hi Tim! Great video and very clean code. The given code will find the first valid solution. Challenge: how would we change the code to find all solutions. I've been wondering about this and I think what is necessary is to keep looping and backtracking until we've tried all values in each free cell, i.e. all counters have are at 9, instead of the first value that yields a valid board.
Yes. If you don't stop after finding a solution the backtracking method will find all others as well.
Good work! I will try to do this in C++, cause i dont know python :/
I really appreciate it !
It helped a lot. Thanks.
If you wanted to make a pygame gui would you have to convert this into a while loop?
Hey Tim, are these pos[1] != i, pos[0]!=i, (i,j) != pos, absolutely required? I believe that this is going to false every time. Because the first condition, i.e. bo[pos[0]][i], bo[k][pos[1]], bo[i][j] will never evaluate to "num" for the candidate position to be filled. It is going to zero. This is one of the reason why the it is a candidate position to be filled, i.e. because it is zero. Is my understanding correct?
great video! may I ask why you used return False at the end of the solve() function? From the way I see it, it would work just fine without it still. Thanks
When I tried to run this code with a different sudoku puzzle I didn’t get the answer. Instead I was returned the same question I gave the program. Pls help
you need to change something.
Perhaps in the "valid" function is missing the "return True" at the end
I've found myself with the same problem, did you ever find a solution?
@@danfox7920 I fixed it, I went the he's website and follow the code from there, in the video is messing a "return argument"
@@Jamb1991 Where? The website doesn't work
Hey Tim what if the board has more than one solutions? How to get that in python?
Why do I print out two boards that are identitical(unsolved) rather than one on the top being unsolved and the one at the bottom being solved? I used the exact code.
You are Genius bro
what is ` if bo[pos[0]][i] == num and pos[1] != i:` doing .is pos[0]][i] == 00,01,...08 and pos[1] != 1,idid not get it.canyou explain how it is looping every element
13:47 line 29, what I don't understand is why if I do not reset the current cell to zero (i.e. remove line 29 from the code), the code does not work? Anyone?
That’s because you set it to the attempted value, if it doesn’t work at that value when you recursively backtrack you need to reset it. So the next time it reaches that cell it tries all the possibilities again and isn’t already filled with a value that didn’t work previously.
@@TechWithTim Thanks for the prompt reply!
But suppose I am filling up the first empty cell on the board now. And let's say the value '1' is valid. That would bring me to line 26, which will call the solve function again. This time, since the first empty cell was filled with '1', I am essentially trying to solve for the second empty cell. Suppose now the second empty cell is invalid for values '1' through '9'. That would bring me to line 31, which will return False to the (called-again) solve function of the first empty cell. That would bring me to line 29 to reset the first empty cell to '0'. And according to the flow of the code, that would cycle back to line 22 and try value '2' for the first empty cell.
So then again, still trying to understand why I have to reset the first empty cell back to '0' since I'm going to cycle it through '2', and so on if need be.
@@winstonong9593 you cant use the first cell as an example. Try doing the process with 4 cells already filled in. You could in theory go back more than one cell in any backtrack. Later cells could go through the cycle of 1-9 an infinite amount of times. So you need to reset because lets say we are at a state in which 4 cells are filled and now we cannot find a value for the 5th cell. Following our backtrack and changing the value of cell 4 we cannot find anything past its current value that works. This means we now need to change cell 3, and reset both 4 and 5. So that when we find a value for 3 and continue we start trying 1-9 for cell 4 and 5 because now cell 3 is a different value from before. So we must check all values for the next cells again, hence why we reset them.
@@TechWithTim Thanks again for the prompt reply!
I think I answered my own question while thinking about it in the shower :D
I would prefer having the resetting to '0' (i.e. line 29) outside the for loop which cycles through '1' to '9'.
The code works fine either way, but it makes more sense in my head if its outside the for loop :P
Line 22: for i in range(1, 10):
Line 23: if valid(bo, i, (row, col)):
Line 24: bo[row][col] = i
Line 25:
Line 26: if solve(bo):
Line 27: return True
Line 28:
Line 29: board[i][j] = 0
Line 30:
Line 31: return False
This is great!
Thx for sharing!
Fara tine aveam restanta asa ca iti multumesc uwu
What I'm really confused about is the valid function's and pos != i part.
Why would we be concerned about this exception if we loop through it only once. I mean, once we confirm that the valid function returns True, we insert the number into our specified spot and then we call a brand new valid function where the 0 is in the next spot.
Long story short, I deleted all three "and pos !=" statements from all three valid function's parts and am still getting the same solutions.
i had a question , why would it try next value while backtracking instead of the same one ? like if the solution is like 4567 and it backtracks to 6 what stops it from choosing 6 again ?
It’s kinda hard to understand at first, but it keeps track of the number it was at. Pretty much it starts at the very end and makes it way to the top. So let’s say 6 wasn’t the right digit 3 square later, well it goes back to that to the recursion it was in when it chose 6 and will try 7, since it was at 6 back then. Kinda hard to explain, but that’s how it works.
Pretty much, it already knows whats gonna work and whats not.
Hey so I didn't understand the point of having (pos[1] != i), (pos[0] != i) and ((i,j) != pos) in the valid function so I removed them and my sudoku solver is working perfectly! Could anyone please explain in detail why did we keep (pos[1] != i), (pos[0] != i) and ((i,j) != pos) in the valid function? And why after removing it, my sudoku solver was working
We don’t want to check our initial position which is pos, what we want to do is check if any row or column has pos, but not the position that we’re currently at