스도쿠의 수학

2026-10-05 업데이트

박스가 있는 라틴 방진

라틴 방진에서는 각 행과 각 열에 모든 기호가 한 번씩 나타납니다. 완성된 스도쿠는 조건 하나가 더 있는 크기 9의 라틴 방진입니다. 아홉 개의 3×3 박스 각각에도 모든 숫자가 한 번씩 들어갑니다.

격자는 몇 개나 있을까

베르트람 펠겐하우어(Bertram Felgenhauer)와 프레이저 자비스(Frazer Jarvis)는 2005년 완성된 9×9 격자의 수를 계산했습니다. 그 수는 6,670,903,752,021,072,936,960개로, 약 6.67 × 10²¹개입니다. 그중 상당수는 겉모습만 다른 같은 격자입니다. 숫자의 표기를 바꾸거나, 회전하거나, 반사하거나, 격자의 유효성을 유지하는 방식으로 행과 열의 순서를 바꾸어 한 격자를 다른 격자로 만들 수 있을 때 두 격자를 하나로 세면 본질적으로 서로 다른 격자 5,472,730,538개가 남습니다. 이 수는 에드 러셀(Ed Russell)과 프레이저 자비스가 계산했습니다.

출처: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

최소 단서 17개

주어진 숫자가 16개 이하인 표준 9×9 스도쿠 중 해답이 정확히 하나인 것은 없습니다. 게리 맥과이어(Gary McGuire), 바스티안 투게만(Bastian Tugemann), 질 시바리오(Gilles Civario)는 전수 컴퓨터 탐색으로 이를 보였으며, 2012년 1월 결과를 발표했습니다. 17개는 최솟값일 뿐 보장은 아닙니다. 주어진 숫자가 17개인 많은 격자에도 여전히 해답이 둘 이상 있습니다.

출처: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

그래프 색칠로 보는 스도쿠

81개의 칸마다 점 하나를 그리고, 두 칸이 같은 행, 열 또는 박스에 속할 때마다 해당하는 두 점을 연결합니다. 이 스도쿠 그래프에는 연결이 810개 있으며, 각 점에는 이웃이 정확히 20개 있습니다. 퍼즐을 푼다는 것은 주어진 숫자로 정해진 색을 바탕으로 나머지 점을 색칠하되, 연결된 점들의 색이 항상 다르게 하는 것을 뜻합니다. 각 행, 열, 박스는 모든 점이 서로 연결된 아홉 점의 묶음이므로 색이 최소 아홉 가지 필요하며, 어떤 완성 격자든 아홉 가지로 충분하다는 것을 보여 줍니다.

출처: Wikipedia: Sudoku graph

일반적으로는 어렵지만 9×9는 빠르게

크기를 제한 없이 늘릴 수 있는 스도쿠 격자(n×n 박스를 사용하는 n²×n² 격자)에서 일부 칸이 채워진 격자를 완성할 수 있는지 판단하는 문제는 NP-완전입니다. 이는 야토 다카유키(Takayuki Yato)와 세타 다카히로(Takahiro Seta)가 2003년에 발표한 결과입니다. 효율적인 컴퓨터 프로그램은 보통 일반적인 9×9 퍼즐을 1초보다 훨씬 짧은 시간에 풀지만, 걸리는 시간은 프로그램, 컴퓨터, 퍼즐에 따라 달라집니다.

출처: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

함께 보기

출처

모든 글 →