백준 2580. 스도쿠

알고리즘 중급 문제 중 531 - 브루트 포스 - 재귀(연습)

스도쿠

1. 간단 설명

---

백트래킹을 이용해 스도쿠를 풀이하는 문제

스도쿠 풀이 방법은 생략

2. 알고리즘

---

간단할 줄 알았는데 생각보다 직접 구현하려니 복잡했다

먼저 간단히 생각해본 방법으로는

for y 1-9 : 
	for x 1-9 : 
		map[y][x]가 빈칸이라면 1-9 사이의 숫자를 넣어본다
		해당 숫자를 넣은 뒤, 스도쿠 룰에 따라 검증해본다
			검증에 실패했다면 되돌아온다
		만약 검증에 통과했다면 다음 빈칸을 찾는다

이런 식으로 구현하고자 했다

막힌 부분

1. 빈칸에 숫자를 넣어 스도쿠 룰을 검증 시, 셀 검증을 어떻게 구현할 것인가?

2. 백트래킹을 구체적으로 어떻게 구현할 것인가?

이 두부분에서 막혔다

그리고 잘못 구현한 부분은

행 및 열 검증을 수행할 때, 1~9의 합이 45가 되는 방식을 이용했는데,

이런식으로 구현하니 빈칸이 두개인 경우 오류가 발생했다

이러한 부분들을 수정한 버전

1. 전체 스도쿠 맵을 입력받는다
	1-1. 맵을 입력 받으면서, 빈칸(0)인 부분은 blank에 기록해둔다
2. 백트래킹을 수행한다
	2-1. 답을 이미 찾았다면 리턴
	2-2. 모든 빈칸을 채웠다면 스도쿠 맵을 출력 후 종료한다
	2-3. 1~9 사이에 가능한 숫자를 넣어본 뒤, 검증한다
		2-3-1. 검증을 통과했다면, map[y][x]에 해당 수를 기록한뒤 재귀호출한다
		2-3-2. 재귀에서 돌아왔다면, 검증에 실패한 것이므로 다시 빈칸(0)으로 채워둔다

필요 변수

• 스도쿠 전체 맵 int map[10][10]
• 빈칸의 좌표를 저장할 vector<pair<int, int>> blank
• y, x 칸에 val을 넣었을 때 스도쿠 룰을 만족하는지 검증할 bool check(int y, int x, int val) 함수
• 정답을 찾았다면 재귀탐색을 중단할 플래그 bool answer_flag

4. 소스코드

---

#include <iostream>
#include <vector>

using namespace std;

int map[10][10];
vector<pair<int, int>> blank;
bool answer_flag = false;

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	for (int y = 1; y <= 9; y++) {
		for (int x = 1; x <= 9; x++) {
			cin >> map[y][x];
			if (map[y][x] == 0) {
				blank.push_back(make_pair(y, x));
			}
		}
	}
}

// y, x에 val을 넣어도 스도쿠 룰에 적합한지 판단하는 함수
bool check(int blank_y, int blank_x, int blank_val) {
	// 행 검증
	for (int x = 1; x <= 9; x++) {
		if(blank_val == map[blank_y][x])
			return false;
	}

	// 열 검증
	for (int y = 1; y <= 9; y++) {
		if( blank_val == map[y][blank_x])
			return false;
	}

	// 셀 검증
	int cell_row = ((blank_y - 1) / 3) * 3 + 1; // 셀은 1부터 시작했으므로 이 부분에 주의한다
	int cell_col = ((blank_x - 1) / 3) * 3 + 1;

	for (int y = 0; y < 3; y++) {
		for (int x = 0; x < 3; x++) {
			if (map[cell_row + y][cell_col + x] == blank_val) {
				return false;
			}
		}
	}

	return true;
}

void recursive(int level) {
	if (answer_flag == true) return;
	if (level == blank.size()) {
		for (int y = 1; y <= 9; y++) {
			for (int x = 1; x <= 9; x++) {
				cout << map[y][x] << " ";
			} cout << endl;
		}
		answer_flag = true;
		return;
	}

	// 1~9 중 가능한 숫자 넣어보기
	for (int i = 1; i <= 9; i++) {
		int yy = blank[level].first;
		int xx = blank[level].second;
		if (check(yy, xx, i)) {
			map[yy][xx] = i;
			recursive(level + 1);
			map[yy][xx] = 0;
		}
	}

}

int main() {
	Input();
	recursive(0);
	return 0;
}