스도쿠 백트래킹
선택, 탐색, 되돌아가기
백트래킹
백트래킹(Backtracking)은 문제 해결 과정에서 막다른 길에 도달했을 때 이전 단계로 돌아가서 다른 선택지를 시도하는 알고리즘이다.
아래 과정을 반복한다.
- 선택: 현재 상황에서 가능한 선택지 중 하나를 선택
- 탐색: 선택한 결과로 다음 단계를 진행
- 되돌아가기: 현재 선택이 해답으로 이어지지 않는다면 선택을 취소하고 다른 선택지를 시도
예를 들어, 어떤 퍼즐의 특정 위치에 숫자를 넣었는데 그 숫자가 규칙을 위반한다면 이후 모든 탐색은 무의미해진다. 더 이상 진행하지 않고 이전 단계로 되돌아가 다른 선택을 시도한다.
알고리즘의 시간 복잡도
스도쿠 백트래킹의 최악의 경우 시간 복잡도는 O(9^(n^2))이다. 여기서 n은 보드의 크기다. 81개의 빈칸이 있다면 각 칸에 9개의 숫자를 시도할 수 있으므로 이론적으로는 9^81가지 경우의 수가 있다.
하지만 실제로는 제약 조건 때문에 대부분은 조기에 제거되어 훨씬 빠르게 동작한다.
시각화
빈칸에 숫자를 하나씩 시도하고, 막히면 되돌아가며 스도쿠판이 채워지는 과정이다.
5
2
7
9
8
1
6
5
8
4
1
7
6
3
2
1
8
1
5
6
1
9
6
3
3
4
6
2
8
9
9
2
7
4
8
시도되돌아가기