스도쿠(Sudoku)는 전 세계적으로 사랑받는 대표적인 숫자 퍼즐입니다. 이 글에서는 C++와 백트래킹(backtracking) 알고리즘을 활용해 주어진 스도쿠 퍼즐을 자동으로 풀어내는 방법을 단계별로 살펴보겠습니다.
스도쿠의 기본 규칙
스도쿠는 9×9 크기의 숫자 격자로 이루어져 있으며, 전체 격자는 다시 3×3 크기의 작은 박스 9개로 나뉩니다. 퍼즐을 풀 때 지켜야 할 규칙은 다음과 같습니다.
숫자는 반드시 1부터 9까지만 사용해야 합니다.
같은 숫자가 한 행, 한 열, 또는 하나의 3×3 박스 안에 중복되어 나타날 수 없습니다.
백트래킹 알고리즘의 동작 원리
이 문제는 백트래킹 기법으로 해결할 수 있습니다. 빈 칸에 숫자를 하나 채운 뒤 해당 값이 유효한지 검사하고, 유효하지 않다면 다른 숫자를 시도합니다. 만약 1부터 9까지 모든 숫자를 시도했는데도 적합한 값을 찾지 못하면, 이전 단계로 되돌아가(백트래킹) 다른 선택지를 다시 탐색합니다.
예를 들어 아래와 같은 입력이 주어졌다고 가정해 보겠습니다.
프로그램이 실행되면 다음과 같은 결과를 얻을 수 있습니다.
알고리즘 구현 단계
문제를 해결하기 위해 다음과 같은 함수들을 정의합니다.
isPresentInCol(col, num) – 특정 열(col)에 숫자 num이 이미 존재하는지 확인합니다. 격자의 각 행 r을 순회하며 grid[r][col] == num이면 true를 반환하고, 끝까지 찾지 못하면 false를 반환합니다.
isPresentInRow(row, num) – 특정 행(row)에 숫자 num이 이미 존재하는지 확인합니다. 각 열 c를 순회하며 grid[row][c] == num이면 true를 반환합니다.
isPresentInBox(boxStartRow, boxStartCol, num) – 박스의 시작 좌표(boxStartRow, boxStartCol)부터 3×3 범위 내에 num이 존재하는지 확인합니다.
findEmptyPlace(row, col) – 값이 0인(비어 있는) 첫 번째 칸을 찾아 그 좌표를 갱신합니다. 빈 칸이 있으면 true, 없으면 false를 반환합니다.
isValidPlace(row, col, num) – 같은 행, 같은 열, 그리고 현재 위치가 속한 3×3 박스(row − row%3, col − col%3) 어디에도 num이 존재하지 않을 때 true를 반환합니다.
solveSudoku() – 실제 문제를 재귀적으로 해결하는 핵심 함수입니다. 더 이상 빈 칸이 없으면 true를 반환해 성공을 의미하고, 그렇지 않으면 1~9 사이의 숫자를 차례대로 시도합니다. 유효한 숫자라면 해당 칸에 값을 넣고 재귀 호출을 진행하며, 실패하면 다시 0으로 되돌려 놓습니다.
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}
};
bool isPresentInCol(int col, int num){ //num이 해당 열에 존재하는지 확인
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInRow(int row, int num){ //num이 해당 행에 존재하는지 확인
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num){
//num이 3x3 박스에 존재하는지 확인
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;
}
}
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;
}
bool isValidPlace(int row, int col, int num){
//행, 열, 현재 3x3 박스 어디에도 존재하지 않으면 유효한 위치
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
마무리
이처럼 백트래킹 알고리즘은 스도쿠처럼 제약 조건이 명확한 문제를 해결하는 데 매우 효과적입니다. 최악의 경우 시간 복잡도는 지수형태로 증가할 수 있지만, 유효성 검사를 조기에 수행해 탐색 공간을 크게 줄일 수 있어 실질적으로 빠르게 동작합니다. 위 코드를 응용하면 난이도 조절, 힌트 생성 등 다양한 스도쿠 프로그램을 만들어 볼 수 있습니다.