#include using namespace std; using vi = vector; #define all(x) begin(x),end(x) #define sz(x) (int)x.size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int a[9][9], b_arr[9][9]; int rb[9], rc[9], bb[9], bc[9]; int ra[9], ca[9], ba[9]; vector gc, guc; int step_cnt = 0; bool gen_a(int r, int c) { if(r == 9) return 1; int nr = c == 8 ? r + 1 : r; int nc = c == 8 ? 0 : c + 1; int b_id = (r / 3) * 3 + (c / 3); int used = ra[r] | ca[c] | ba[b_id]; if(used == 511) return 0; vi p; for(int i = 0; i < 9; i++) { if(!(used & (1 << i))) p.push_back(i); } shuffle(all(p), rng); for(int v : p) { a[r][c] = v; ra[r] |= (1 << v); ca[c] |= (1 << v); ba[b_id] |= (1 << v); if(gen_a(nr, nc)) return 1; ra[r] ^= (1 << v); ca[c] ^= (1 << v); ba[b_id] ^= (1 << v); } return 0; } bool dfs_b(int c, const vi& p) { if(c == 9) return 1; if(++step_cnt > 2500) return 0; for(int id : p) { const auto& v = gc[id]; const auto& u = guc[id]; bool ok = 1; for(int i = 0; i < 9; i++) { if(rb[i] & (1 << v[i])) { ok = 0; break; } if(rc[i] & (1 << u[i])) { ok = 0; break; } int b_id = (i / 3) * 3 + (c / 3); if(bb[b_id] & (1 << v[i])) { ok = 0; break; } if(bc[b_id] & (1 << u[i])) { ok = 0; break; } } if(!ok) continue; for(int i = 0; i < 9; i++) { rb[i] |= (1 << v[i]); rc[i] |= (1 << u[i]); int b_id = (i / 3) * 3 + (c / 3); bb[b_id] |= (1 << v[i]); bc[b_id] |= (1 << u[i]); b_arr[i][c] = v[i]; } if(dfs_b(c + 1, p)) return 1; for(int i = 0; i < 9; i++) { rb[i] ^= (1 << v[i]); rc[i] ^= (1 << u[i]); int b_id = (i / 3) * 3 + (c / 3); bb[b_id] ^= (1 << v[i]); bc[b_id] ^= (1 << u[i]); } } return 0; } void solve() { vi v(9); while(1) { for(int i = 0; i < 9; i++) ra[i] = ca[i] = ba[i] = 0; gen_a(0, 0); gc.clear(); guc.clear(); iota(all(v), 0); do { int v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3], v4 = v[4], v5 = v[5], v6 = v[6], v7 = v[7], v8 = v[8]; int mk = 0; bool ok = 1; int u_cur[9]; for(int i = 0; i < 9; i++) { int sum = a[i][0] * v0 + a[i][1] * v1 + a[i][2] * v2 + a[i][3] * v3 + a[i][4] * v4 + a[i][5] * v5 + a[i][6] * v6 + a[i][7] * v7 + a[i][8] * v8; sum %= 9; if(mk & (1 << sum)) { ok = 0; break; } mk |= (1 << sum); u_cur[i] = sum; } if(ok) { gc.push_back(v); guc.push_back(vi(u_cur, u_cur + 9)); } } while(next_permutation(all(v))); if(sz(gc) < 9) continue; for(int i = 0; i < 9; i++) rb[i] = rc[i] = bb[i] = bc[i] = 0; vi p(sz(gc)); iota(all(p), 0); shuffle(all(p), rng); step_cnt = 0; if(dfs_b(0, p)) { for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) cout << a[i][j] << (j == 8 ? "" : " "); cout << "\n"; } for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) cout << b_arr[i][j] << (j == 8 ? "" : " "); cout << "\n"; } return; } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solve(); }