how is this code working? backtracking and recursion

This is a working code that solves the sudoku:

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num:
            return False

    for i in range(9):
        if board[i][col] == num:
            return False

    box_row = (row - row % 3)
    box_col = (col - col % 3)

    for i in range(3):
        for j in range(3):
            if board[box_row + i][box_col + j] == num:
                return False
    return True

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1,10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        solve(board)
                        board[row][col] = 0

                return False

print(np.matrix(board))

solve(board)

The part that confuses me is:

if board[row][col] == 0:
    for num in range(1,10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            solve(board)
            board[row][col] = 0

    return False

how is this part working? I know it will assign the number, to the current row and col THEN, run the solve() function again, so, when will the program run this:

board[row][col] = 0

because as I understand it, the code won’t run unless there’s a 0 already. Then the program will check if the number is valid or not. also if there’s no num [1~9] that is valid, won’t it return false and quit the function?

talking about it makes my head spin, I know it’s even hard to explain, I googled it.

Edit:

this is the board I’m dealing with:

board_1 = [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0]
    ]

Output:

[[3 1 6 5 7 8 4 9 2]
 [5 2 9 1 3 4 7 6 8]
 [4 8 7 6 2 9 5 3 1]
 [2 6 3 4 1 5 9 8 7]
 [9 7 4 8 6 3 1 2 5]
 [8 5 1 7 9 2 6 4 3]
 [1 3 8 9 4 7 2 5 6]
 [6 9 2 3 5 1 8 7 4]
 [7 4 5 2 8 6 3 1 9]]

Answer

There are two cases where the solve function returns. I’ll rewrite the code to make it sweeter (but yours works too)*:

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1,10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        solve(board)
                        board[row][col] = 0

                return False
    return True

So, whenever the solve method reaches one of those return statements, it returns to the method that called it. Note that there are a two if-statements outside the call to solve. These can evaluate to False. And if they evaluate to False often enough, one of the return statements will be reached. That’s how you get to board[row][col] = 0

If you want to see the solved Sudoku, you have to repeat print(np.matrix(board)) after the call to solve at the very end too.


*Side notes:

  • As you wrote it, the solve method can return either None or False which is bad style because bool(None) evaluates to False too. Why does it return None? That’s because no return statement at the end of a function is equivalent to return None.
  • You could also just use return unless you need the True/False later. That’s because solve(board) is not assigned to anything.
  • If the Sudoku doesn’t have a solution, you’ll enter a convoluted infinite loop that will only end once the maximum recursion depth is reached (in CPython).