poj_2676_sudoku

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
int map[10][10],rech[10][10],recl[10][10],rec[10][10],flag=0,zero[90][2],count;
void findrec(int x,int y,int num){
    int group;
    if(x>=1&&x<=3){
        if(y>=1&&y<=3){
            rec[1][num]=1;
            group=1;
        }
        else if(y>=4&&y<=6){
            rec[4][num]=1;
            group=4;
        }
        else{
            rec[7][num]=1;
            group=7;
        }
    }
    else if(x>=4&&x<=6){
        if(y>=1&&y<=3){
            rec[2][num]=1;
            group=2;
        }
        else if(y>=4&&y<=6){
            rec[5][num]=1;
            group=5;
        }
        else{
            rec[8][num]=1;
            group=8;
        }
    }
    else{
        if(y>=1&&y<=3){
            rec[3][num]=1;
            group=3;
        }
        else if(y>=4&&y<=6){
            rec[6][num]=1;
            group=6;
        }
        else{
            rec[9][num]=1;
            group=9;
        }
    }
}
int find(int x,int y){
    int group;
    if(x>=1&&x<=3){
        if(y>=1&&y<=3){
            group=1;
        }
        else if(y>=4&&y<=6){
            group=4;
        }
        else{
            group=7;
        }
    }
    else if(x>=4&&x<=6){
        if(y>=1&&y<=3){
            group=2;
        }
        else if(y>=4&&y<=6){
            group=5;
        }
        else{
            group=8;
        }
    }
    else{
        if(y>=1&&y<=3){
            group=3;
        }
        else if(y>=4&&y<=6){
            group=6;
        }
        else{
            group=9;
        }
    }
    return group;
}
void dfs(int step){
    int i,j,k = 0;
    if(flag==1){
        return;
    }
    if(step==count){
        for(i=1;i<=9;i++){
            for(j=1;j<=9;j++){
                printf("%d",map[i][j]);
            }
            printf("n");
        }
        flag=1;
        return;
    }
    for(k=1;k<=9;k++){
        int temp=find(zero[step][1],zero[step][0]);
        if(rec[temp][k]==0&&rech[zero[step][0]][k]==0&&recl[zero[step][1]][k]==0){
            map[zero[step][0]][zero[step][1]]=k;
            rec[temp][k]=1;
            rech[zero[step][0]][k]=1;
            recl[zero[step][1]][k]=1;
            dfs(step+1);
            map[zero[step][0]][zero[step][1]]=0;
            rec[temp][k]=0;
            rech[zero[step][0]][k]=0;
            recl[zero[step][1]][k]=0;
        }
    }
    return;
}
int main() {
    int n,i,j;
    scanf("%d",&n);
    while(n--){
        for(i=1;i<=9;i++){
            for(j=1;j<=9;j++){
                scanf("%1d",&map[i][j]);
                rech[i][map[i][j]]++;
                recl[j][map[i][j]]++;
                findrec(j, i, map[i][j]);
                if(map[i][j]==0){
                    zero[count][0]=i;
                    zero[count][1]=j;
                    count++;
                }
            }
        }
        dfs(0);
        flag=0;
        count=0;
        memset(map, 0, sizeof(int)*100);
        memset(rec, 0, sizeof(int)*100);
        memset(recl, 0, sizeof(int)*100);
        memset(rech, 0, sizeof(int)*100);
    }
    return 0;
}

没啥的,我用的找小九宫格的方式最原始,用坐标区间判断,这样很长,但不易出错.还有要把为零的纪录下来,这样省时间.