스도쿠란 무엇인가?
스도쿠는 9×9 크기의 숫자 퍼즐로, 전체 격자는 다시 3×3 크기의 작은 상자(박스) 9개로 나뉩니다. 부분적으로 채워진 스도쿠 그리드가 주어졌을 때 이를 해결하려면 다음 두 가지 기본 규칙을 반드시 지켜야 합니다.
- 숫자는 반드시 1부터 9까지의 숫자만 사용해야 합니다.
- 같은 숫자는 하나의 행, 하나의 열, 그리고 하나의 3×3 박스 안에서 중복될 수 없습니다.
백트래킹(Backtracking) 접근 방식
이 문제는 백트래킹 알고리즘을 사용하면 효과적으로 해결할 수 있습니다. 백트래킹의 핵심 아이디어는 다음과 같습니다.
- 빈 칸을 찾아 1부터 9까지의 숫자를 하나씩 넣어 봅니다.
- 숫자를 채운 후 해당 위치에 그 숫자가 유효한지 검사합니다.
- 유효하지 않다면 다른 숫자를 시도합니다.
- 1부터 9까지 모든 숫자를 시도했는데도 유효한 숫자를 찾지 못하면, 이전 단계로 되돌아가(백트래킹) 다른 선택지를 탐색합니다.
알고리즘 설계
스도쿠 솔버를 구현하기 위해 다음과 같은 핵심 함수들을 정의합니다.
1. isPresentInCol(col, num)
- 그리드의 모든 행 r을 순회하며
grid[r][col] == num인 경우 true를 반환합니다. - 끝까지 확인해도 없으면 false를 반환합니다.
2. isPresentInRow(row, num)
- 그리드의 모든 열 c를 순회하며
grid[row][c] == num인 경우 true를 반환합니다. - 끝까지 확인해도 없으면 false를 반환합니다.
3. isPresentInBox(boxStartRow, boxStartCol, num)
- 박스 시작 좌표부터 3×3 범위를 모두 순회하며 num이 존재하는지 확인하고, 존재하면 true를 반환합니다.
4. findEmptyPlace(row, col)
- 그리드 전체를 순회하며 값이 0인 빈 칸을 찾습니다.
- 빈 칸을 찾으면 참조 매개변수로 행과 열 좌표를 전달하고 true를 반환합니다.
- 모든 칸이 채워져 있으면 false를 반환합니다.
5. isValidPlace(row, col, num)
- 해당 숫자가 같은 행, 같은 열, 그리고 현재 3×3 박스 어디에도 존재하지 않으면 유효한 위치로 판단하여 true를 반환합니다.
6. solveSudoku()
- 그리드에서 더 이상 빈 칸이 없다면 퍼즐이 완성된 것이므로 true를 반환합니다.
- 빈 칸에 대해 1부터 9까지 각 숫자를 시도합니다.
- isValidPlace()로 유효성을 검사한 뒤 유효하면 해당 칸에 숫자를 할당합니다.
- 재귀적으로 solveSudoku()를 호출하여 성공하면 true를 반환합니다.
- 실패하면 해당 칸을 다시 0으로 되돌립니다(백트래킹).
- 모든 숫자를 시도했음에도 실패하면 false를 반환합니다.
C++ 전체 구현 코드
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
// 열에 num이 존재하는지 확인
bool isPresentInCol(int col, int num){
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
// 행에 num이 존재하는지 확인
bool isPresentInRow(int row, int num){
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
// 3x3 박스에 num이 존재하는지 확인
bool isPresentInBox(int boxStartRow, int boxStartCol, int num){
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
// 해결된 스도쿠 그리드 출력
void sudokuGrid(){
for (int row = 0; row < N; row++){
for (int col = 0; col < N; col++){
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] << " ";
}
if(row == 2 || row == 5){
cout << endl;
for(int i = 0; i<N; i++)
cout << "---";
}
cout << endl;
}
}
// 비어 있는 위치(값이 0인 칸)를 찾아 좌표를 갱신
bool findEmptyPlace(int &row, int &col){
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) // 0은 빈 칸을 의미
return true;
return false;
}
// 행, 열, 3x3 박스 어디에도 없을 때 유효한 위치
bool isValidPlace(int row, int col, int num){
return !isPresentInRow(row, num) && !isPresentInCol(col, num) &&
!isPresentInBox(row - row%3, col - col%3, num);
}
// 백트래킹으로 스도쿠 해결
bool solveSudoku(){
int row, col;
if (!findEmptyPlace(row, col))
return true; // 모든 칸이 채워짐
for (int num = 1; num <= 9; num++){ // 유효한 숫자는 1~9
if (isValidPlace(row, col, num)){ // 유효성 검사
grid[row][col] = num; // 현재 칸에 숫자 할당
if (solveSudoku()) // 재귀적으로 해결 시도
return true;
grid[row][col] = 0; // 실패 시 백트래킹
}
}
return false;
}
int main(){
if (solveSudoku() == true)
sudokuGrid();
else
cout << "No solution exists";
}입력 예제
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}출력 결과
3 1 6 | 5 7 8 | 4 9 2 5 2 9 | 1 3 4 | 7 6 8 4 8 7 | 6 2 9 | 5 3 1 --------------------------- 2 6 3 | 4 1 5 | 9 8 7 9 7 4 | 8 6 3 | 1 2 5 8 5 1 | 7 9 2 | 6 4 3 --------------------------- 1 3 8 | 9 4 7 | 2 5 6 6 9 2 | 3 5 1 | 8 7 4 7 4 5 | 2 8 6 | 3 1 9
마무리
백트래킹 기반 스도쿠 솔버는 구현이 비교적 간단하면서도 강력한 동작을 보여주는 대표적인 알고리즘 예제입니다. 최악의 경우 시간 복잡도는 O(9^m)으로 지수적으로 증가할 수 있지만(m은 빈 칸의 개수), 실제 스도쿠 퍼즐에서는 유효성 검사를 통해 탐색 공간이 크게 줄어들기 때문에 대부분의 퍼즐을 빠르게 해결할 수 있습니다. 이 코드를 확장하면 난이도 평가, 힌트 제공, 다중 해답 탐색 등 다양한 기능으로 발전시킬 수 있습니다.