[백준][2580][C++] 스도쿠

링크

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

2580번: 스도쿠

해설

백트래킹을 이용한 간단한 문제입니다.

방법 자체를 생각하는 건 어렵지 않으나 코드를 어떻게 짤지를 고민하는 게 더 중요해 보입니다.

 

제가 짠 코드는 각 행, 열, 사각형 에 대한 bool 배열을 만들어두고 3개다 true 이면 넣고 다음으로 넘어가는 방식입니다.

그 후 TABLE 에서 0인 칸을 찾아서 1~9 까지 다 넣어보고 하나도 안되면 false 로 뒤로 돌아가고 가능하면 더 가봅니다.

 

81번째까지 다 검사했는데도 0이 없으면 완성된 것이므로 해결!

 

코드

#include <iostream>
using namespace std;

int TABLE[81];
bool Y[9][9], X[9][9], square[9][9];

bool sudoku(int _n) {
	for (int i = _n; i < 81; ++i) {
		if (TABLE[i] == 0) {
			int x = i % 9, y = i / 9;
			for (int j = 0; j < 9; ++j) {
				if (X[x][j] && Y[y][j] && square[(y / 3) * 3 + x / 3][j]) {
					TABLE[i] = j + 1;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = false;
					if (sudoku(i + 1))
						return true;
					X[x][j] = Y[y][j] = square[(y / 3) * 3 + x / 3][j] = true;
				}
			}
			TABLE[i] = 0;
			return false;
		}
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < 9; ++i)
		for (int j = 0; j < 9; ++j)
			Y[i][j] = X[i][j] = square[i][j] = true;
	

	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			int inp;
			cin >> inp;
			TABLE[9 * i + j] = inp;
			if (inp != 0) {
				--inp;
				Y[i][inp] = false;
				X[j][inp] = false;
				square[(i / 3) * 3 + j / 3][inp] = false;
			}
		}
	}



	sudoku(0);

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

	return 0;
}