Untitled
raw download clone
TEXT
views 25
,
size 3626 b
#include<bits/stdc++.h>
using namespace std;
typedef long long          ll;
typedef vector<int>        vi;
typedef pair<int, int>     ii;
typedef vector<ii>         vii;
typedef set<int>           si;
typedef map<string, int>   msi;
typedef map<int, int>      mii;
typedef map<int, bool>     mib;
#define m 1000000007
#define MX 1000000
#define forr(a,b)          for(int i=a; i<=b; i++)
#define rforr(a,b)         for(int i=b; i>=a; i--)
#define sf(a)              scanf("%d",&a)
#define sf2(a,b)           scanf("%d%d",&a,&b)
#define sf3(a,b,c)         scanf("%d%d%d",&a,&b,&c)
#define sfl(a)             scanf("%lld",&a)
#define sfl2(a,b)          scanf("%lld%lld",&a,&b)
#define pf(a)              printf("%d\n",a)
#define pf2(a,b)           printf("%d %d\n",a,b)
#define pf3(a,b,c)         printf("%d%d%d",a,b,c)
#define pfl(a)             printf("%lld\n",a)
#define pfl2(a,b)          printf("%lld%lld",a,b)
#define pb                 push_back
#define ppb                pop_back
int sud[10][10];
int cnt;
bool in_ro(int n, int x)
{
    forr(1,9) if(sud[x][i]==n) return 1;
    return 0;
}
bool in_col(int n, int y)
{
    forr(1,9) if(sud[i][y]==n) return 1;
    return 0;
}
bool in_box(int n, int x, int y)
{
    x=((x-1)/3)*3;
    y=((y-1)/3)*3;
    for(int i=1; i<4; i++)
        for(int j=1; j<4; j++)
            if(sud[x+i][y+j]==n) return 1;
    return 0;
}
int npv(int x, int y)//num of poss value
{
    int cnt=0;
    for(int k=1;k<10;k++)
        if(!in_ro(k,x) && !in_col(k,y) && !in_box(k,x,y)) cnt++;
    return cnt;
}
/*int mnx()
{
    int ret,mn=10;
    for(int x=1;x<10;x++)
        for(int y=1;y<10;y++){
            if(sud[x][y]==0){
                int t=npv(x,y);
                if(t<mn){ret=x;mn=t;}
            }
        }
    return ret;
}
int mny()
{
    int ret,mn=10;
    for(int x=1;x<10;x++)
        for(int y=1;y<10;y++){
            if(sud[x][y]==0){
                int t=npv(x,y);
                if(t<mn){ret=y;mn=t;}
            }
        }
    return ret;
}*/
void mnxy(int &X, int &Y)
{
    int mn=10;
    for(int x=1;x<10;x++)
        for(int y=1;y<10;y++){
            if(sud[x][y]==0){
                int t=npv(x,y);
                if(t<mn){X=x;Y=y;mn=t;}
            }
        }
    //return ret;
}
void bos()
{
    //pf(cnt);
    if(cnt==0){
        forr(1,9){
            for(int j=1;j<10;j++){
                printf("%d",sud[i][j]);
            }
            puts("");
        }
        return;
    }
    //int x=mnx();
    //int y=mny();
    int x,y;
    mnxy(x,y);
    //pf2(x,y);
    for(int k=1;k<10;k++){//pf(k);
        if(!in_ro(k,x) && !in_col(k,y) && !in_box(k,x,y)){
            sud[x][y]=k;
            /*forr(1,9){
                for(int j=1;j<10;j++){
                    printf("%d",sud[i][j]);
                }
                puts("");
            }*/
            cnt--;
            bos();
            if(cnt==0) return;
            sud[x][y]=0;
            cnt++;
        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    char a[100];
    int t,l=1;
    sf(t);fflush(stdin);
    while(t--){
        cnt=0;
        for(int i=1;i<10;i++){
            scanf("%s",a);
            for(int j=0;j<9;j++){
                if(a[j]=='.') {sud[i][j+1]=0;cnt++;}
                else{
                    int x=a[j]-'0';
                    sud[i][j+1]=x;
                }
            }
        }
        printf("Case %d:\n",l++);
        bos();
    }
}
close fullscreen
Login or Register to edit or fork this paste. It's free.