[Codeup] 3530. 스도쿠

1. 문제 링크

https://codeup.kr/problem.php?id=3530

코드업

 

2. 문제 풀이

빈칸의 위치를 모두 저장해 둔다.

이후, 각 행과 열, 자신이 속한 3*3 사각형 내외 안에 들어갈 수 있는 후보에 해당하는 숫자인지 체크를 진행한다.

 

만족하면, 해당 숫자를 임시 확정 짓고, 다음 칸으로 이동시켜, 탐색을 계속 이어나간다.

이 과정이 마지막까지 모두 되었다면, 스도쿠가 완성된 것이다.

 

만약, 이 과정에서 임시 확정 시킨 숫자의 문제가 있었다면, 빈칸 처리 후 다른 숫자로 재시도한다.

각 행과 열, 3x3 규칙에 안맞는 후보를 미리 버려두어 탐색의 후보를 줄이는게 핵심이다.

 

3. 아이디어

1. 빈칸의 위치와 빈칸의 개수를 계산한다.
2. 각 행과 열 그리고 자신이 속한 3*3 사각형 내외 안에 들어갈 수 있는 후보에 해당하는지 체크하는 작업을 함수로 만든다..
    2-1. x,y에 대해서 0 <= i < 9 일 때, board[x][i], board[i][y]를 검사하면 각 행과 열을 체크할 수 있다.
    2-2. 좌표의 시작점을 0-based로 처리하면, 각 9칸의 구역을 아래와 같은 공식으로 나눌수 있다.
      (1,1) ~ (3,3)과 같은 1-based 기반을 (0,0) ~(2,2) 0-based로 처리한다.
    2-3. 이렇게 하면 row = (x / 3) * 3, col = (y / 3) * 3로, 각 영역의 시작점을 쉽게 구할 수 있다.
    2-4. 이중 for문으로 사각형에 속해 있는 9칸을 탐색 시키면 된다.
3. 탐색할 때, 해당 칸의 숫자를 확정지을 수 있으면 재귀적으로 다음 칸 탐색을 진행한다.
    3-1. 탐색 과정에서 현재 탐색 중인 빈칸의 번째수가 빈칸의 수와 같으면, 스도쿠 완성이 확정된다.

 

 

4. 구현

C++ Source Code

#include <iostream>
using namespace std;
int sudoku[10][10];
int blink_index[81][2];
int blink_count = 0;

bool check(int x, int y, int value)
{
	bool cnt[10] = { 0 }; // 각 숫자 값 카운트 체크
	int row = (x / 3) * 3; // 보드 판을 기준으로 1,2,3,4,5,6,7,8,9 영역 중 어디인지 나타냄.
	int col = (y / 3) * 3;
	for (int i = 0; i < 9; i++) // 각 행과 열 숫자 카운트
	{
		if (cnt[sudoku[x][i]] == 0) cnt[sudoku[x][i]] = true;
		if (cnt[sudoku[i][y]] == 0) cnt[sudoku[i][y]] = true;
	}

	for (int i = row; i < row + 3; i++) // 3*3칸 만큼 확인
	{
		for (int j = col; j < col + 3; j++) // 3*3칸 만큼 확인
		{
			if (cnt[sudoku[i][j]] == 0) cnt[sudoku[i][j]] = true;
			if (cnt[sudoku[i][j]] == 0) cnt[sudoku[i][j]] = true;
		}
	}
	
	return !cnt[value]; // 값이 있으면 해당 숫자는 후보에서 제외.
}
bool back(int current_blink)
{
	if (blink_count == current_blink)
	{
		return true;
	}

	int x = blink_index[current_blink][0];
	int y = blink_index[current_blink][1];

	for(int k=1; k<=9; k++)
	{
		if (check(x,y,k)) // 들어갈 수 있는 후보에 해당 하는지 체크
		{
			sudoku[x][y] = k;
			if (back(current_blink + 1)) // 뒤 모든 값을 파고 들어 성공하면 스도쿠 완성
			{
				return true;
			}
			sudoku[x][y] = 0; // 실패시 다시 빈칸 처리 후 재시도
		}
	}
	return false;
}



int main(void)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> sudoku[i][j];
			if (sudoku[i][j] == 0) // 0인 경우 담기
			{
				blink_index[blink_count][0] = i;
				blink_index[blink_count][1] = j;
				blink_count++;
			}
		}
	}

	if (back(0))
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << sudoku[i][j] << " ";
			}
			cout << endl;
		}
	}
	else
	{
		cout << "Not Possible";
	}
}