문제 간략 설명

9×9 크기의 스도쿠 보드가 주어진다. 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채워야 한다. 빈 칸은 0으로 표시되어 있으며, 모든 빈 칸을 채워 완성된 스도쿠를 출력한다.

풀이 방법

  1. 칸을 순회하면서 아직 채워지지 않은 칸에 대해 flag 배열을 사용하여 그 칸에 들어갈 수 있는 숫자들을 저장한다.
  2. 가능한 숫자를 넣고 다음 칸으로 넘어간다.
  3. 불가능한 상황이 오면 백트래킹으로 돌아가서 다른 숫자를 시도한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<string> map(9);

void backtracking(int x, int y)
{
	if (x == 9) {
		if (y == 8) {
			for (int i = 0; i < 9; i++)
				cout << map[i] << endl;
			exit(0);
		}
			
		x = 0;
		y++;
	}

	if (map[y][x] != '0') {
		backtracking(x + 1, y);
		return ;
	}

	bool flag[10];

	for (int i = 0; i < 10; i++)
		flag[i] = true;

	for (int i = 0; i < 9; i++) {
		flag[map[y][i] - '0'] = false;
		flag[map[i][x] - '0'] = false;
		flag[map[(y / 3) * 3 + i / 3][(x / 3) * 3 + i % 3] - '0'] = false;
	}

	for (int i = 1; i < 10; i++) {
		if (flag[i]) {
			map[y][x] = i + '0';
			backtracking(x + 1, y);
			map[y][x] = '0';
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 9; i++)
		cin >> map[i];

	backtracking(0, 0);

	return 0;
}

Key Points