http://acm.pku.edu.cn/JudgeOnline/problem?id=2676












數獨




T了幾次終于過了!!代碼寫得很..純回溯的。剛開始是正向搜，一直T，看了discuss反向搜就過了！估計是數據問題。

Source Code

    

        

            
Problem: 2676
            

            
User: lovecanon
        
        

            
Memory: 224K
            

            
Time: 79MS
        
        

            
Language: C
            

            
Result: Accepted
        
    

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int map[11][11];
int PlaceIndex[11][11];
int NumOfPlace[11];
int check(int row,int col,int num)
{
    int i,j;
    for(i=((int )ceil(1.0*row/3)-1)*3+1;i<=((int )ceil(1.0*row/3))*3;i++)
        for(j=((int )ceil(1.0*col/3)-1)*3+1;j<=((int )ceil(1.0*col/3))*3;j++)
        {
            if(map[i][j]==num) return 0;
        }
    for(i=1;i<=9;i++)
    {
        if(map[row][i]==num)  return 0;
        if(map[i][col]==num)   return 0;
    }
    return 1;
}

int solve(int row,int t)
{
    int i;
    if(row<1)  return 1;
    if(t>NumOfPlace[row]) if(solve(row-1,1)) return 1;
    for(i=1;i<=9;i++)
    {
        if(check(row,PlaceIndex[row][t],i))
        {
            map[row][PlaceIndex[row][t]]=i;
            if(solve(row,t+1))  return 1;
            map[row][PlaceIndex[row][t]]=0;
        }
    }
    return 0;
}

int main()
{
    int cases;
    scanf("%d",&cases);getchar();
    while(cases--)
    {
        int i,j;
        memset(NumOfPlace,0,sizeof(NumOfPlace));

        for(i=1;i<=9;i++)
        {
            for(j=1;j<=9;j++)
            {
                map[i][j]=getchar()-'0';
                if(map[i][j]==0)  
                {
                    ++NumOfPlace[i];
                    PlaceIndex[i][NumOfPlace[i]]=j;
                }            
            }
            getchar();
        }
        solve(9,1);
        for(i=1;i<=9;i++)
        {
            for(j=1;j<=9;j++)
                printf("%d",map[i][j]);
            printf("\n");
        }    
    }
    return 0;
}