https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
백 트래킹으로 칸에 들어가지 못하는 수는 아예 넣지를 말자
n-queen 문제와 유사. 행, 열, 정사각형을 검사해야한다
|
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int sudo[10][10];
bool c[10][10]; // 행 9개
bool c2[10][10]; // 열 9개
bool c3[10][10]; // 정사각형 9개
// 정사각형 번호 매기기
int square(int x, int y)
{
return (x / 3) * 3 + (y / 3);
}
bool go(int z)
{
//출력
if (z == 81)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
cout << sudo[i][j] << ' ';
}
cout << '\n';
}
return true;
}
// 이차원 배열에 번호 붙이기
// k / m -> 행 k % m -> 열
int x = z / 9;
int y = z % 9;
// 백트래킹
if (sudo[x][y] != 0)
{
return go(z + 1);
}
else // 0 일 때
{
for (int i = 1; i <= 9; i++)
{
if (c[x][i] == 0 && c2[y][i] == 0 && c3[square(x, y)][i] == 0)
{
c[x][i] = c2[y][i] = c3[square(x, y)][i] = true;
sudo[x][y] = i;
if (go(z + 1))
return true;
//브루트포스니까 다시 바꿔줘야함
sudo[x][y] = 0;
c[x][i] = c2[y][i] = c3[square(x, y)][i] = false;
}
}
}
return false;
}
int main()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
scanf("%d", &sudo[i][j]);
if (sudo[i][j] != 0)
{
c[i][sudo[i][j]] = true;
c2[j][sudo[i][j]] = true;
c3[square(i, j)][sudo[i][j]] = true;
}
}
}
go(0);
return 0;
}
|
cs |
if (go(z + 1))
return true;
for문을 다 돌았는데도 숫자가 없다면 false가 반환될 것이고
돌아가서 그 값을 끈다.
z == 81이 되면 이제 모든 칸을 다 채운 것
돌아가면서 다 return true를 시켜야 하므로!!!
