数独

随便写的解决数独问题程序

#include <iostream>
#include <cstring>
using namespace std;
const int N=100;
int map[N][N];
bool raw[N][N];
bool cal[N][N];
bool belong[N][N];
bool judge() {
    for(int i=0;i<9;i++) {
        for(int j=0;j<9;j++) {
            if(!map[i][j]) return false;
        }
    }
    return true;
}
bool dfs(int x,int y) {
    if(x>=9) {
        if(judge()) {
            for(int i=0;i<9;i++) {
                for(int j=0;j<9;j++) {
                    cout<<map[i][j]<<" ";
                }
                cout<<endl;
            }
        }
        cout<<endl;
        return true;
    }
    int y1=(y+1)%9;
    int x1=x+(y+1)/9;
    int b=3*(x/3)+y/3;
    if(map[x][y]) if(dfs(x1,y1)) return true;
    for(int i=1;i<=9;i++) {
        if(!map[x][y] && !belong[b][i] && !raw[x][i] && !cal[y][i]) {
            map[x][y]=i;
            belong[b][i]=true;
            raw[x][i]=true;
            cal[y][i]=true;
            if(dfs(x1,y1)) return true;
            map[x][y]=0;
            belong[b][i]=false;
            raw[x][i]=false;
            cal[y][i]=false;
        }
    }
    return false;
}
int main() {
    for(int i=0;i<9;i++) {
        for(int j=0;j<9;j++) {
            char c;
            cin>>c;
            if(c>='1' && c<='9') {
                map[i][j]=c-'0';
                raw[i][map[i][j]]=true;
                cal[j][map[i][j]]=true;
                belong[3*(i/3)+j/3][map[i][j]]=true;
            }
        }
    }
    dfs(0,0);
    return 0;
}