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.

Could you do one more episode of this where you make a gui of this

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.

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...

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

Thanks mate! Its fun to code these algorithms because i remember coding a maze algorithm with recursive algorithm and memories begin flashing my eyes.

8:34 Tim : to do this, it is actually very straightforward Me : oh okay Tim : we're gonna do it recursively Me : (°-° )

@langrock74

3 жыл бұрын

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.

@user-wc1sm8cj8s

3 жыл бұрын

LOL That got me

@theomichail9818

2 жыл бұрын

@@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

@ThatControlUser

Жыл бұрын

​@@theomichail9818here I am, a year later, could you please tell me more about how that would improve the speed os this algorithm?

@saisreekarsunku4140

8 ай бұрын

🤣🤣🤣🤣🤣🤣😂

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 !

@surajvijay1937

3 жыл бұрын

Ya he could have used x for rows and y for columns

Keep up the content bro, i'm learning a lot!

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!

i cannot express how legendary you are for these vids. thank you man

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.

Couldn’t wrap my head around 2D arrays until this, thanks 🙏🏽

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!

Its awesome to watch how easy things can be Easy if taught by great teachers, Hats off to you !!

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.

The explanation is very straightforward to the point where it is unbelievable!

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

Great set of training videos. Well done Tim

Thanks, it was so helpful I, ll go through each line of code and try to learn it. Good job sir

Thanks Tim! This helps me a lot to understand logic in coding

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 :)

Really helped. Would love to see more in the future

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.

Continually impressed by your videos ! Your explanation make coding simple. Keep up the good work

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 :')

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.

literally so well explained bro. Nice job

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 :)

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 :)

You helped me a lot to understand the recursion and baCKTRACKING! aWESOME VIDEO ! tHANK U BUDDY

super explanation and marvelous code you made it short i tried box with definingeach and every position in thew box array

love this one! good job bro

Great video, keep doing this kind of problem

Very impressive work here, Tim

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.

@Davidsito44

11 ай бұрын

Yeah! That was confusing and after running and debugging I found that is not necessary.

this is an amazing video! i hope you hit one million subscribers in the future

@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.

Thanks bro you explain it very well!!

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?

@TechWithTim

5 жыл бұрын

Probably!

Thank you bro, i have learnt a bunch of great and interesting thing from you.

Thanks 💓 . Please do more like this

Thanks for the video. Can you please make a series of hard problems of LeetCode

Pretty simple when you break it down like this!

fantastic video, very useful please make more projects!!!!!!!!!!!!

I really appreciate it !

Excellent & Elegant solution & code

You are the best ! Thanks a lot !!

So clear. Genius

It helped a lot. Thanks.

super bro,very good solution.

This is great!

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 :(

Amazing video very helpful

awesome teaching style.

You are Genius bro

Tim you could have mentioned about DFS similarity and have given some algo base too.

Superb one 👌

Thx for sharing!

5:33 3//3 is 1.

Good work! I will try to do this in C++, cause i dont know python :/

Thanks,Tim, your are a great inspiration to go to advanced python programming for us beginners.

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

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.

@TechWithTim

5 жыл бұрын

Ya you’re right, oversight on my part but really not an issue as we know the length of each is the same.

@delbandtaha5539

5 жыл бұрын

@@TechWithTim thanks again for taking the time to put this together. Keep up the great work.

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.

@sbalogh53

2 жыл бұрын

Yes. If you don't stop after finding a solution the backtracking method will find all others as well.

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???

thank bro very much

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

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.

function solve(bo) doesn't return the board.... how is the global variable 'board' being modified?

Thank You

Looks very good - now try do this in C++ using a stack :) :) :)

i like it thank u

The video is great, but I recommend you to read "clean code" book. It's a beautiful help to you and to us !

@merover99

4 жыл бұрын

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.

@HealthInspectorz

4 жыл бұрын

@@merover99 oh thats what i did. It makes it easier to read. I learned that in my days where i coded in python.

@jaylynnemuzik

3 жыл бұрын

Robert Martin or Jim Lewis ...which "clean code" book?

@Toga333T

3 жыл бұрын

@@jaylynnemuzik The uncle bob, Robert Martin

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.

@sarthak2482

Жыл бұрын

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'

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!

@hossumquat

2 жыл бұрын

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.

@khechog

2 жыл бұрын

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).

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)?

Have you tried solving larger grids? I.e. 16x16, 25x25, 36x36. They get more challenging as you recursive function call stack is limited.

@langrock74

3 жыл бұрын

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.

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.

I noticed that the algorithm only returns correct solutions with a certain number of entries to start with: if the sudoku board to solve has between 25 to 30 numbers to start with, it produce a correct solution, but if you pass a board with less than that it returns wrong solutions. Does anyone know why? Thanks for any reply and congrats for your channel man, love it!!!!

@cbt121314

4 жыл бұрын

I'm late but in case it helps someone else I'd make sure to change the line that says "for i in range(1,10)" to put the size of the rows u're using... like for an 8*8 sudoku that would be " for i in range(1,9)" to go through 8 columns and not 9

Could you make another video perhaps expanding on testing? Possibly a good sample size?

@TechWithTim

5 жыл бұрын

Ya maybe

@boicey

5 жыл бұрын

@@TechWithTim How easy would it be to take this program and generate a GUI for it allowing users to enter a puzzle rather than going through the code?

Fara tine aveam restanta asa ca iti multumesc uwu

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.

@big123lak

5 ай бұрын

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

@theauthenticdhamma

5 ай бұрын

@@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.

If you wanted to make a pygame gui would you have to convert this into a while loop?

I don't understand anything in this tutorial. how does the valid() function work, also what is pos[]?

good vid

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!

@vamsikrishna4960

4 жыл бұрын

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

@MP-zz9wr

4 жыл бұрын

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.

@henryash413

3 жыл бұрын

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).

@subigyashrestha4956

3 жыл бұрын

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...

@cheeyuanng853

3 жыл бұрын

@@MP-zz9wr 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.

10:48 find_empty returns none anyways, there is no need to write it.. or am I wrong??

@krishnans2006

4 жыл бұрын

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.

Hi @Tech With Tim, i really liked your video. But I still got a question: In my unsteranding the backtracking method is only used for each row. If we take a look in the first row 7 8 0 | 4 0 0 | 1 2 0 ==> we can find two possible solutions: 7 8 5 | 4 3 9 | 1 2 6 AND 7 8 5 | 4 9 3 | 1 2 6 We picked the first solution (which is obviously the right one) but we couldnt know. Does the code handle this possibilty and how? Thanks in advance.

@langrock74

3 жыл бұрын

Why is the first solution 'obviously' the correct one? You mean in the context of a particular Sudoku? The code tries essentially all possible combinations of valid numbers, which isn't the same as ALL numbers. If the code runs into a wall, it goes back and tries to fix a previous position and then progresses forward again until it hits another wall or finishes successfully.

what is pos[1] and pos[0] in the above code? Please explain. Thanky you!

@langrock74

3 жыл бұрын

'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.

@victoriae3253

2 жыл бұрын

@@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

Hi Tim, while backtracking we need to backtrack only on to those items whose value we had updated as part of the code execution and not goto the original ones. How is your code handling that part? I mean along the course of traversal how does the code know which are the original values and shouldn't be disturbed and which are the ones modified as part of the code execution?

@TechWithTim

5 жыл бұрын

It does do that. It works recursively by finding empty squares(in other words ones that were not apart of the original board) and only modifying those, it it finds that there is no valid option for the next empty square it will backtrack and change the value of the last modified square

@nagarajnms22

5 жыл бұрын

Tech With Tim so it does remember which was the last modified square?

@TechWithTim

5 жыл бұрын

Yes because of the recursive calls on the stack

@nagarajnms22

5 жыл бұрын

Tech With Tim yes got it. Thanks Tim!

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?

how does line 29 bo[row][col] = 0 execute if there is an if statement before it that is constantly being checked?

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?

and if we want a 2*2 sudoku game what changes do we need have?

nice video bro❤️ can i use backtrack algorithms to maze solover 🤔

@sakshamkulshrestha2415

4 жыл бұрын

i think that would rather have some path-finding algorithm, try A*.

@langrock74

3 жыл бұрын

Yes, that's what we did in high school in the dark ages of programming using Turbo Pascal ... those were the days. Blast from the past;-) It's a fun algorithm to implement. Here, you'd have four directions to try (N,E,S,W). After each move, you call the function again and pick one of the valid directions ... etc.

For the valid function, why did you divide and multiply the position by three? When you could have just used the positions as they were to begin with.

@hossumquat

2 жыл бұрын

It is integer division, so the remainder gets dropped, then multiply. So it essentially rounds the number off to a multiple of 3. So not quite back where it began.