[BOJ] 2580 스도쿠 - Back Tracking

스도쿠 퍼즐은 다음과 같은 규칙을 가진다.

한칸에 1부터 9의 숫자를 넣을수 있다.

가로 줄에 같은 숫자가 존재 하면 안된다.

세로 줄에 같은 숫자가 존재 하면 안된다.

가로 세로 크기가 3인 큰 정사각형으로 잘랐을때, 하나의 큰 정사각형 내에 1부터 9의 숫자가 하나씩 존재해야 한다.

 

스도쿠 퍼즐

 

그렇다면,

어떠한 Row에 숫자가 존재하는지 간단하게 검사할 수 있다.

또, 어떠한 Col에 해당 숫자가 존재하는지 간단하게 검사할 수 있다.

가로세로 크기 3인 큰 정사각형 내에 숫자가 존재하는지 간단하게 검사할 수 있다. 

퍼즐의 빈칸에 대해, 

이 3가지 배열 조건을 검사하고, 만족하는 경우 숫자를 기입하며 Back Tracking 하면 쉽게 답을 찾을 수 있다.

코드를 구현하면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>

int     sudokuboard    [9][9];
bool    SectorCandidate[3][3][10]      = { false, };
bool    RowCandidate   [9][10]         = { false, };
bool    ColCandidate   [9][10]         = { false, };
std::vector<std::pair<int, int>> EmptySpaces;

bool BackTracking_Sudoku(size_t EmptySpaceIdx, size_t MaxEmptySpace)
{
	if (EmptySpaceIdx == MaxEmptySpace)
		return true;

	int CurXpos = EmptySpaces[EmptySpaceIdx].first;
	int CurYpos = EmptySpaces[EmptySpaceIdx].second;

	int SectorIdxX = CurXpos / 3;
	int SectorIdxY = CurYpos / 3;

	for (int i = 1; i <= 9; ++i)
	{
		if (SectorCandidate[SectorIdxY][SectorIdxX][i] == true ||
			RowCandidate[CurYpos][i] == true                   ||
			ColCandidate[CurXpos][i] == true)
			continue;
		
		sudokuboard                   [CurYpos][CurXpos]            = i;
		SectorCandidate               [SectorIdxY][SectorIdxX][i]   = true;
		RowCandidate                  [CurYpos][i]                  = true;
		ColCandidate                  [CurXpos][i]                  = true;

		if (BackTracking_Sudoku(EmptySpaceIdx + 1, MaxEmptySpace) == true)
			return true;

		SectorCandidate               [SectorIdxY][SectorIdxX][i]   = false;
		RowCandidate                  [CurYpos][i]                  = false;
		ColCandidate                  [CurXpos][i]                  = false;
	}

	return false;

}





int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin.tie(nullptr);

	for (int Y = 0; Y < 9; ++Y)
	for (int X = 0; X < 9; ++X)
	{
		int Num;
		std::cin >> Num;

		sudokuboard[Y][X] = Num;

		if (Num == 0)
		{
			EmptySpaces.push_back(std::pair<int, int>(X, Y));
			continue;
		}

		ColCandidate              [X][Num]            = true;
		RowCandidate              [Y][Num]            = true;
		SectorCandidate           [Y / 3][X / 3][Num] = true;
	}

	BackTracking_Sudoku(0, EmptySpaces.size());

	for (int Y = 0; Y < 9; ++Y)
	{
		std::cout << sudokuboard[Y][0];
		for (int X = 1; X < 9; ++X)
		{
			std::cout << ' ' << sudokuboard[Y][X];
		}
		std::cout << '\n';
	}

}