acwing 166

acwing 166

#include
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define _zero(a) memset(a, 0, sizeof(a))
#define endl 'n'
#define int long long
//#define mp make_pair
#define PII pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define PII pair
typedef long long ll;
typedef double dd;
typedef long double ld;

using namespace std;

const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);//arctan(y/x);
const ld eps = 1e-8;

const int N = 9;
int ones[1 << N], mp[1 << N];
int row[N], col[N], cell[3][3];
char str[100];

inline int lowbit(int x)
{
    return x & -x;
}

void init()
{
    for(int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
    for(int i = 0; i < 3; i++) 
        for(int j = 0; j < 3; j++) 
            cell[i][j] = (1 << N) - 1;
}

inline int get(int xx, int yy)
{
    return row[xx] & col[yy] & cell[xx / 3][yy / 3];
}

bool dfs(int cnt)
{
    if(!cnt) return true;
    
    int minv = 20;
    int xx, yy;
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++) 
            if(str[i * 9 + j] == '.'){
                int t = ones[get(i, j)];
                if(t < minv){
                    minv = t;
                    xx = i, yy = j;
                }
            }
    
    for(int i = get(xx, yy); i; i -= lowbit(i)){
        
        int t = mp[lowbit(i)];
        
        row[xx] -= 1 << t;
        col[yy] -= 1 << t;
        cell[xx / 3][yy / 3] -= 1 << t;
        str[xx * 9 + yy] = '1' + t;
        
        if(dfs(cnt - 1)) return true;
        
        row[xx] += 1 << t;
        col[yy] += 1 << t;
        cell[xx / 3][yy / 3] += 1 << t;
        str[xx * 9 + yy] = '.';
    }
    return false;
}

signed main()
{
    IOS;
    for(int i = 0; i < N; i++) mp[1 << i] = i;
    
    for(int i = 0; i < 1 << N; i++){
        int s = 0;
        for(int j = i; j; j -= lowbit(j)) s++;
        ones[i] = s;
    }
    
    while(cin >> str, str[0] != 'e'){
        init();
        
        int cnt = 0;
        for(int i = 0, k = 0; i < N; i++){
            for(int j = 0; j < N; j++, k++){
                if(str[k] != '.'){
                    int t = str[k] - '1';
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    cell[i/3][j/3] = 1 << t;
                }
                else cnt ++;
            }
        }
        dfs(cnt);
        cout << str << endl;
    }
    return 0;
}