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


def print_board(b):
    boardstr = ""
    for i in range(9):
        if i == 3 or i == 6:
            boardstr += "---------------------\n"
        for j in range(9):
            boardstr += str(b[i][j]) + " "
            if j == 8:
                boardstr += "\n"
            if j == 2 or j == 5:
                boardstr += "| "
    print(boardstr)

def solve_board(b):
    def is_valid_number(b, num, x, y):
        for i in range(9):
            if b[i][y] == num:
                return False
        for j in range(9):
            if b[x][j] == num:
                return False
        for i in range(3):
            for j in range(3):
                if b[(x // 3) * 3 + i][(y // 3) * 3 + j] == num:
                    return False
        return True

    def next_valid_position(b):
        for i in range(9):
            for j in range(9):
                if b[i][j] == 0:
                    return (i, j)
        return True

    def recursive_solve(b):
        if next_valid_position(b) == True:
            print("Board solved!\n")
            print_board(board)
            return True

        x, y = next_valid_position(b)

        for i in range(1, 10):
            if is_valid_number(b, i, x, y):
                board[x][y] = i
                recursive_solve(board)
        board[x][y] = 0
        return False

    recursive_solve(b)

print_board(board)
solve_board(board)