fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. bool v_possible(vector<vector<int>>& sudoku, pair<int, int> pos, int num){
  7. 	for(int i = 0; i < 9; i++){
  8. 		if(i != pos.first and sudoku[i][pos.second] == num){
  9. 			return false;
  10. 		}
  11. 	}
  12. 	return true;
  13. }
  14.  
  15. bool h_possible(vector<vector<int>>& sudoku, pair<int, int> pos, int num){
  16. 	for(int i = 0; i < 9; i++){
  17. 		if(i != pos.second and sudoku[pos.first][i] == num){
  18. 			return false;
  19. 		}
  20. 	}
  21. 	return true;
  22. }
  23.  
  24. bool s_possible(vector<vector<int>>& sudoku, pair<int, int> pos, int num){
  25.  
  26. 	int r = pos.first / 3 * 3;
  27. 	int c = pos.second / 3 * 3;
  28.  
  29. 	for(int i = 0; i < 3; i++){
  30. 		for(int j = 0; j < 3; j++){
  31. 			if(r + i != pos.first and c + j != pos.second and sudoku[r + i][c + j] == num){
  32. 				return false;
  33. 			}
  34. 		}
  35. 	}
  36. 	return true;
  37. }
  38.  
  39. void dfs(vector<vector<int>>& sudoku, vector<pair<int, int>>& blank, int idx){
  40. 	if(idx == blank.size()){
  41. 		for(int i = 0; i < 9; i++){
  42. 			for(int j = 0; j < 9; j++){
  43. 				cout << sudoku[i][j] << " ";
  44. 			}
  45. 			cout << '\n';
  46. 		}
  47. 		exit(0);
  48. 	}
  49.  
  50. 	for(int i = 1; i <= 9; i++){
  51. 		pair<int, int> pos = blank[idx];
  52. 		if(v_possible(sudoku, pos, i) and h_possible(sudoku, pos, i) and s_possible(sudoku, pos, i)){
  53. 			sudoku[pos.first][pos.second] = i;
  54. 			dfs(sudoku, blank, idx + 1);
  55. 			sudoku[pos.first][pos.second] = 0;
  56. 		}
  57. 	}
  58. }
  59.  
  60. int main() {
  61.  
  62. 	ios_base::sync_with_stdio(0);
  63. 	cin.tie(0);
  64.  
  65. 	vector<vector<int>> sudoku(9, vector<int>(9));
  66. 	vector<pair<int, int>> blank;
  67.  
  68. 	for(int i = 0; i < 9; i++){
  69. 		for(int j = 0; j < 9; j++){
  70. 			cin >> sudoku[i][j];
  71. 			if(sudoku[i][j] == 0){
  72. 				blank.push_back(make_pair(i, j));
  73. 			}
  74. 		}
  75. 	}
  76.  
  77. 	dfs(sudoku, blank, 0);
  78.  
  79. 	return 0;
  80. }
Success #stdin #stdout 0s 4988KB
comments (?)
stdin
copy 
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
stdout
copy 
1 3 5 4 6 9 2 7 8 
7 8 2 1 3 5 6 4 9 
4 6 9 2 7 8 1 3 5 
3 2 1 5 4 6 8 9 7 
8 7 4 9 1 3 5 2 6 
5 9 6 8 2 7 4 1 3 
9 1 7 6 5 2 3 8 4 
6 4 3 7 8 1 9 5 2 
2 5 8 3 9 4 7 6 1
https://ideone.com/PaeoI0
language:
C++14 (gcc 8.3)
created:
3 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!