fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #define N 9
  4.  
  5. using namespace std;
  6.  
  7. bool isSafe(const vector<vector<int>> &board, int row, int col, int val)
  8. {
  9.     // check row
  10.     for (int i = 0; i < N; ++i) {
  11.         if (board[row][i] == val)
  12.             return false;
  13.     }
  14.     // check column
  15.     for (int i = 0; i < N; ++i) {
  16.         if (board[i][col] == val)
  17.             return false;
  18.     }
  19.     // first 3x3 square
  20.     if (row <= 2 && col <= 2) {
  21.         for (int i = 0; i <= 2; ++i) {
  22.             for (int j = 0; j <= 2; ++j) {
  23.                 if (board[i][j] == val)
  24.                     return false;
  25.             }
  26.         }
  27.     }
  28.     // second 3x3 square
  29.     if (row <= 2 && col >= 3 && col <= 5) {
  30.         for (int i = 0; i <= 2; ++i) {
  31.             for (int j = 3; j <= 5; ++j) {
  32.                 if (board[i][j] == val)
  33.                     return false;
  34.             }
  35.         }
  36.     }
  37.     // third 3x3 square
  38.     if (row <= 2 && col >= 6 && col <= 8) {
  39.         for (int i = 0; i <= 2; ++i) {
  40.             for (int j = 6; j <= 8; ++j) {
  41.                 if (board[i][j] == val)
  42.                     return false;
  43.             }
  44.         }
  45.     }
  46.     // fourth 3x3 square
  47.     if (row >= 3 && row <= 5 && col <= 2) {
  48.         for (int i = 3; i <= 5; ++i) {
  49.             for (int j = 0; j <= 2; ++j) {
  50.                 if (board[i][j] == val)
  51.                     return false;
  52.             }
  53.         }
  54.     }
  55.     // fifth 3x3 square
  56.     if (row >= 3 && row <= 5 && col >= 3 && col <= 5) {
  57.         for (int i = 3; i <= 5; ++i) {
  58.             for (int j = 3; j <= 5; ++j) {
  59.                 if (board[i][j] == val)
  60.                     return false;
  61.             }
  62.         }
  63.     }
  64.     // sixth 3x3 square
  65.     if (row >= 3 && row <= 5 && col >= 6 && col <= 8) {
  66.         for (int i = 3; i <= 5; ++i) {
  67.             for (int j = 6; j <= 8; ++j) {
  68.                 if (board[i][j] == val)
  69.                     return false;
  70.             }
  71.         }
  72.     }
  73.     // seventh 3x3 square
  74.     if (row >= 6 && row <= 8 && col <= 2) {
  75.         for (int i = 6; i <= 8; ++i) {
  76.             for (int j = 0; j <= 2; ++j) {
  77.                 if (board[i][j] == val)
  78.                     return false;
  79.             }
  80.         }
  81.     }
  82.     // eighth 3x3 square
  83.     if (row >= 6 && row <= 8 && col >= 3 && col <= 5) {
  84.         for (int i = 6; i <= 8; ++i) {
  85.             for (int j = 3; j <= 5; ++j) {
  86.                 if (board[i][j] == val)
  87.                     return false;
  88.             }
  89.         }
  90.     }
  91.     // ninth 3x3 square
  92.     if (row >= 6 && row <= 8 && col >= 6 && col <= 8) {
  93.         for (int i = 6; i <= 8; ++i) {
  94.             for (int j = 6; j <= 8; ++j) {
  95.                 if (board[i][j] == val)
  96.                     return false;
  97.             }
  98.         }
  99.     }
  100.     return true;
  101. }
  102.  
  103. bool solveSudoku(vector<vector<int>> &board, int row = 0, int col = 0)
  104. {
  105.     // if reaching the final square of sudoku board
  106.     if (row == N && col == N) {
  107.         return true;
  108.     }
  109.     // if reaching the final square of each row
  110.     if (row < N && col == N) {
  111.         if (solveSudoku(board, row + 1)) {
  112.             return true;
  113.         }
  114.         return false;
  115.     }
  116.     // if the square doesn't have a number
  117.     if (board[row][col] == 0)
  118.     {
  119.         for (int i = 1; i <= 9; ++i)
  120.         {
  121.             if (isSafe(board, row, col, i))
  122.             {
  123.                 board[row][col] = i;
  124.                 if (solveSudoku(board, row, col + 1))
  125.                     return true;
  126.                 board[row][col] = 0; // backtrack
  127.             }
  128.         }
  129.         return false;
  130.     }
  131.     else {
  132.         // if the final square on each row has a number
  133.         if (row < N - 1 && col == N - 1) {
  134.             if (solveSudoku(board, row + 1, 0))
  135.                 return true;
  136.         }
  137.         // if the final square of sudoku board has a number
  138.         if (row == N - 1 && col == N - 1) {
  139.             if (solveSudoku(board, row + 1, col + 1))
  140.                 return true;
  141.         }
  142.         // normal
  143.         else {
  144.             if (solveSudoku(board, row, col + 1))
  145.                 return true;
  146.         }
  147.         return false;
  148.     }
  149. }
  150.  
  151. int main()
  152. {
  153.     vector<vector<int>> sudoku(N);
  154.     for (int i = 0; i < N; ++i) {
  155.         sudoku[i].resize(N);
  156.         for (int j = 0; j < N; ++j) {
  157.             cin >> sudoku[i][j];
  158.         }
  159.     }
  160.     if (solveSudoku(sudoku)) {
  161.         for (int i = 0; i < N; ++i)
  162.         {
  163.             for (int j = 0; j < N; ++j)
  164.             {
  165.                 cout << sudoku[i][j] << " ";
  166.             }
  167.             cout << endl;
  168.         }
  169.     }
  170.     else cout << -1;
  171.     return 0;
  172. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
0 7 0 0 6 0 0 0 0
5 0 6 0 0 0 0 0 0
0 0 0 0 0 5 0 2 0
0 0 0 0 0 6 0 0 2
0 0 4 0 0 7 0 0 0
7 0 0 3 0 0 0 0 0
0 0 0 0 0 0 9 4 0
3 9 0 0 0 0 0 0 0
0 0 0 5 1 0 0 0 8
stdout
copy 
1 7 2 4 6 3 5 8 9 
5 3 6 2 9 8 1 7 4 
4 8 9 1 7 5 6 2 3 
9 1 3 8 4 6 7 5 2 
6 2 4 9 5 7 8 3 1 
7 5 8 3 2 1 4 9 6 
8 6 1 7 3 2 9 4 5 
3 9 5 6 8 4 2 1 7 
2 4 7 5 1 9 3 6 8
https://ideone.com/4AxU4F
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!