백준 2580: 스도쿠

문제 요약

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

문제 분류

• 백트래킹

문제 풀이

1~9의 합이 45임을 이용하여 숫자의 중복 여부를 검사하려했는데 시간초과로 계속 실패하였다.

12095번: 가장 오래 걸리는 스도쿠
따라서 12095번의 소스코드를 일부 참고하였다.

여기서는 bool타입의 배열을 행, 열, 구역의 총 3가지로 선언하여 각 배열에서 어떠한 숫자가 사용되었는지 확인한다. 예를 들어 horizen[4][5]가 true일 경우 4행에서 5라는 숫자가 사용되어있음을 의미한다.

배열을 탐색하던 중 0을 만나서 어떠한 값 i를 넣으려고 할때에, horizen[x][i], vertical[y][i], area[(x / 3) * 3 + (y / 3)][i]가 모두 false인 경우에만 값을 넣을 수 있다.

이 경우에 값을 넣고 계속해서 탐색을 진행하는데, 탐색 완료시 true를 반환하게 하는것으로 탐색완료 여부를 가늠한다. false가 반환되었을 경우 탐색이 불가한 것이므로 할당했던 배열의 값들을 모두 회수하고 다음 i값으로 계속해서 탐색해 나가면 된다.

알고 보면 어렵지 않은 문제이다.

풀이 코드

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

using namespace std;

int ary[9][9];
bool horizen[9][10];
bool vertical[9][10];
bool area[9][10];

bool dfs(int idx) {
	if (idx == 81) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				printf("%d ", ary[i][j]);
			printf("\n");
		}
		return true;
	}
	int x = idx / 9, y = idx % 9;
	if (ary[x][y] != 0)
		return dfs(idx + 1);
	for (int i = 1; i <= 9; i++) {
		if (!horizen[x][i] && !vertical[y][i] && !area[(x / 3) * 3 + (y / 3)][i]) {
			horizen[x][i] = vertical[y][i] = area[(x / 3) * 3 + (y / 3)][i] = true;
			ary[x][y] = i;
			if (dfs(idx + 1)) return true;
			horizen[x][i] = vertical[y][i] = area[(x / 3) * 3 + (y / 3)][i] = false;
			ary[x][y] = 0;
		}
	}
	return false;
}

int main()
{
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &ary[i][j]);
			horizen[i][ary[i][j]] = true;
			vertical[j][ary[i][j]] = true;
			area[(i / 3) * 3 + (j / 3)][ary[i][j]] = true;
		}
	}
	dfs(0);
	return 0;
}