Sudoku Flow컴퓨터는 스도쿠를 어떻게 풀까
2026-10-05 업데이트
백트래킹
풀이 프로그램은 빈칸에 규칙에 맞는 숫자를 넣어 보고 계속 진행한다. 어떤 숫자를 넣어도 해답으로 이어지지 않으면 이전 선택을 되돌리고 다른 숫자를 시도한다. 넣을 수 있는 숫자가 가장 적은 칸부터 선택하면 탐색 과정이 훨씬 짧아지는 경우가 많다.
출처: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
정확 덮개와 Dancing Links
스도쿠는 정확 덮개 문제로 바꿔 표현할 수 있다. 모든 칸과 각 행, 열, 박스의 모든 숫자가 정확히 한 번씩 충족되도록 숫자 배치를 선택하는 것이다. 도널드 크누스는 2000년 11월 논문에서 자신의 백트래킹 알고리즘인 Algorithm X를 효율적으로 실행하는 방법인 Dancing Links를 설명했다. 이를 스도쿠의 정확 덮개 모델에 적용하면 퍼즐의 모든 해답을 빠르게 찾을 수 있다.
출처: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
무작위 탐색
일부 프로그램은 격자를 무작위로 채운 다음, 시뮬레이티드 어닐링이나 유전 알고리즘 같은 방법으로 숫자를 재배치해 규칙 위반의 수를 줄인다. 이런 방법은 대안적 접근법으로 연구되어 왔으며, 성능은 프로그램과 퍼즐에 따라 달라진다.
출처: Wikipedia: Sudoku solving algorithms
사람처럼 생각하는 풀이 프로그램
힌트 엔진의 역할은 다르다. 답을 찾는 데 그치지 않고 사람이 따라 할 수 있는 다음 단계를 보여 주어야 한다. 우리 앱의 엔진은 히든 싱글 같은 가장 쉬운 기법부터 체인과 거의 잠긴 집합 같은 가장 어려운 기법까지, 사람의 풀이 기법을 정해진 순서로 시도하고 숫자 입력으로 이어지는 첫 번째 기법을 사용한다. 더 어려운 기법은 먼저 후보를 제거하는 방식으로 작동한다. 퍼즐을 풀 때 사용한 가장 어려운 기법이 앱에서 그 퍼즐의 난이도를 결정한다.
