TIOJ 1025 數獨問題 ( 96校內賽 prob 2 )

poao899    -8K    122MS    G++     0.92K     2009-11-13 22:38:26                                   .



感謝小可魚>//////////<


唔暴力DFS也沒有特別剪枝


絕對是因為忘了數獨怎麼拼才取這種變數名稱(?

//*************************

#include<stdio.h>
int surwdkgo[9][9],cnt;
void dfs(int i,int j){
    int ni=i,nj=j;
    if(ni==8&&nj==8){
        cnt++;
        for(int p=0;p<9;p++)
            for(int q=0;q<9;q++,putchar(q==9?'\n':32))
                printf("%d",surwdkgo[p][q]);
        puts("");
        return;
    }
    bool can=0;
    for(;ni<9&&!can;ni++){
        for(;nj<9&&!can;nj++){
            if(surwdkgo[ni][nj]==0)can=1;
            if(can)break;
        }
        if(can)break;
        nj=0;
    }
    if(!can){
        dfs(8,8);
        return;
    }
    bool used[10]={0};
    for(int k=0;k<9;k++){
        used[surwdkgo[k][nj]]=1;
        used[surwdkgo[ni][k]]=1;
    }
    for(int p=0;p<3;p++)
        for(int q=0;q<3;q++)
            used[surwdkgo[p+(ni/3*3)][q+(nj/3*3)]]=1;
    for(int k=1;k<10;k++){
        if(!used[k]){
            surwdkgo[ni][nj]=k;
            dfs(ni,nj);
        }
    }
    surwdkgo[ni][nj]=0;
}
main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++){
            if(scanf("%d",&surwdkgo[i][j])==EOF)return 0;
        }
    dfs(0,0);
    printf("there are a total of %d solution(s).\n",cnt);
}

我要引用

我要回應

儲存至「書籤」