From Crutches to Bijection: How I Wrote a Sudoku Generator in JS

Context

초기 버전은 기본 유효한 Sudoku 그리드를 16진수 시드로 제어되는 비트 플래그 기반 랜덤 셔플로 변환했다. 이 방식은 제한된 변환 함수 개수(24가지)로 인해 생성 가능한 그리드 조합이 제한되었고 패턴이 나타날 수 있었다.

Technical Solution

• 기본 배열 셔플 방식을 Factorial Number System(계승수 체계) 기반 Bijection으로 전환: 시드 정수를 6으로 반복 나누어 각 순열의 인덱스 계산
• 행/열 블록 순열 독립 생성: 3개 행 블록, 3개 열 블록에 대해 각각 3! = 6가지 순열을 시드에서 추출
• 행/열 내부 순열 독립 생성: 각 블록 내 3개 행, 3개 열에 대해 각각 3! = 6가지 순열을 시드에서 추출
• 숫자 순열 독립 생성: 9개 숫자의 순열을 9! = 362,880가지로 계산해 전역 숫자 변환 적용
• 물리적 셔플 제거: 인덱싱을 통해 원본 BASE_GRID에서 직접 변환된 셀 값을 읽음으로써 배열 스왑 연산 제거

Impact

총 생성 가능한 유효한 Sudoku 그리드 개수를 6^8 × 9! = 약 1,218,998,108,160개(약 1.2조)로 확장

Key Takeaway

조합론과 수학적 구조를 활용하면 임시방편적 알고리즘을 우아하고 충돌 없는 정확한 솔루션으로 전환할 수 있다. Factorial Number System을 활용한 Bijection은 유한한 순열 공간을 결정론적으로 열거하는 강력한 패턴이다.