백준 2580 : 스도쿠

문제 설명

---

몇칸이 비어있는 9x9 격자판이 주어졌을 때 해당 스도쿠를 채워 출력하는 문제.

---

 

 이 문제는 백트래킹을 사용하여 빈칸을 채워 스도쿠 퍼즐을 해결 할 수 있다. 각 행(row), 각 열(column)에 대해 숫자가 사용되었는지를 체크해주다. 또, 각 3x3 서브그리드에 대해 숫자가 사용되었는지도 체크해주어야한다. 다음 3가지를 각각 체크하며 비어있는 칸을 백트래킹을 이용하여 풀면 된다.

---

소스코드

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

using namespace std;

int chs[10][10], chg[10][10];
int chsq[10][10];
int m_sq[10][10];
int ch = 0;
vector <pair<int, int>> emp;

int sqnumjudge(int x, int y)
{
	if (0 <= x && x <= 2 && 0 <= y && y <= 2) return 1;
	if (0 <= x && x <= 2 && 3 <= y && y <= 5) return 2;
	if (0 <= x && x <= 2 && 6 <= y && y <= 8) return 3;

	if (3 <= x && x <= 5 && 0 <= y && y <= 2) return 4;
	if (3 <= x && x <= 5 && 3 <= y && y <= 5) return 5;
	if (3 <= x && x <= 5 && 6 <= y && y <= 8) return 6;

	if (6 <= x && x <= 8 && 0 <= y && y <= 2) return 7;
	if (6 <= x && x <= 8 && 3 <= y && y <= 5) return 8;
	if (6 <= x && x <= 8 && 6 <= y && y <= 8) return 9;

	return 0;
}

void place_magic_sq(int x)
{
	int i, j;
	if (x >= emp.size()) {
		ch = 1;
		return;
	}
	for (i = 1; i <= 9; i++) {
		int a = emp[x].first, b = emp[x].second;
		int nsq = sqnumjudge(a, b);
		if (chs[a][i] == 1) continue;
		if (chg[b][i] == 1) continue;
		if (chsq[nsq][i] == 1) continue;
		chsq[nsq][i] = 1;
		chg[b][i] = 1;
		chs[a][i] = 1;
		m_sq[a][b] = i;
		place_magic_sq(x + 1);
		if (ch == 1) return;
		chsq[nsq][i] = 0;
		chg[b][i] = 0;
		chs[a][i] = 0;
	}
	return;
}

int main()
{
	int i, j;
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			scanf("%d", &m_sq[i][j]);
			if (m_sq[i][j] == 0) emp.push_back({ i, j });
			else {
				chsq[sqnumjudge(i, j)][m_sq[i][j]] = 1;
				chs[i][m_sq[i][j]] = 1;
				chg[j][m_sq[i][j]] = 1;
			}
		}
	}
	place_magic_sq(0);
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			printf("%d ", m_sq[i][j]);
		}
		printf("\n");
	}
	return 0;
}

 

---

소스코드 설명

---

-변수 설명

 

• chs[10][10]: 각 행(row)에 대해 숫자가 사용되었는지를 나낸다.
• chg[10][10]: 각 열(column)에 대해 숫자가 사용되었는지를 나타낸다.
• chsq[10][10]: 각 3x3 서브그리드에 대해 숫자가 사용되었는지를 나타낸다.
• m_sq[10][10]: 스도쿠 격자를 나타내며, 숫자가 채워질 2차원 배열이다.
• ch: 스도쿠가 해결되었는지를 나타내는 플래그역할을 한다.
• emp: 빈칸의 좌표를 저장하는 벡터이다.

 

-함수 설명

 

• sqnumjudge(int x, int y) 함수 : 이 함수는 주어진 좌표 (x, y)가 어떤 3x3 서브그리드에 속하는지 판단한다. 스도쿠의 격자는 9개의 3x3 서브그리드로 나뉘며, 이 함수는 해당 좌표가 어느 서브그리드에 속하는지를 반환한다.
• place_magic_sq(int x) 함수 : 이 함수는 백트래킹을 사용하여 빈칸을 채우는 역할을 한다. 빈칸을 하나씩 채우면서, 해당 위치에 올 수 있는 숫자를 시도하고, 조건에 맞지 않으면 되돌아간다.