의 격자에 ~ 까지의 숫자 중 하나를 채워넣는데, 각 행 / 열에 중복되는 숫자가 없어야 하며, 격자를 종횡으로 3등분한 모든 격자에도 중복되는 숫자가 하나도 없어야 한다. 아래는 완성된 스도쿠 판 예시이다.
문제에서는 아래와 같이 몇몇 칸들이 비어있는 채로 주어지게 된다.
비어있는 칸들에 들어가야 하는 값들을 추론해 주어진 스도쿠 판을 완성시켜보자 개의 숫자가 입력되며 빈칸은 0으로 입력된다.
81개의 칸이 모두 비어있는 입력이 주어질 때를 생각해보자. 단순하게 완전 탐색으로 생각해본다면 각 칸에 들어갈 수 있는 숫자는 9가지이므로 경우의 수는 이된다. 말 그대로 어마무시한 숫자다. 하지만 첫 번째 문제에서 처럼 각 행/열/격자마다 숫자가 중복될 수 없다는 제약이 있으니 이를 활용해 경우의 수를 소거할 수 있다. 빈 칸들을 탐색하며 해당하는 행/열/격자에 아직 사용되지 않은 숫자를 집어넣는 재귀 함수를 작성해 해결할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
int arr[10][10];
int v[10][10], h[10][10], box[3][3][10]; // 숫자 사용 여부 기입
struct pos {
int x, y;
};
vector<pos> zpos;
void r(int p) {
if (p == zpos.size()) {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cout << arr[i][j] << " ";
}
cout << "\n";
}
exit(0);
}
for (int i = 1; i <= 9; i++) {
int x = zpos[p].x;
int y = zpos[p].y;
if (v[y][i] == 1 || h[x][i] == 1 || box[(y - 1) / 3][(x - 1) / 3][i] == 1) continue; // 행/열/박스에서 이미 해당 숫자를 사용한 경우 검사 생략
v[y][i] = 1; h[x][i] = 1; box[(y - 1) / 3][(x - 1) / 3][i] = 1; arr[y][x] = i;
r(p + 1); // 다음 위치 탐색
v[y][i] = 0; h[x][i] = 0; box[(y - 1) / 3][(x - 1) / 3][i] = 0; arr[y][x] = 0; // 현재 숫자를 넣었을 때 완성되지 않은 경우, 사용 여부 초기화
}
}
int main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cin >> arr[i][j];
if (arr[i][j] == 0) {
// 빈칸인 경우 위치 기록
zpos.push_back({ j, i });
}
else {
// 빈칸이 아닌 경우 해당 숫자 사용 여부 기록
v[i][arr[i][j]] = 1; h[j][arr[i][j]] = 1; box[(i - 1) / 3][(j - 1) / 3][arr[i][j]] = 1;
}
}
}
r(0);
return 0;
}