sudokunique.cpp

#include <bits/stdc++.h>
using namespace std;

#define PI acos(-1.0)
#define MOD 1000000007

template<class T1, class T2>
using umap = unordered_map<T1, T2>;
template<class T>
using uset = unordered_set<T>;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int s[9][9];

inline int lsone(int n) {
  return n & (-n);
}

inline int bid2(int x, int y) {
  return x / 3 * 3 + y / 3;
}

int h[9];
int v[9];
int b[9];
int mem[9][9];

int r;

vector<ii> alur;
int sz;

void solve(int idx) {
  if (idx == sz) {
    memcpy(mem, s, sizeof(mem));
    ++r;
    return;
  }

  auto a = alur[idx];
  int x = a.first;
  int y = a.second;

  int bid = bid2(x, y);

  int hm = h[x];
  int vm = v[y];
  int bm = b[bid];
  int m = (hm & vm & bm);

  for (int mc = m; mc > 0; mc -= lsone(mc)) {
    int l = lsone(mc);
    int can = __builtin_ctz(l) + 1;

    s[x][y] = can;
    h[x] -= l;
    v[y] -= l;
    b[bid] -= l;

    solve(idx + 1);

    if (r > 1) return;

    h[x] += l;
    v[y] += l;
    b[bid] += l;
    s[x][y] = 0;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  while (true) {
    for (int i = 0; i < 9; ++i) {
      h[i] = (1 << 9) - 1;
      v[i] = (1 << 9) - 1;
      b[i] = (1 << 9) - 1;
    }

    bool ok = true;
    alur.clear();

    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        int k;
        if (!(cin >> k)) {
          return 0;
        }
        s[i][j] = k;

        if (k == 0) {
          alur.emplace_back(i, j);
          continue;
        }

        int tos = (1 << (k - 1));
        int bbb = bid2(i, j);

        if ((tos > 0) && (h[i] & tos) == 0) ok = false;
        if ((tos > 0) && (v[j] & tos) == 0) ok = false;
        if ((tos > 0) && (b[bbb] & tos) == 0) ok = false;

        h[i] -= tos;
        v[j] -= tos;
        b[bbb] -= tos;
      }
    }

    if (!ok) {
      cout << "Find another job" << endl << endl;
      continue;
    }

    r = 0;
    sz = alur.size();
    solve(0);

    if (r == 0) {
      cout << "Find another job" << endl << endl;
      continue;
    } else if (r > 1) {
      cout << "Non-unique" << endl << endl;
      continue;
    }
    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        cout << (mem[i][j]) << " ";
      }
      cout << endl;
    }
    cout << endl;
  }
}