fork download
  1. #include <iostream>
  2. #include <utility>
  3.  
  4. int table[9][9], k;
  5. std::pair<int, int> empty[81];
  6.  
  7. bool line(int y, int x, int n) {
  8. int i, j;
  9.  
  10. for (i = 0; i < 9; i++) {
  11. if (i != y and table[i][x] == n)
  12. return false;
  13. if (i != x and table[y][i] == n)
  14. return false;
  15. }
  16.  
  17. return true;
  18. }
  19.  
  20. bool box(int y, int x, int n) {
  21. int i, j;
  22.  
  23. int base_y = y / 3 * 3;
  24. int base_x = x / 3 * 3;
  25.  
  26. for (i = base_y; i < base_y + 3; i++)
  27. for (j = base_x; j < base_x + 3; j++)
  28. if (table[i][j] == n)
  29. return false;
  30.  
  31. return true;
  32. }
  33.  
  34. void sudoku(int n) {
  35. int i, j;
  36.  
  37. if (n == k) {
  38. for (i = 0; i < 9; i++) {
  39. for (j = 0; j < 9; j++)
  40. std::cout << table[i][j] << " ";
  41. std::cout << std::endl;
  42. }
  43.  
  44. exit(0);
  45. }
  46.  
  47. int y = empty[n].first;
  48. int x = empty[n].second;
  49.  
  50. for (i = 1; i <= 9; i++) {
  51. if (line(y, x, i) and box(y, x, i)) {
  52. table[y][x] = i;
  53.  
  54. sudoku(n + 1);
  55.  
  56. table[y][x] = 0;
  57. }
  58. }
  59. }
  60.  
  61. int main() {
  62. int i, j;
  63.  
  64. for (i = 0; i < 9; i++) {
  65. for (j = 0; j < 9; j++) {
  66. std::cin >> table[i][j];
  67.  
  68. if (table[i][j] == 0)
  69. empty[k++] = { i, j };
  70. }
  71. }
  72.  
  73. sudoku(0);
  74.  
  75. return 0;
  76. }
Success #stdin #stdout 0.01s 5288KB
stdin
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
stdout
1 2 3 4 5 6 7 8 9 
4 5 6 7 8 9 1 2 3 
7 8 9 1 2 3 4 5 6 
2 1 4 3 6 5 8 9 7 
3 6 5 8 9 7 2 1 4 
8 9 7 2 1 4 3 6 5 
5 3 1 6 4 2 9 7 8 
6 4 2 9 7 8 5 3 1 
9 7 8 5 3 1 6 4 2