💡 백트래킹
Memory 1228KB Time 688ms Code Length 1232B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
int map[9][9];
int ResultMap[9][9];
vector<pair<int, int>> v;
int NumOfZero = 0;
void FindBlank() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (map[i][j] == 0)
v.push_back({ i,j });
}
}
}
bool isDup(int y, int x, int num) {
int py3 = y / 3;
int px3 = x / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (map[i + 3 * py3][j + 3 * px3] == num) return true;
}
}
for (int i = 0; i < 9; i++) {
if (map[y][i] == num) return true;
}
for (int i = 0; i < 9; i++) {
if (map[i][x] == num) return true;
}
return false;
}
void dfs(int index) {
if (index == NumOfZero) {
memcpy(ResultMap, map, sizeof(map));
return;
}
for (int i = 1; i <= 9; i++) {
int y = v[index].first;
int x = v[index].second;
if (isDup(y, x, i))continue;
map[y][x] = i;
dfs(index + 1);
map[y][x] = 0;
}
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf(" %d", &map[i][j]);
}
}
FindBlank(); // vector 생성
NumOfZero = v.size();
dfs(0);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d ", ResultMap[i][j]);
}
printf("\n");
}
}
이 코드는 9x9 크기의 스도쿠 퍼즐을 풀기 위한 프로그램이다.
FindBlank() 함수는 주어진 스도쿠 퍼즐에서 빈 칸(0으로 표시된 칸)의 위치를 찾아 v 벡터에 저장한다.
isDup() 함수는 주어진 숫자가 특정 위치에 입력될 때 스도쿠 규칙을 위배하는지 확인한다. 가로, 세로, 그리고 3x3 작은 정사각형 영역에 중복된 숫자가 있는지 검사한다.
dfs() 함수는 백트래킹을 사용하여 스도쿠 퍼즐을 해결한다. 빈 칸에 가능한 숫자를 하나씩 넣어보면서 모든 경우의 수를 탐색한다.
main() 함수에서는 초기 스도쿠 퍼즐을 입력받고, FindBlank() 함수를 통해 빈 칸을 찾고, dfs() 함수를 호출하여 스도쿠 퍼즐을 풀고 결과를 출력한다.
