2580번

1.문제

2.풀이

1. 빈칸(0)에만 숫자를 넣고 유효성 검사를 해야하므로 빈칸의 인덱스를 배열에 기록해둔다.

   1-1.이를 위해 좌표쌍을 가진 point라는 int형 pair를 선언, points라는 배열에 넣어준다.

2. cnt변수에 0의 갯수를 기록해둔뒤, 재귀함수를 돌때마다 size변수의 크기를 0부터 증가시켜 cnt == size가 될때 즉, 모든 스도쿠 판이 채워질경우 종료한다.

3. 1부터 9까지 for문을 돌며 빈칸에 넣어 check를 통해 유효성 검사를 한다.

   3-1. 만약 유효성 검사를 통과한다면 해당 좌표에 알맞은 숫자가 들어간것이므로 스도쿠판에 숫자를 넣어주고 size를 증가시켜준다.

   3-2.만약 유효성 검사를 통과하지 못했다면 계속해서 for문을 돌게되고 만약 9까지 돌았음에도 통과하지못했다면 해당 케이스에서 알맞는 숫자가 없는것이므로 백트래킹을 할수 있도록 해당 좌표의 값을 0으로 돌려준다. 그래야 실패지점을 만날경우 다시 뒤로 가면서 새로운 값을 시도해 최적의 값을 찾을 수 있다.

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int table[9][9];
int cnt = 0;
bool finish = false;
vector<pair<int, int>> points;

void print_result() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << table[i][j] << " ";
		}
		cout << '\n';
	}
}

bool check(int x, int y, int value) {

	for (int i = 0; i < 9; i++) { //가로 + 세로 검사
		if (table[x][i] == value || table[i][y] == value) {
			return 0;
		}
	}

	for (int i = (x / 3) * 3; i <= 3 * (x / 3) + 2; i++) {
		for (int j = (y / 3) * 3; j <= 3 * (y / 3) + 2; j++) {
			if (table[i][j] == value) {
				return 0;
			}
		}
	}

	return value;
}

void sdk(int size) {
	if (size == cnt) {//모든 스도쿠판을 채운경우
		print_result();
		finish = true; //스도쿠판을 다 채웠으므로 이전 재귀함수들의 반복문을 계속 돌릴필요가 없으므로 중단 플래그를 새워준다.
		return;
	}

	for (int i = 1; i <= 9; i++) {
		if (finish == true) {
			return;
		}
	
		if (check(points[size].first, points[size].second, i)) {
			table[points[size].first][points[size].second] = i;
			sdk(size + 1);
		}
	}
	table[points[size].first][points[size].second] = 0;
	
}

int main(void) {

	int n;

	pair<int, int> point;

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> n;
			table[i][j] = n;
			if (n == 0) {
				point.first = i;
				point.second = j;
				cnt++;
				points.push_back(point); //0인값의 좌표를 가진 쌍 point를 points배열에 담는다.
			}
		}

	}
	sdk(0);
}

3.배운점

특정 인덱스의 좌표를 기록하는경우 pair함수를 써서 쉽게 기록 할 수 있다.
pair<int, int> p