completed, C++ (gcc)

completed

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

const int mod = 1e9 + 7;

const int N = 1e5 + 5;

int mat[9][9];

int remain(int x, int fg){          //fg = 1 -> col, else row
    vector<bool> av(9, false);
    for(int j = 1; j <= 8; j++)
        fg? av[mat[j][x]] = true : av[mat[x][j]] = true;
    
    int pos = 0;
    for(int i = 1; i < 9; i++)
        if(fg && mat[i][x] == 0) pos = i;
        else if(!fg && mat[x][i] == 0) pos = i;
        
    for(int j = 1; j <= 8; j++) 
        if(!av[j]){
            for(int i = 1; i < 8; i++)
                if(fg && mat[pos][i] == j) return 0;
                else if(!fg && mat[i][pos] == j) return 0;
            return j;
        }
}

int possible(int r, int c){
    int rm_r = 0, rm_c = 0, all = 511;
    
    for(int j = 1; j < 9; j++)
        rm_r |= (1 << mat[r][j]), rm_c |= (1 << mat[j][c]);
    rm_r ^= all, rm_c ^= all;
    
    vector<int> occ(9, 0);
    int r1, r2, c1, c2;
    if(r > 0 && r < 5){
        r1 = 1, r2 = 4;
        if(c > 0 && c < 5) c1 = 1, c2 = 4;
        else c1 = 5, c2 = 8;
    }
    else{
        r1 = 5, r2 = 8;
        if(c > 0 && c < 5) c1 = 1, c2 = 4;
        else c1 = 5, c2 = 8;
    }
    for(int j = r1; j <= r2; j++) for(int k = c1; k <= c2; k++) occ[mat[j][k]]++;
    int rm = 0;
    for(int j = 1; j < 9; j++)
        if(occ[j] < 2) rm |= (1 << j);
    
    rm = rm&rm_r&rm_c;
    return rm;
}

void print(){
    for(int j = 1; j < 9; j++){
        for(int k = 1; k < 9; k++) cout << mat[j][k] << " ";
        cout << endl;
    }
    cout << endl;
}

void reset(const vector< vector<bool> >& fix){
    for(int j = 1; j < 9; j++) for(int k = 1; k < 9; k++) if(!fix[j][k]) mat[j][k] = 0;
}

bool foo(){
    //print();
    
    set<pii> s;
    vector<int> rw(9, 0), cl(9, 0);
    vector< vector<bool> > fix(9, vector<bool>(9, true));
    
    for(int j = 1; j <= 8; j++){
        int cnt = 0;
        for(int k = 1; k <= 8; k++){
            if(mat[j][k] == 0) fix[j][k] = false, cnt++;
        }
        rw[j] = cnt;
        if(cnt) s.insert(mp(cnt, j*10));
    }
    
    for(int j = 1; j <= 8; j++){
        int cnt = 0;
        for(int k = 1; k <= 8; k++)
            if(mat[k][j] == 0) cnt++;
        cl[j] = cnt;
        if(cnt) s.insert(mp(cnt, j*10+1));
    }
    
    //for(auto i : s) cout << "(" << i.first << " " << i.second << ")  "; cout << endl;
    
    int x = -1;
    while(!s.empty()){
        int sec = s.begin() -> second, fir = s.begin() -> first;
        s.erase(s.begin());
        
        if(sec % 10){    //col
            sec /= 10;
            if(fir == 1){
                int rem = remain(sec, 1);
                if(rem == 0){
                    reset(fix);
                    return 0;
                }
                for(int j = 1; j <= 8; j++)
                    if(mat[j][sec] == 0){
                        mat[j][sec] = rem;
                        s.erase(mp(rw[j], j*10));
                        rw[j]--;
                        cl[sec]--;
                        if(rw[j]) s.insert(mp(rw[j], j*10));
                        break;
                    }
                continue;
            }
            x = sec*10 + 1;
            break;
        }
        else{            //row
            sec /= 10;
            if(fir == 1){
                int rem = remain(sec, 0);
                if(rem == 0){
                    reset(fix);
                    return 0;
                }
                for(int j = 1; j <= 8; j++)
                    if(mat[sec][j] == 0){
                        mat[sec][j] = rem;
                        s.erase(mp(cl[j], j*10 + 1));
                        cl[j]--;
                        rw[sec]--;
                        if(cl[j]) s.insert(mp(cl[j], j*10+1));
                        break;
                    }
                continue;
            }
            x = sec*10;
            break;
        }
    }
    
    //print();
    if(x == -1) return 1;
    
    if(x % 10){    // col
        x /= 10;
            
        for(int j = 1; j < 9; j++){
            if(mat[j][x] == 0){
                int can = possible(j, x);
                for(int i = 1; i < 9; i++)
                    if(can & (1 << i)){
                        mat[j][x] = i;
                        bool aft = foo();
                        if(aft) return 1;
                        else mat[j][x] = 0;
                    }
                break;
            }
        }
    }
    else{   // row
        x /= 10;
        
        for(int j = 1; j < 9; j++){
            if(mat[x][j] == 0){
                int can = possible(x, j);
                for(int i = 1; i < 9; i++)
                    if(can & (1 << i)){
                        mat[x][j] = i;
                        bool aft = foo();
                        if(aft) return 1;
                        else mat[x][j] = 0;
                    }
                break;
            }
        }
    }
    reset(fix);
    return false;
}

bool check(){
    for(int j = 1; j < 9; j++){
        vector<int> occ(9, 0);
        for(int i = 1; i < 9; i++) occ[mat[j][i]]++;
        for(int i = 1; i < 9; i++) if(occ[i] > 1) return 0;
    }
    for(int j = 1; j < 9; j++){
        vector<int> occ(9, 0);
        for(int i = 1; i < 9; i++) occ[mat[i][j]]++;
        for(int i = 1; i < 9; i++) if(occ[i] > 1) return 0;
    }
    
    vector<int> occ;
    
    occ.clear();
    occ.resize(9, 0);
    for(int j = 1; j < 5; j++)
        for(int k = 1; k < 5; k++) occ[mat[j][k]]++;
    for(int j = 1; j < 9; j++) if(occ[j] > 2) return 0;
        
    occ.clear();
    occ.resize(9, 0);
    for(int j = 1; j < 5; j++)
        for(int k = 5; k < 9; k++) occ[mat[j][k]]++;
    for(int j = 1; j < 9; j++) if(occ[j] > 2) return 0;
        
    occ.clear();
    occ.resize(9, 0);
    for(int j = 5; j < 9; j++)
        for(int k = 1; k < 5; k++) occ[mat[j][k]]++;
    for(int j = 1; j < 9; j++) if(occ[j] > 2) return 0;
      
    occ.clear();
    occ.resize(9, 0);
    for(int j = 5; j < 9; j++)
        for(int k = 5; k < 9; k++) occ[mat[j][k]]++;
    for(int j = 1; j < 9; j++) if(occ[j] > 2) return 0;
      
    return 1;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    scanf("%d",&t);
    for(int i = 1; i <= t; i++){
        printf("Test case #%d: ", i);
        
        for(int j = 1; j < 9; j++)
            for(int k = 1; k < 9; k++) scanf("%d",&mat[j][k]);
            
        if(!check()) printf("NO\n");
        else{
            if(foo()){
                printf("YES\n");
                for(int j = 1; j < 9; j++){
                    for(int k = 1; k < 9; k++)
                        printf("%d ",mat[j][k]);
                    printf("\n");
                }
            }
            else printf("NO\n");
        }
    }
    return 0;
}


run \| edit \| history \| help	0