[백준] 2580번 스도쿠

2580번: 스도쿠

백트래킹으로 푸는 문제이다.

 

1. 같은 행에 숫자 N이 없을 때

2. 같은 열에 숫자 N이 없을 때

3. 같은 3*3 칸에 숫자 N이 없을 때

 

이 세 조건을 충족시키면 다음 빈칸을 채우러 가고

만족시키지 못한다면 N+1을 하여 다음 숫자를 넣어본다.

N을 9까지 증가시켰는데 빈칸을 채우는데 실패하면 이전 빈칸의 숫자가 잘못된 것이므로 돌아간다.

 

모든 빈칸이 채워지는 경우엔 finish에 표시한 후 모두 빠져나와 출력시키면 끝

#include <iostream>
#include <vector>
using namespace std;
int sudokuboard[9][9] = { 0 }, finish = 0;
vector <pair<int, int> > v;

void sudoku(int idx) {
	if (idx == v.size()) {
		finish = 1;
		return; //모든 빈칸을 채워주었다면 종료
	}
	int row = v[idx].first, col = v[idx].second;
	
	int box_row = 0, box_col = 0;
	for (int N = 1; N <= 9; N++) {
		int ok = 0;
		sudokuboard[row][col] = N;
		for (int i = 0; i < 9; i++) {
			if (i != col && sudokuboard[row][i] == N) { //같은 행에 숫자 N이 있는지 확인
				ok = 1;
				break;
			}
			if (i != row && sudokuboard[i][col] == N) { //같은 열에 숫자 N이 있는지 확인
				ok = 1;
				break;
			}
		}
		if (ok == 0) { //위 조건도 만족한다면
			box_row = (row / 3 + 1) * 3;
			box_col = (col / 3 + 1) * 3;
			for (int i = box_row - 3; i < box_row; i++) { //같은 3X3 박스에 숫자 N이 있는지 확인
				for (int j = box_col - 3; j < box_col; j++) {
					if (i != row && j != col && sudokuboard[i][j] == N) {
						ok = 1;
						break;
					}
				}
				if (ok == 1) break;
			}
		}

		if (ok == 0) sudoku(idx + 1); //세가지 조건을 모두 충족시킨다면 다음 빈칸을 찾는다
		if (finish == 1) return; //finish가 1이면 모든 빈칸을 채웠다는 뜻이므로 종료

	} //ok가 0이 아닌 경우 다음 숫자 N+1을 넣어본다
	sudokuboard[row][col] = 0; //채우는데 실패하면 다시 빈칸으로 만들어주고 이전 빈칸으로 돌아가서 다시 한다
}

int main() {
		for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> sudokuboard[i][j];
			if (sudokuboard[i][j] == 0) v.push_back(pair <int, int>(i, j)); //빈 칸일 경우만 벡터에 담아둔다
		}
	}

	sudoku(0);

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

	return 0;
}