[数据结构与算法]数独游戏dfs

#include "bits/stdc++.h"
using namespace std;
char mp[15][15];
bool check(int x,int y,char k){
    for(int i=0;i<9;i++){
        if(mp[x][i]==k){
            return false;
        }
    }
    for(int i=0;i<9;i++){
        if(mp[i][y]==k){
            return false;
        }
    }
    for(int i=x/3*3;i<x/3*3+3;i++){
        for(int j=y/3*3;j<y/3*3+3;j++){
            if(mp[i][j]==k){
                return false;
            }
        }
    }
    return true;
}

bool dfs(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(mp[i][j]!='?') continue;
            else{
                for(char k='1';k<='9';k++){
                    if(check(i,j,k)){
                        mp[i][j]=k;
                        if (dfs())
                            return true;
                        else
                            mp[i][j]='?';
                    }
                }
                return false;
            }
        }
    }
    return true;
}
void print(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cout << mp[i][j]-'0';
            if(j!=8) cout << " ";
        }
        cout << endl;
    }
    cout << endl;
}
int main()
{
    while (cin >> mp[0][0])
    {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(i == 0 && j == 0) continue;
                else cin>> mp[i][j];
            }
        }
        dfs();
        print();
    }

    return 0;
}