Python Sudoku Solver Tutorial with Backtracking p.2 

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?

🤣🤣🤣🤣🤣🤣😂

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

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

Probably!

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'

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.

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.

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

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

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.

Ya maybe

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

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

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

'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

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

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.

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.