Sicily 1162 Sudoku

数独、直接深く探せばいい.

#include <stdio.h>
#include <string.h>
#include <memory.h>
int t;
int data[12][12];
int row [12][12];
int col[12][12];
int square[12][12];
int x[90];
int y[90];
char num;
int ctr,flag;
int get_square_num(int i,int j) {
    if (i>=1&&i<=3) {
        if (j>=1&&j<=3)
            return 1;
        else if (j>=4&&j<=6)
            return 2;
        else
            return 3;
    }
    else if (i>=4&&i<=6) {
        if (j>=1&&j<=3)
            return 4;
        else if (j>=4&&j<=6)
            return 5;
        else
            return 6;
    }
    else {
        if (j>=1&&j<=3)
            return 7;
        else if (j>=4&&j<=6)
            return 8;
        else
            return 9;
    }
}
void DFS(int p) {
    int temp,i,j,m;
    if (flag==1)
        return;
    if (p==ctr) {
        flag=1;
        return;
    }
    i=x[p];
    j=y[p];
    temp=get_square_num(i,j);
//  printf("%d %d %d
",i,j,temp);
    for (m=1;m<=9;m++) {
        if (row[i][m]==0&&col[j][m]==0&&square[temp][m]==0) {
            data[i][j]=m;
            row[i][m]=1;
            col[j][m]=1;
            square[temp][m]=1;
            DFS(p+1);
            if (flag==1)/*´Ë´¦²»´óÀí½â£¬ÐèҪעÒâ*/
                return;
        //  data[i][j]=0;
            row[i][m]=0;
            col[j][m]=0;
            square[temp][m]=0;          
        }
    }
}
int main()
{
    int i,j,temp;

    scanf("%d",&t);
    getchar();
    while (t--) {
        ctr=0;
        flag=0;
        memset(row,0,sizeof(row));
        memset(col,0,sizeof(col));
        memset(square,0,sizeof(square));
        for (i=1;i<=9;i++) {
            for (j=1;j<=9;j++) {
                scanf("%c",&num);
                data[i][j]=num-'0';
                if (data[i][j]==0) {
                    x[ctr]=i;
                    y[ctr]=j;
                    ctr++;
                }
                else {
                //  printf("888888888
");
                    temp=get_square_num(i,j);
                    row[i][data[i][j]]=1;
                    col[j][data[i][j]]=1;
                    square[temp][data[i][j]]=1;
                }
            }
            getchar();
        }
    
        DFS(0);
        for (i=1;i<=9;i++) {
            for (j=1;j<=9;j++) {
                printf("%d",data[i][j]);
            }
            printf("
");
        }
    }
    return 0;
}