이 프로그램은 Donald Knuth의 Dancing Links와 Algorithm X를 사용하여 스도쿠를 해결합니다.
알고리즘 동작 원리:
- 스도쿠 문제를 정확 피복 문제(Exact Cover Problem)로 변환
- 각 제약 조건을 이진 행렬의 열로 표현
- Dancing Links 자료구조로 효율적인 백트래킹 구현
- 재귀적 깊이 우선 탐색으로 해답 탐색
스도쿠의 4가지 제약 조건:
- 각 셀에는 정확히 하나의 숫자가 있어야 함
- 각 행에는 1-9의 숫자가 정확히 한 번씩 나타나야 함
- 각 열에는 1-9의 숫자가 정확히 한 번씩 나타나야 함
- 각 3×3 박스에는 1-9의 숫자가 정확히 한 번씩 나타나야 함