fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=10;
  5. int n, a[N][N], x[N][N];
  6. bool row[N][10], col[N][10], cell[N][10];
  7.  
  8. int getcell(int i, int j)
  9. {
  10.     return (i-1)/3*3+(j-1)/3;
  11. }
  12.  
  13. bool check()
  14. {
  15.     for(int i=1;i<=n;++i){
  16.         for(int j=1;j<=n;++j){
  17.             if(a[i][j]==0 && x[i][j]==0) return false;
  18.         }
  19.     }
  20.     return true;
  21. }
  22.  
  23. void print()
  24. {
  25.     for(int i=1;i<=n;++i){
  26.         cout << i << ": ";
  27.         for(int j=1;j<=n;++j){
  28.             if(x[i][j]!=0) cout << x[i][j] << ' ';
  29.         }
  30.         cout << '\n';
  31.     }
  32.     exit(0);
  33. }
  34.  
  35. bool btrack(int i, int j)
  36. {
  37.     if(i>n || j>n){
  38.         if(check())
  39.             print();
  40.         return false;
  41.     }
  42.     if(a[i][j]==0){
  43.         bool ok=false;
  44.         for(int d=1;d<=n;++d){
  45.             if(row[i][d] || col[j][d]) continue;
  46.             if(cell[getcell(i, j)][d]) continue;
  47.             ok=true;
  48.             x[i][j]=d;
  49.             row[i][d]=1;
  50.             col[j][d]=1;
  51.             cell[getcell(i, j)][d]=1;
  52.             if(j==n) ok=btrack(i+1, 1);
  53.             else ok=btrack(i, j+1);
  54.             x[i][j]=0;
  55.             row[i][d]=0;
  56.             col[j][d]=0;
  57.             cell[getcell(i, j)][d]=0;
  58.         }
  59.         if(!ok) return false;
  60.     }
  61.     if(j==n) btrack(i+1, 1);
  62.     else btrack(i, j+1);
  63.     return false;
  64. }
  65.  
  66. signed main()
  67. {
  68.     ios::sync_with_stdio(0);
  69.     cin.tie(0); cout.tie(0);
  70.  
  71.     cin >> n;
  72.     for(int i=1;i<=n;++i){
  73.         for(int j=1;j<=n;++j){
  74.             cin >> a[i][j];
  75.             row[i][a[i][j]]=1;
  76.             col[j][a[i][j]]=1;
  77.             cell[getcell(i, j)][a[i][j]]=1;
  78.         }
  79.     }
  80.     btrack(1, 1);
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ELsLuR
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!