Counting, Symmetries and Equivalence Classes of Sudoku Grids

거대한 스도쿠 퍼즐 찾기

당신은 81개의 방이 있는 거대한 저택을 아홉 가지 종류의 가구로 채울 수 있는 모든 가능한 방법을 세려는 탐정이라고 상상해 보십시오. 하지만 여기에는 아주 까다로운 규칙이 있습니다. 모든 행, 모든 열, 그리고 모든 3x3 크기의 방에는 반드시 각 가구의 종류가 정확히 하나씩 있어야 합니다. 이것이 바로 수백만 명을 매료시킨 스도쿠의 세계입니다. 하지만 수학자들에게 스도쿠는 단순한 게임이 아닙니다. 그것은 거대한 조합론적 미로입니다. 그들은 이 거대한 저택(또는 "그리드")이 얼마나 많은 고유한 방식으로 존재할 수 있는지 알고 싶어 합니다. 그리고 더 중요한 것은, 집 전체를 회전시키거나 가구의 이름을 바꾸는 것을 무시했을 때, 정말로 '서로 다른' 저택이 몇 개나 존재하는가 하는 점입니다.

이 문제를 해결하기 위해 수학자들은 '군론(group theory)'이라는 강력한 도구를 사용하는데, 이는 본질적으로 대칭성을 연구하는 학문입니다. 대칭성을 마법의 거울이라고 생각해 보십시오. 눈송이를 회전시키거나 카드를 뒤집으면 잠시 동안은 다르게 보일 수 있지만, 그것은 근본적으로 동일한 물체입니다. 스도쿠의 세계에서, 만약 당신이 숫자를 바꾸거나(예를 들어 모든 1을 2로, 2를 1로 바꾸는 것) 행과 열을 섞어서 하나의 그리드를 다른 그리드로 만들 수 있다면, 이 두 그리드는 "쌍둥이"로 간주됩니다. 큰 질문은, 숫자를 바꾸거나 행과 열을 섞는 등의 변환을 고려하지 않고, 오직 고유하고 서로 다른 "쌍둥이가 아닌" 그리드가 몇 개나 존재하는가 하는 것입니다. 수십 년 동안 이 답은 브루트 포스(brute-force) 방식의 컴퓨터 연산력을 통해 밝혀졌지만, 그 과정은 명확하고 논리적인 경로라기보다는 지저분한 기교들의 더미처럼 느껴졌습니다.

논문의 발견: 숨겨진 패턴을 찾아서

이 논문에서 페르난다 페레이라(Fernanda Pereira)는 스도쿠 계산 문제의 특정하고 까다로운 부분에 대해 새로운 시각을 제시합니다. 그녀는 그리드의 "첫 번째 밴드(first band)", 즉 상단 세 줄의 행에 집중합니다. 이전 연구자인 펠겐하우어(Felgenhauer)와 자비스(Jarvis)는 이미 이 상단 행 밴드의 구별되는 유형이 정확히 44개라는 사실을 밝혀낸 바 있습니다. 그러나 그들은 이 44라는 숫자에 도달하기 위해 다섯 가지 서로 다른 "축소(reduction)" 과정을 거치는 길고 복잡한 사슬을 적용했습니다. 그것은 마치 양파 껍질을 한 겹 한 겹 벗겨내는 것과 같았으며, 각 층마다 서로 다른 특정한 기술이 필요했습니다. 결과는 맞았지만, 숫자 44는 깊은 의미가 없는, 길고 구불구불한 길 위의 우연한 정거장처럼 느껴졌습니다.

페레이라의 논문은 44가 무작위적인 사고가 아니라 근본적인 구조적 진실이라고 주장합니다. 그녀는 문제를 바라보는 더 깨끗한 새로운 방식을 제안합니다. 그녀는 단순히 층을 벗겨내는 대신, 새로운 렌즈를 통해 스도쿠 그리드를 바라볼 것을 제안합니다: 바로 **열 분할(column partitions)**입니다.

그리드의 상단 세 줄을 세 개의 별도 상자라고 상상해 보십시오. 각 상자에서 세 개의 열은 특정 "팀"의 세 숫자를 형성합니다. 예를 들어, 첫 번째 상자에서 첫 번째 열은 {1, 4, 7}, 두 번째 열은 {2, 5, 8}, 세 번째 열은 {3, 6, 9}를 가질 수 있습니다. 이러한 그룹화를 "분할(partition)"이라고 합니다. 페레이라의 위대한 아이디어는 스도쿠 그리드 상단 밴드의 모든 복잡성을 이 세 가지 "숫자 팀"의 단순한 목록으로 요약할 수 있다는 것입니다.

그녀는 이 세 팀을 엄격한 순서(상자 1, 상자 2, 상자 3)가 아닌, 멀티셋(multiset)—즉, 순서는 상관없지만 중복은 허용되는 주머니—으로 취급합니다. 만약 당신이 세 개의 동일한 숫자 주머니를 가지고 있다면 그것은 한 가지 경우이고, 두 개는 동일하지만 하나는 다르다면 또 다른 경우입니다. 논문은 두 스도쿠 밴드가 "쌍둥이"(동등함)인 필요충분조건은 숫자를 재배열(relabeling)하거나 상자를 바꾸더라도 그들의 숫자 팀 주머니가 동일한 경우임을 증명합니다.

"수기로 계산된" 돌파구

이 논문의 가장 흥兴奋스러운 부분은 그녀가 이 주머니들을 세는 방법입니다. 수백만 개의 가능성을 확인하기 위해 슈퍼컴퓨터에 의존하는 대신, 페레이라는 **번사이드의 보조정리(Burnside's Lemma)**라는 수학적 정리를 사용합니다. 이 정리는 서로 다른 대칭성을 적용했을 때 얼마나 많은 것들이 변하지 않고 유지되는지를 살펴봄으로써 고유한 그룹의 수를 찾아내는 영리한 계산 단축키와 같습니다.

그녀는 이 "분할의 주머니" 아이디어에 이 정리를 적용함으로써, 폐쇄형 분석 공식(closed, analytical formula)을 통해 숫자 44를 도출해 냅니다. 그녀는 문제를 30가지의 서로 다른 숫자 섞기 패턴(순환 유형/cycle types)으로 나눕니다. 각 패턴에 대해, 그녀는 얼마나 많은 "주머니"가 변하지 않고 유지되는지를 계산합니다. 그런 다음 그녀는 19개의 특정 비제로(non-zero) 계산 결과를 모두 더합니다. 최종 합계를 특정 숫자로 나누면 정확히 44에 도달합니다.

하지만 이 우아한 공식을 찾아가는 과정에는 계산적 보조가 필요했습니다. 최종적인 44개 클래스의 도출은 컴퓨터 열거 없이도 가능한 폐쇄형 계산이지만, 논문은 저자가 수학적 논증을 발전시키기 위해 AI 도구의 도움을 받았고, 계산 검증을 수행하기 위해 파이썬(Python) 스크립트를 작성했다고 명시하고 있습니다. 이 스크립트들은 모든 순열에 대한 직접적인 평가를 통해 계산의 분해와 최종 합계가 제대로 되었는지 독립적으로 확인했습니다. 이는 "수기로 계산된" 논리가 브루트 포스 방식의 현실과 일치함을 보장하며, 44개의 클래스가 올바른 구조적 결과임을 확증합니다.

이는 관점의 거대한 전환입니다. 논문은 44가 단순히 길고 임시방편적인 축소 과정의 지저한 부산물이라는 생각에 명시적으로 반박합니다. 대신, 그녀는 44가 대칭의 규칙 아래에서 숫자 분할을 배열하는 고유한 방법들을 세는 자연스러운 결과임을 보여줍니다.

더 큰 그림

논문은 44개 클래스에 대한 주요 초점을 맞추고 있지만, 모든 고유한 스도쿠 그리드의 총 개수에 대해서도 언급합니다. 그녀는 러셀(Russell)과 자비스(Jarvis)가 컴퓨터를 통해 찾아낸 기존의 숫자 인 5,472,730,538개의 본질적으로 다른 그리드 수를 확인합니다. 페레이라의 방법은 단순히 이를 재검증하는 데 그치지 않고, 그 거대한 계산의 토대를 이루는 44개 클래스에 대한 구조적 설명을 제공합니다.

요약하자면, 이 논문은 긴 여정의 무작위적인 정거점처럼 보였던 숫자를 명확하고 아름다운 지도가 있는 목적지로 탈바로 놓았습니다. 그녀는 다섯 단계의 복잡한 기교를 하나의 우아한 불변량(분할의 멀티셋)과 하나의 강력한 계산으로 대체했습니다. 그 결과는 44개의 클래스가 계산의 우연이 아니라 스도쿠 우주의 근본적인 특징이라는 증명이며, 최종적인 분석 단계는 손으로 계산 가능하면서도 그 밑바탕이 되는 논리는 컴퓨터에 의해 엄격하게 검증되었습니다.