스도쿠

문제

백준 2580번 - 스도쿠

언어

JavaScript

순서도

주어진 스도쿠 판에서 빈 칸 찾기
주어진 스도쿠 판에서 주어진 칸들을 이용해서 행, 열, 격자 배열에 값 채우기
빈 칸들에 대해서 가능한 모든 경우를 만들어보기
각 경우에 대해서 스도쿠의 규칙을 어기지 않는 경우 찾아서 출력하기

문제 풀이 step 1

본 문제는 스도쿠 문제를 푸는 문제입니다.
- 백준 9663번 - N-Queen 풀이 와 유사한 방식으로 풀 수 있습니다.
우선, 스도쿠에는 몇 가지 규칙이 존재합니다.
- 각 행에는 1 부터 9 까지의 숫자가 한 번씩만 나타나야 합니다.
- 각 열에는 1 부터 9 까지의 숫자가 한 번씩만 나타나야 합니다.
- 굵은 선으로 구분되어 있는 3 x 3 격자 안에도 1 부터 9 까지의 숫자가 한 번씩만 나타나야 합니다.

문제 풀이 step 2

재귀 함수를 이용해서 위의 스도쿠의 규칙을 모두 지키며 모든 빈칸을 채울 수 있는 경우 중에서 하나를 출력하면 정답입니다.
우선, 주어진 스도쿠 문제에서 빈 칸 정보를 수집합니다.
- 배열에 좌표 형식으로 담으면 됩니다.

그리고 각 행, 각 열, 굵은 선으로 구분되어 있는 3 x 3 격자들에 대해서 1 부터 9 까지의 숫자 중 어떤 숫자가 채워져 있는지에 대한 정보를 수집합니다.

이는 나중에 재귀함수를 호출할 때 다음에 채우려는 숫자가 위에서 알아본 스도쿠의 규칙을 어기지 않는지 검사하기 위한 용도로 사용됩니다.
각 행과 각 열에 대한 정보는 별다른 좌표에 대한 조작이 필요 없어서 넘어가고,

굵은 선으로 구분되어 있는 3 x 3 격자에 대한 정보는 좌표에 대한 조작이 필요해서 그 부분만 알아보겠습니다.

const arr = [
	"[0, 0], [0, 1], [0, 2] | [0, 3], [0, 4], [0, 5] | [0, 6], [0, 7], [0, 8]",
	"[1, 0], [1, 1], [1, 2] | [1, 3], [1, 4], [1, 5] | [1, 6], [1, 7], [1, 8]",
	"[2, 0], [2, 1], [2, 2] | [2, 3], [2, 4], [2, 5] | [2, 6], [2, 7], [2, 8]",
	" ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ",
	"[3, 0], [3, 1], [3, 2] | [3, 3], [3, 4], [3, 5] | [3, 6], [3, 7], [3, 8]",
	"[4, 0], [4, 1], [4, 2] | [4, 3], [4, 4], [4, 5] | [4, 6], [4, 7], [4, 8]",
	"[5, 0], [5, 1], [5, 2] | [5, 3], [5, 4], [5, 5] | [5, 6], [5, 7], [5, 8]",
	" ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ",
	"[6, 0], [6, 1], [6, 2] | [6, 3], [6, 4], [6, 5] | [6, 6], [6, 7], [6, 8]",
	"[7, 0], [7, 1], [7, 2] | [7, 3], [7, 4], [7, 5] | [7, 6], [7, 7], [7, 8]",
	"[8, 0], [8, 1], [8, 2] | [8, 3], [8, 4], [8, 5] | [8, 6], [8, 7], [8, 8]",
];

각 좌표를 [i, j] 라고 할 때, 각 좌표에 “3 x (parseInt(i / 3)) + parseInt(j / 3)” 을 적용시키면 다음과 같습니다.

const arr = [
	"[0], [0], [0] | [1], [1], [1] | [2], [2], [2]",
	"[0], [0], [0] | [1], [1], [1] | [2], [2], [2]",
	"[0], [0], [0] | [1], [1], [1] | [2], [2], [2]",
	" ㅡㅡㅡㅡㅡㅡ    ㅡㅡㅡㅡㅡㅡㅡ    ㅡㅡㅡㅡㅡㅡ ",
	"[3], [3], [3] | [4], [4], [4] | [5], [5], [5]",
	"[3], [3], [3] | [4], [4], [4] | [5], [5], [5]",
	"[3], [3], [3] | [4], [4], [4] | [5], [5], [5]",
	" ㅡㅡㅡㅡㅡㅡ    ㅡㅡㅡㅡㅡㅡㅡ    ㅡㅡㅡㅡㅡㅡ ",
	"[6], [6], [6] | [7], [7], [7] | [8], [8], [8]",
	"[6], [6], [6] | [7], [7], [7] | [8], [8], [8]",
	"[6], [6], [6] | [7], [7], [7] | [8], [8], [8]",
];

이렇게 각 좌표에 대해서 약간의 조작을 통해서 굵은 선으로 구분되어 있는 3 x 3 격자 안의 정보도 수집합니다.

문제 풀이 step 3

위에서 수집한 정보를 바탕으로 재귀함수를 호출합니다.
매 호출시 각 빈 칸에 1 부터 9 까지의 숫자를 넣어보고,
행, 열, 3 x 3 격자 배열을 이용해서 넣은 숫자가 스도쿠의 규칙을 어기는지 검사해가며,
규칙을 어길 경우에는 더 이상 호출하지 않고, 규칙이 지켜질 경우에만 다음 호출을 이어갑니다.
그렇게 스도쿠의 규칙을 다 지켜가며 모든 빈 칸에 숫자를 채웠을 때의 스도쿠 판의 상태를 출력하면 정답입니다.
스도쿠 판을 채우는 방법이 여럿인 경우에는 그 중 하나만 출력해야 하므로, 그 시점에서 재귀 호출을 중지합니다.
추가 설명은 주석으로 작성하겠습니다.

후기

꼭 다시 풀어볼 문제입니다.
“백준 9663번 - N-Queen” 문제와 로직의 흐름이 상당히 유사합니다.
- N-Queen 문제에서는 매번 호출 시 가로, 세로, 대각선을 검사하고, 규칙을 어기지 않는 경우에만 다음 호출을 이어갑니다.
- 스도쿠 문제에서는 매번 호출 시 행, 열, 3 x 3 격자를 검사하고, 규칙을 어기지 않는 경우에만 다음 호출을 이어갑니다.
N-Queen 문제에서 많은 시행 착오를 겪어서인지 스도쿠 문제는 어렵지 않게 해결할 수 있었던 것 같습니다.
두 문제는 브루트포스 유형의 문제이면서, 더 이상의 의미 없는 호출을 하지 않는 백 트래킹 유형의 문제이기도 했습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

let res = "";

const rec = (arr, n, blanks, row, col, grid, depth) => {
	// 방법을 찾았다면, 호출 중지
	if (res !== "") return;

	if (depth === n) {
		// 출력 형식에 맞게 문자열 생성
		res = arr.map((v) => v.join(" ")).join("\n");
		return;
	}

	const [x, y] = blanks[depth];
	for (let i = 1; i < 10; i++) {
		// 행, 열, 3 x 3 격자 검사
		if (row[x][i] === true) continue;
		if (col[y][i] === true) continue;
		if (grid[3 * parseInt(x / 3) + parseInt(y / 3)][i] === true) continue;

		row[x][i] = true;
		col[y][i] = true;
		grid[3 * parseInt(x / 3) + parseInt(y / 3)][i] = true;
		arr[x][y] = i;

		// 스도쿠의 규칙을 지키는 경우 다음 호출을 이어감
		rec(arr, n, blanks, row, col, grid, depth + 1);

		row[x][i] = false;
		col[y][i] = false;
		grid[3 * parseInt(x / 3) + parseInt(y / 3)][i] = false;
		arr[x][y] = 0;
	}
};

const solution = (input) => {
	const arr = input.map((v) => v.split(" ").map(Number));

	// 빈칸 찾기
	const blanks = [];
	for (let i = 0; i < 9; i++) {
		for (let j = 0; j < 9; j++) {
			if (arr[i][j] === 0) blanks.push([i, j]);
		}
	}
	const n = blanks.length;

	// 행, 열, 3 x 3 격자 정보 수집
	const row = Array.from({length: 10}, () => Array(10).fill(false));
	const col = Array.from({length: 10}, () => Array(10).fill(false));
	const grid = Array.from({length: 10}, () => Array(10).fill(false));
	for (let i = 0; i < 9; i++) {
		for (let j = 0; j < 9; j++) {
			if (arr[i][j] === 0) continue;

			row[i][arr[i][j]] = true;
			col[j][arr[i][j]] = true;
			grid[3 * parseInt(i / 3) + parseInt(j / 3)][arr[i][j]] = true;
		}
	}

	rec(arr, n, blanks, row, col, grid, 0);

	return res;
};

console.log(solution(input));