이 글에서는 세계적으로 유명한 숫자 퍼즐인 '스도쿠(Sudoku)'를 컴퓨터로 해결하는 방법을 다룹니다. 스도쿠는 9×9 크기의 숫자 격자로 이루어져 있으며, 전체 격자는 다시 3×3 크기의 작은 박스 아홉 개로 나뉩니다. 스도쿠를 풀 때는 다음과 같은 규칙을 반드시 지켜야 합니다.
- 1부터 9까지의 숫자만 사용하여 퍼즐을 완성해야 합니다.
- 같은 숫자는 하나의 행, 하나의 열, 그리고 하나의 3×3 박스 안에서 중복될 수 없습니다.
여기서는 백트래킹(backtracking) 알고리즘을 활용해 스도쿠를 해결합니다. 빈 칸에 숫자를 하나 채울 때마다 그 숫자가 규칙에 맞는지 검사하고, 유효하지 않다면 다른 숫자를 시도합니다. 만약 1부터 9까지 모든 숫자를 시도했는데도 놓을 수 있는 숫자가 없다면, 이전 단계로 되돌아가(백트래킹) 다른 선택을 다시 시도하는 방식입니다.
입력과 출력
입력: 9×9 크기의 행렬이 스도쿠 격자로 주어집니다. 일부 칸에는 숫자가 미리 채워져 있으며, 빈 칸은 0으로 표시됩니다.출력: 숫자가 모두 채워진 최종 스도쿠 격자. 해가 존재하지 않으면 false를 반환합니다. 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
알고리즘
isPresentInCol(col, num)
입력: 검사할 열(column)과 찾으려는 숫자
출력: 해당 열에 숫자가 존재하면 true
시작
격자의 각 행 r에 대해 반복
만약 grid[r, col] = num이면
true 반환
반복 종료
그 외의 경우 false 반환
끝
isPresentInRow(row, num)
입력: 검사할 행(row)과 찾으려는 숫자
출력: 해당 행에 숫자가 존재하면 true
시작
격자의 각 열 c에 대해 반복
만약 grid[row, c] = num이면
true 반환
반복 종료
그 외의 경우 false 반환
끝
isPresentInBox(boxStartRow, boxStartCol, num)
입력: 3×3 박스의 시작 행과 시작 열, 찾으려는 숫자
출력: 해당 박스 안에 숫자가 존재하면 true
시작
boxStartRow부터 3개의 행 r에 대해 반복
boxStartCol부터 3개의 열 c에 대해 반복
만약 grid[r, c] = num이면
true 반환
반복 종료
반복 종료
그 외의 경우 false 반환
끝
findEmptyPlace(row, col)
입력: 격자의 행과 열
출력: grid[row, col]이 비어 있으면 true, 아니면 false
시작
격자의 각 행 r에 대해 반복
격자의 각 열 c에 대해 반복
만약 grid[r, c] = 0이면
true 반환
반복 종료
반복 종료
false 반환
끝
isValidPlace(row, col, num)
입력: 격자의 행, 열, 그리고 검사할 숫자
출력: grid[row, col] 위치에 숫자를 놓는 것이 유효하면 true
시작
isPresentInRow(row, num), isPresentInCol(col, num),
isPresentInBox(row – row mod 3, col – col mod 3, num)
세 결과가 모두 false라면
true 반환
끝
solveSudoku(스도쿠 격자)
입력: 아직 풀리지 않은 스도쿠 격자
출력: 풀이가 완료된 격자
시작
만약 격자에 빈 칸이 더 이상 없다면
true 반환
1부터 9까지의 숫자에 대해 반복
만약 isValidPlace(row, col, number)가 참이면
grid[row, col] := number
만약 solveSudoku() = true이면
true 반환
grid[row, col] := 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}
};
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) { //빈 위치를 찾아 row와 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 박스 어디에도 num이 없을 때 true 반환
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; //조건이 맞지 않으면 다시 빈 칸(0)으로 되돌림
}
}
return false;
}
int main() {
if (solveSudoku() == true)
sudokuGrid();
else
cout << "No solution exists";
}
실행 결과
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
이 알고리즘의 시간 복잡도는 빈 칸의 개수를 n이라 할 때 최악의 경우 O(9n)으로 지수 시간이 걸립니다. 다만 백트래킹은 유효하지 않은 경로를 조기에 잘라내기 때문에, 실제로는 대부분의 스도쿠 퍼즐을 훨씬 적은 연산으로 빠르게 해결할 수 있습니다.