[백준]2580_스도쿠

https://www.acmicpc.net/problem/2580

Solved

✔ 스도쿠 빈칸 채우는 문제.
✔ 백트래킹
✔ 빈칸의 정보를 blank 라는 벡터에 좌표값과 함께 저장한다
✔ dfs 재귀 중 방문한 좌표의 수와 blank의 수가 같아질 때 정답을 출력한다.
✔ 3*3 범위 내에서 해당 값이 올바른 값인지 확인 할 때

int squareX = (x/3)*3;
int squareY = (y/3)*3:

으로 squareX ~ squareX+3, squareY ~ squareY+3 사이의 값을 비교하면 된다.

using namespace std;
#include <iostream>
#include <vector>

int board[9][9];
vector<pair<int, int>> blank;
bool answer = false;

int main(){
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0)
				blank.push_back(make_pair(i, j));
		}
	}
	solution(0);

}

bool possible(int value, int idx) {
	int x = blank[idx].first;
	int y = blank[idx].second;
	for (int i = 0; i < 9; i++) {
		if (board[x][i] == value)
			return false;
		if (board[i][y] == value)
			return false;
	}
	//0 3 6
	int squareX = (x / 3) * 3;
	int squareY = (y / 3) * 3;
	for (int i = squareX; i < squareX + 3; i++)
		for (int j = squareY; j < squareY + 3; j++)
			if (board[i][j] == value)
				return false;
	return true;
}
void solution(int idx) {
	if (answer == true) return;
	if (idx == blank.size()) {
		answer = true;
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << board[i][j] << ' ';
			}
			cout << '\n';
		}
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (possible(i, idx) == true) {
			int x = blank[idx].first;
			int y = blank[idx].second;
			board[x][y] = i;
			solution(idx + 1);
			if (answer == true) return;
			board[x][y] = 0;
		}
	}
}