fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 81, P = 9;
  6.  
  7. int block[][ P ] = {
  8.     { 0, 0, 0, 1, 1, 1, 2, 2, 2 },
  9.     { 0, 0, 0, 1, 1, 1, 2, 2, 2 },
  10.     { 0, 0, 0, 1, 1, 1, 2, 2, 2 },
  11.     { 3, 3, 3, 4, 4, 4, 5, 5, 5 },
  12.     { 3, 3, 3, 4, 4, 4, 5, 5, 5 },
  13.     { 3, 3, 3, 4, 4, 4, 5, 5, 5 },
  14.     { 6, 6, 6, 7, 7, 7, 8, 8, 8 },
  15.     { 6, 6, 6, 7, 7, 7, 8, 8, 8 },
  16.     { 6, 6, 6, 7, 7, 7, 8, 8, 8 } };
  17.  
  18. class sudoku_t: vector< int >
  19. {
  20.     int cell[ P ][ P ];
  21.  
  22.     typedef bitset< P >       bitset_t;
  23.  
  24.     array< bitset_t, P > row, col, blk;
  25.  
  26.     bool set_cell( int i, int j, int k )
  27.     {
  28.         int b = block[ i ][ j ], l = k - 1;
  29.  
  30.         if ( row[ i ][ l ] or col[ j ][ l ] or blk[ b ][ l ] )
  31.             return false;
  32.         else
  33.         {
  34.             push_back( cell[ i ][ j ] ), cell[ i ][ j ] = k;
  35.  
  36.             return row[ i ][ l ] = col[ j ][ l ] = blk[ b ][ l ] = true;
  37.         }
  38.     }
  39.  
  40.     void reset_cell( int i, int j )
  41.     {
  42.         int b = block[ i ][ j ], k = cell[ i ][ j ], l = k - 1;
  43.  
  44.         cell[ i ][ j ] = back(), pop_back(), row[ i ][ l ] = col[ j ][ l ] = blk[ b ][ l ] = false;
  45.     }
  46.  
  47. public:
  48.  
  49.     sudoku_t()
  50.     {
  51.         for( int i = 0; i < P; i++ )
  52.             for( int j = 0; j < P; j++ )
  53.             {
  54.                 int k; cin >> k, cell[ i ][ j ] = 0;
  55.  
  56.                 if ( k > 0 and not set_cell( i, j, k ) )
  57.                 {
  58.                     cout << "invalid initial state cell(",
  59.                     cout << i << ',' << j << ") = " << k << endl;
  60.                     exit( 1 );
  61.                 }
  62.             }
  63.     }
  64.  
  65.     bool solved( const int row = 0, const int col = 0 )
  66.     {
  67.         int next_col = col, next_row = row;
  68.  
  69.         if ( ++next_col == P )
  70.             next_col = 0, ++next_row;
  71.  
  72.         if ( cell[ row ][ col ] != 0 )
  73.             return size() == N ? true : solved( next_row, next_col );
  74.  
  75.         for( int k = 1; k <= P; k++ )
  76.             if ( set_cell( row, col, k ) )
  77.             {
  78.                 if ( size() == N or solved( next_row, next_col ) )
  79.                     return true;
  80.                 else
  81.                     reset_cell( row, col );
  82.             }
  83.  
  84.         return false;
  85.     }
  86.  
  87.     void write() const
  88.     {
  89.         for( int i = 0; i < P; i++, cout << '\n' )
  90.             for( int j = 0; j < P; j++ )
  91.                 cout << cell[ i ][ j ] << ' ';
  92.     }
  93. };
  94.  
  95. int main()
  96. {
  97.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  98.  
  99.     sudoku_t sudoku;
  100.  
  101.     if ( sudoku.solved() )
  102.         sudoku.write();
  103.     else
  104.         cout << "No solution";
  105. }
  106.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
0 0 5 1 3 0 0 0 7
3 0 0 0 4 0 5 9 0
0 0 1 0 6 0 0 8 0
0 0 0 0 7 4 0 0 0 
0 5 0 8 0 9 7 3 0
4 0 0 6 2 3 0 0 0
2 8 4 0 0 0 0 0 0
0 0 6 7 0 0 9 0 0 
0 0 9 4 0 0 3 6 8
stdout
copy 
9 4 5 1 3 8 6 2 7 
3 6 8 2 4 7 5 9 1 
7 2 1 9 6 5 4 8 3 
8 9 3 5 7 4 2 1 6 
6 5 2 8 1 9 7 3 4 
4 1 7 6 2 3 8 5 9 
2 8 4 3 9 6 1 7 5 
5 3 6 7 8 1 9 4 2 
1 7 9 4 5 2 3 6 8
https://ideone.com/mL8YX6
Sudoku
language:
C++14 (gcc 8.3)
created:
6 years 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!