C++解数独运行时间的优化

Question

以下是我的代码

#include<iostream>
using namespace std;
int num[9][9];
bool flag = false;
void Input() {
    int i, j;
    char ch;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            cin >>ch;
            if(ch=='.') num[i][j]=0; 
            else num[i][j]=ch-'0';

        }
    }
}
bool Check(int n, int key) {
    int i, j;
    for (j = 0; j < 9; j++) {
        i = n / 9;
        if (num[i][j] == key) {
            return false;
        }
    }
    for (i = 0; i < 9; i++) {
        j = n % 9;
        if (num[i][j] == key) {
            return false;
        }
    }
    int x = n / 9 / 3 * 3;
    int y = n % 9 / 3 * 3;
    for (i = x; i < x + 3; i++) {
        for (j = y; j < y + 3; j++) {
            if (num[i][j] == key) {
                return false;
            }
        }
    }
    return true;
}

int DFS(int n) {
    if (n > 80) {
        flag = true;
        return 0;
    }
    if (num[n / 9][n % 9] != 0) { 
        DFS(n + 1);
    } 
    else {
        for (int i = 1; i <= 9; i++) {
            if (Check(n, i) == true) {
                num[n / 9][n % 9] = i;  
                DFS(n + 1);
                if (flag == true)
                    return 0;
                num[n / 9][n % 9] = 0;
            }
        }
    }
}

void Output() {
    cout << endl << "完成后的数独：" << endl;
    int i, j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            cout << num[i][j] << " ";
            if (j % 3 == 2) {
                cout << "  ";
            }
        }
        cout << endl;
        if (i % 3 == 2) {
            cout << endl;
        }
    }
}

void Output0(){
    cout << endl << "完成后的数独：" << endl;
    int i, j;
    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++) {
            cout << num[i][j];
        }
    }
}

int main() {
    cout<<"请输入0或1指定输出格式,0为机器格式，1为自定格式"<<endl;
    int x;
    while(cin>>x){
        if(x==0){
            cout << "请输入一个9*9的数独，空位用.表示：" << endl;
            Input();
            DFS(0);
            Output0();
            return 0;}
        if(x==1){
            cout << "请输入一个9*9的数独，空位用.表示：" << endl;
            Input();
            DFS(0);
            Output();
            return 0;}
    }
    return 0;
}

在计算一个较难的例子时运行了十几秒，请问能在哪里进行优化让时间减少吗