fork download 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4.  
  5. using namespace std;
  6.  
  7. void printGrid(int grid[9][9]) {
  8.     for(int i = 0; i < 9; i++) {
  9.         for(int j = 0; j < 9; j++) {
  10.             cout<<grid[i][j]<<" ";
  11.         }
  12.         cout<<"\n";
  13.     }
  14. }
  15.  
  16. int getLocalBlockStart(int i) {
  17.     if(i >= 0 && i <= 2) {
  18.         return 0;
  19.     } else if(i >= 3 && i <= 5) {
  20.         return 3;
  21.     } else {
  22.         return 6;
  23.     }
  24. }
  25.  
  26. bool checkValueInSameRow(int output[9][9], int row, int col) {
  27.     int num = output[row][col];
  28.     for(int j = 0; j < 9 && j != col; j++) {
  29.        if(output[row][j] == num) {
  30.            return false;
  31.        }
  32.     }
  33.     return true;
  34. }
  35.  
  36. bool checkValueInSameCol(int output[9][9], int row, int col) {
  37.     int num = output[row][col];
  38.     for(int i = 0; i < 9 && i != row; i++) {
  39.        if(output[i][col] == num) {
  40.            return false;
  41.        }
  42.     }
  43.     return true;
  44. }
  45.  
  46. bool checkValueIn3X3Block(int output[9][9], int row, int col) {
  47.     int num = output[row][col];
  48.     int startRow = getLocalBlockStart(row);
  49.     int startCol = getLocalBlockStart(col);
  50.     int endRow = startRow + 3;
  51.     int endCol = startCol + 3;
  52.     for(int i = startRow; i < endRow; i++) {
  53.         for(int j = startCol; j < endCol; j++) {
  54.            if(i != row && j != col && output[i][j] == num) {
  55.                return false;
  56.            } 
  57.         }
  58.     }
  59.     return true;
  60. }
  61.  
  62. bool isSudokuConditionSatisfied(int output[9][9]) {
  63.     bool satisfied = true;
  64.     for(int i = 0; i < 9; i++) {
  65.         for(int j = 0; j < 9; j++) {
  66.             if(output[i][j] != 0) {
  67.                 if(!checkValueInSameRow(output, i, j) || !checkValueInSameCol(output, i, j) || !checkValueIn3X3Block(output, i, j)) {
  68.                     satisfied = false;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     return satisfied;
  74. }
  75.  
  76. void sudoku_solve(int grid[9][9]) {
  77.     for(int i = 0; i < 9; i++) {
  78.         for(int j = 0; j < 9; j++) {
  79.             if(grid[i][j] == 0) {
  80.                 for(int num = 1; num <= 9; num++) {
  81.                     grid[i][j] = num;
  82.                     cout<<"Trying "<<i<<" "<<j<<" with "<<num<<"\n";
  83.                     if(isSudokuConditionSatisfied(grid)) {
  84.                         cout<<"Soduku condition satisfied for "<<i<<" "<<j<<"\n";
  85.                         printGrid(grid);
  86.                         sudoku_solve(grid);
  87.                     }
  88.                 }
  89.                 grid[i][j] = 0;
  90.                 return;
  91.             } 
  92.         }
  93.     }
  94. }
  95.  
  96.  
  97.  
  98. int main(void) {
  99.     int n, board[9][9];
  100.     cin >> n;
  101.     for(int i=0;i<n;i++) {
  102.         for(int j=0;j<9;j++) {
  103.             for(int k=0;k<9;k++) {
  104.                 board[j][k] = 0;
  105.                 cin >> board[j][k];
  106.             }
  107.         }
  108.         sudoku_solve(board);
  109.     }
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/CzIlZd
language:
C++ (gcc 8.3)
created:
19 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!