피드로 돌아가기
Dev.toBackend
원문 읽기
The Algorithm Behind Solving Any Sudoku Puzzle in Milliseconds
Sudoku 솔버가 Constraint Propagation과 Backtracking 알고리즘 조합으로 9^56 탐색 공간을 밀리초 단위로 해결
AI 요약
Context
Sudoku는 81개 셀 중 25~35개 클루만 제공되는 제약 만족 문제로, 나머지 46~56개 셀을 채워야 한다. 순진한 전수 탐색으로는 9^56가지 경우의 수를 모두 확인해야 하므로 실행 불가능하다.
Technical Solution
- Constraint Propagation 단계 도입: 각 빈 셀의 후보를 {1-9}로 초기화한 후 같은 행, 열, 3x3 박스에 이미 배치된 숫자를 제거하여 후보 범위 축소
- Naked Single 감지: 후보가 1개만 남은 셀을 자동으로 해결하고 연쇄적으로 관련 셀의 후보 감소
- Hidden Single 감지: 특정 행, 열, 박스에서 어떤 숫자가 오직 한 셀에만 배치 가능한 경우를 감지하여 직접 해결
- Backtracking 검색 도입: Propagation만으로 풀리지 않는 경우 최소 남은 값(MRV) 휴리스틱을 사용해 후보가 가장 적은 셀을 먼저 선택
- 재귀적 추측 및 되돌리기: 각 후보값을 시도한 후 Propagation 수행, 모순 발생 시 이전 상태로 복구하고 다음 후보값 시도
Impact
모든 유효한 Sudoku 퍼즐이 10밀리초 이내에 해결된다.
Key Takeaway
Constraint Propagation과 Backtracking의 조합은 Sudoku를 넘어 스케줄링, 자원 할당, 회로 설계, 컴파일러 레지스터 할당 같은 실제 제약 만족 문제에 적용 가능한 핵심 패턴이다. SAT 솔버의 기반이 되어 하드웨어 검증과 패키지 의존성 해결 같은 산업 수준 응용에 활용된다.
실천 포인트
일정 수립, 자원 할당, 패키지 의존성 해결 같은 제약 만족 문제를 다루는 엔지니어는 먼저 Constraint Propagation으로 가능한 많은 경우를 제거한 후 필요할 때만 Backtracking 검색을 적용하고, 탐색 단계에서 최소 남은 값(MRV) 휴리스틱을 사용해 분기 인수를 최소화하면 현저히 빠른 솔루션을 구현할 수 있다.