https://www.acmicpc.net/problem/2580
---
백트래킹을 제대로 이해하게 된 문제임
연쇄적인 조건을 만족하는 해를 찾아가는 알고리즘.
조건이 맞지 않을 경우 되돌아가 불필요한 탐색을 없앤다.
답이 될 수 없는 조건을 걸고 DFS(재귀) 탐색을 하는 것이 일반적인 것 같음
#include <iostream>
using namespace std;
int sd[9][9];
bool promising (int row, int col, int val) {
for (int i = 0; i < 9; i++) {
if (sd[i][col] == val)
return false;
}
for (int i = 0; i < 9; i++) {
if (sd[row][i] == val)
return false;
}
row = (row / 3) * 3;
col = (col / 3) * 3;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (sd[i][j] == val)
return false;
}
}
return true;
}
void backtracking(int row, int col) {
if (col == 9) {
backtracking(row + 1, 0);
return;
}
if (row == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if(i == 8 && j == 8) {
cout << sd[i][j];
exit(0);
} else {
cout << sd[i][j] << " ";
}
}
cout << "\n";
}
return;
}
if (sd[row][col] == 0) {
for (int i = 1; i <= 9; i++) {
if (promising(row, col, i)) {
sd[row][col] = i;
backtracking(row, col + 1);
}
}
sd[row][col] = 0;
return;
}
backtracking(row, col + 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> sd[i][j];
}
}
backtracking(0, 0);
}