[This post was poorly received so I've made some suggested edits to try to improve it for posterity. I hope it's helpful to anyone who finds it in the future!]
I have been trying to understand recursion/backtracking/DFS using a simple Sudoku example. I'm not really interested in the Sudoku example per se, so per suggestion I've minimized the example below to just a 2x2 sudoku board in order to just focus on the point that confuses me about recursion (thank you @MisterMiyagi for the suggestion).
In the code below, I have a helper function check_board which takes a 2x2 matrix and checks if any numbers repeat in its rows and columns (i.e., checks if the 2x2 sudoku entered is valid). Then the function solve_sudoku is what I understand to be a standard DFS/backtracking algorithm to solve the sudoku by picking the first empty position (represented by a 0), and trying both values 1 and 2 in it, recursively looking for a solution.
So with input [[0,0], [0,2]] the output should be [[[2,1],[1,2]], but I was receiving the output False.
@ThierryLathuille helped by noticing the problem in the code: after trying each possible descendant node (in this case, by trying both values 1, 2), I missed the "backtracking" step, and need to add a line resetting the value to 0, meaning that square in the matrix would be stuck in a 2 for all subsequent calls (or, in the original 9x9 example, stuck at a 9):
When you see that the last value you tried in a square can't lead to a valid solution, you try the next one, until you reach 9. At this point, you return and go back to incrementing the value in the previous square, but you current one still contains the value 9, so it is considered as non available for the next attempts.
You just have to put it back to its original value of 0 before returning:
Now here's where I'm still confused and the point of the question: I am trying to think about the recursion like a tree. Once one of the nodes has tried every value for a square and its descendant nodes have all come back False, doesn't it just report False back up to its parent? Why would anyone else look at that board with the 2 again?
If you can help with my understanding of recursion, I'd really appreciate it!
Edit: @ThierryLathuille answered the question again in a comment! Thanks so much!
Note that when calling your function recursively, you don't pass copies of the board, but only manipulate the same board everywhere. As your code worked, each time you explored a branch of the tree, all the squares you touched during the exploration were left with a non-zero value, so they were not considered as free any more.
I had the mistaken idea that whenever a function is called in recursion, it gets a new copy of all its variables to act on. Which of course it does, but not of the input! Another fix to the code would be to use Python's copy module with the line copy_board = copy.deepcopy(board) and operate on and return copy_board at each instantiation of the function, which is what I mistakenly thought Python always did in recursion.
Maybe this has something to do with pass by value versus pass by reference, and Python is pass by reference always? Any more discussion on the subject is still appreciated!
Here's the broken code with line that fixes it commented out:
def check_board(board: list):
for i in chars:
for j in chars:
for k in chars:
if k == j:
continue
if board[i][j] == board[i][k] and board[i][j] != 0:
return False
if board[j][i] == board[k][i] and board[j][i] != 0:
return False
return True
def solve_sudoku(board: list):
chars = range(2)
if not check_board(board):
return False
for i in chars:
for j in chars:
if board[i][j] == 0:
for a in chars:
board[i][j] = a+1
if solve_sudoku(board):
return solve_sudoku(board)
# uncommenting this next line fixes the algorithm
#board[i][j] = 0
return False
return board
board = [[0,0],[0,2]]
if __name__ == "__main__":
print(solve_sudoku(board))
Output:
False
When you see that the last value you tried in a square can't lead to a valid solution, you try the next one, until you reach 9. At this point, you return and go back to incrementing the value in the previous square, but your current one still contains the value 9, so it is considered as non available for the next attempts.
You just have to put it back to its original value of 0 before returning:
if board[3*a+c][3*b+d] == board[3*a+e][3*b+f] and board[3*a+c][3*b+d] != 0:
board[i][j] = 0
return False
Output:
[[4, 8, 6, 9, 1, 5, 7, 3, 2],
[7, 2, 5, 4, 6, 3, 1, 9, 8],
[3, 9, 1, 7, 8, 2, 4, 5, 6],
[5, 6, 4, 1, 9, 7, 2, 8, 3],
[9, 7, 3, 6, 2, 8, 5, 1, 4],
[8, 1, 2, 5, 3, 4, 6, 7, 9],
[2, 5, 7, 8, 4, 9, 3, 6, 1],
[1, 3, 8, 2, 5, 6, 9, 4, 7],
[6, 4, 9, 3, 7, 1, 8, 2, 5]]
which is the correct answer.
It takes a very long time to reach it, though (about 30 seconds or so...), as a lot of parts of your code, especially the checks for the existence of duplicates in rows/colums/blocks are very inefficient. Have a look at this question for ideas of efficient ways.