fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int board[9][9];
  6.  
  7. struct pos {
  8.     int x, y;
  9. };
  10.  
  11. pos find_empty(int bo[9][9])
  12. {
  13.     pos result;
  14.     result.x = -1;
  15.     result.y = -1;
  16.  
  17.     for(auto i = 0; i < 9; i++)
  18.         for(auto j = 0; j < 9; j++)
  19.             if(bo[i][j] == 0) {
  20.                 result.x = i;
  21.                 result.y = j;
  22.                 return result;
  23.             }
  24.  
  25.     return result;
  26. }
  27.  
  28. bool valid(int bo[9][9], int num, pos position)
  29. {
  30.     int i, j;
  31.  
  32.     // check row
  33.     for(i = 0; i < 9; i++)
  34.         if(bo[position.x][i] == num && position.y != i)
  35.             return false;
  36.  
  37.     // check column
  38.     for(i = 0; i < 9; i++)
  39.         if(bo[i][position.y] == num && position.x != i)
  40.             return false;
  41.  
  42.     // check box
  43.     int box_x = position.y / 3, box_y = position.x / 3;
  44.  
  45.     for(i = box_y * 3; i < box_y * 3 + 3; i++)
  46.         for(j = box_x * 3; j < box_x * 3 + 3; j++)
  47.             if(bo[i][j] == num && i != position.x && j != position.y)
  48.                 return false;
  49.  
  50.     return true;
  51. }
  52.  
  53. bool backtracking(int bo[9][9])
  54. {
  55.     int row, col, i;
  56.  
  57.     pos find = find_empty(bo);
  58.  
  59.     if(find.x == -1)
  60.         return true;
  61.  
  62.     row = find.x;
  63.     col = find.y;
  64.  
  65.     for(i = 1; i < 10; i++) {
  66.         if(valid(bo, i, find)) {
  67.             bo[row][col] = i;
  68.  
  69.             if(backtracking(bo))
  70.                 return true;
  71.  
  72.             bo[row][col] = 0;
  73.         }
  74.     }
  75.  
  76.     return false;
  77. }
  78.  
  79. int main(void)
  80. {
  81.     int i, j;
  82.  
  83.     for(i = 0; i < 9; i++)
  84.         for(j = 0; j < 9; j++)
  85.             cin >> board[i][j];
  86.  
  87.     backtracking(board);
  88.  
  89.     for(i = 0; i < 9; i++) {
  90.         for(j = 0; j < 9; j++)
  91.            cout << board[i][j] << " ";
  92.         cout << endl;
  93.     }
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
2 5 8 7 3 0 9 4 1
6 0 9 8 2 4 3 0 7
4 0 7 0 1 5 2 6 0
3 9 5 2 7 0 4 0 6
0 6 2 4 0 8 1 0 5
8 4 0 6 5 0 7 2 9
1 8 4 3 6 9 5 7 2
0 7 0 1 4 2 0 9 3
9 2 3 5 8 7 6 1 4
stdout
copy 
2 5 8 7 3 6 9 4 1 
6 1 9 8 2 4 3 5 7 
4 3 7 9 1 5 2 6 8 
3 9 5 2 7 1 4 8 6 
7 6 2 4 9 8 1 3 5 
8 4 1 6 5 3 7 2 9 
1 8 4 3 6 9 5 7 2 
5 7 6 1 4 2 8 9 3 
9 2 3 5 8 7 6 1 4
https://ideone.com/HftRzb
Sudoku
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!