스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

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

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

예제 입력 및 출력

입력

0 3 5 4 6 9 2 7 8

7 8 2 1 0 5 6 0 9

0 6 0 2 7 8 1 3 5

3 2 1 0 4 6 8 9 7

8 0 4 9 1 3 5 0 6

5 9 6 8 2 0 4 1 3

9 1 7 6 5 2 0 8 0

6 0 3 7 0 1 9 5 2

2 5 8 3 9 4 7 6 0

 

출력

1 3 5 4 6 9 2 7 8

7 8 2 1 3 5 6 4 9

4 6 9 2 7 8 1 3 5

3 2 1 5 4 6 8 9 7

8 7 4 9 1 3 5 2 6

5 9 6 8 2 7 4 1 3

9 1 7 6 5 2 3 8 4

6 4 3 7 8 1 9 5 2

2 5 8 3 9 4 7 6 1

소스 코드

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

int map[9][9];
typedef struct pos {
	int x;
	int y;
};
//0인 원소의 위치 따로 저장해둔 벡터
vector<pos> arr0; 

bool checkgaro(int garo, int num) {
	for (int i = 0; i < 9; i++) {
		//num이 있으면 false 반환
		if (map[garo][i] == num)
			return false;
	}
	return true;
}

bool checksero(int sero, int num) {
	for (int i = 0; i < 9; i++) {
		//num이 있으면 false 반환
		if (map[i][sero] == num)
			return false;
	}
	return true;
}

bool checksquare(int garo, int sero, int num) {
	int gstart = 3 * (garo / 3), sstart = 3 * (sero / 3); //사각형 왼쪽맨위 인덱스값 구하기
	for (int i = gstart; i < gstart + 3; i++) {
		for (int j = sstart; j < sstart + 3; j++) {
			//num이 있으면 false 반환
			if (map[i][j] == num) 
				return false;
		}
	}
	return true;
}

void setsudoku(int idx) {
	//다 돌았으면 출력 후 반환
	if (idx == arr0.size()) {
		for (int a = 0; a < 9; a++) {
			for (int b = 0; b < 9; b++)
				printf("%d ", map[a][b]);
			printf("\n");
		}
		exit(0);
	}

	//현재 idx가능한 수 넣어준다
	for (int i = 1; i < 10; i++) {
		int x = arr0[idx].x;
		int y = arr0[idx].y;
		//세가지 조건을 모두 통과하면 수를 넣는다
		if (checkgaro(x, i) && checksero(y, i) && checksquare(x, y, i)) {
			map[x][y] = i;
			setsudoku(idx+1); //값을 넣고 다음 idx에 수를 넣는 함수 호출
			map[x][y] = 0; //return하면 원래대로 초기화
		}
	}
}

int main(void) {
	pos tmp;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &map[i][j]);
			//스도쿠에서 0인 위치는 따로 저장
			if (map[i][j] == 0) {
				tmp.x = i;
				tmp.y = j;
				arr0.push_back(tmp);
			}
		}
	}
	setsudoku(0);
}

문제 풀이

• • checkgaro(), checksero(), checksquare() 함수 반환 값이 모두 true이면 해당 값을 넣을 수 있으므로 값을 설정하고 다음번 idx의 재귀 함수를 호출한다.

  • 재귀 함수에서 넣을 값이 없어 함수가 반환되면 설정했던 값을 다시 0으로 바꿔주고 다음번 가능한 값을 찾는다.

 

문제 출처: https://www.acmicpc.net/problem/2580