4×4 스도쿠 경우의 수는 288 가지 입니다. (feat. 덕문여고 1-1기말 2025)
오늘은 4×4 스도쿠 경우의 수를 직접 세어 보겠습니다.
글 - 알티수학 쌤＠센텀 알티수학 학원
1. 스도쿠?
스도쿠는 일본에서 유명해진 숫자 퍼즐입니다. 기본적인 형태는 9×9 격자에 1~9의 숫자를 채우는 것인데, 규칙은 세 가지입니다.
(i) 각 행에 1~9 가 한 번씩
(ii) 각 열에 1~9 가 한 번씩
(iii) 각 3×3 박스에 1~9 가 한 번씩
이 세 가지 조건을 동시에 만족시키도록 빈칸을 채우는 거죠.
이 9×9 스도쿠의 경우의 수는
인데, 이것은 대략 6.67 섹스틸리언(sextillion), 즉 6.67 해(垓) 정도입니다. 일반적으로 이 숫자는 지구상 모든 해변과 사막을 합친 모래알의 추정치보다도 약 890배 많은 것으로 알려져 있습니다.
펠겐하우어와 자비스(Felgenhauer & Jarvis)가 2005년에 컴퓨터와 수학적 분석을 결합해서 정확히 계산한 결과라 합니다.
2. 4×4 스도쿠 경우의 수 = 288
축소판인 4×4 스도쿠는 4×4 격자에 1~4 의 숫자를 위 세 조건(단, 박스는 2×2)에 맞게 채우는 겁니다. 이 축소판은 경우의 수를 중학생 수준으로 계산할 수 있습니다. 답은 288가지 입니다. 이제 이것을 저와 함께 한 번 세어보면 아마 수학 상식으로 기억되어 버릴것입니다.ㅋ
(1단계) 1행 고정
1행을 채우는 방법은 1, 2, 3, 4 의 순열 수 4!=24 가지입니다. 일반성을 잃지 않고 일단 1행을 (1,2,3,4) 로 고정해 두고, 마지막에 24를 곱해 주기로 하겠습니다.
(2단계) 2행은 4가지뿐
2행을 보겠습니다. 2×2 박스를 성립시키는 조건이 작동하는데,
좌상 박스에는 이미 1, 2 가 들어가 있으므로, 좌상 박스를 완성하려면 아래 두 칸에는 {3, 4} 가 어떤 순서로든 들어가야 합니다. 마찬가지로 우상 박스의 아래 두 칸에는 {1, 2} 가 들어가야 합니다.
따라서, 2행으로 가능한 조합은
뿐입니다. 1행과 2행까지 각각 적어보면 아래와 같습니다.
여기서, 자세히 보면 위쪽 두 개와 아래쪽 두 개는 각각 성질이 다릅니다.
위쪽 두 개를 (가형) 이라고 하고, 아래쪽 두 개를 (나형) 이라 하겠습니다.
세로 방향으로 두 개의 숫자쌍을 볼 때, (가형)은 서로 다른 숫자쌍이 2쌍입니다. (가형) 의 왼쪽 스도쿠 1, 2행을 보면 세로 방향 숫자쌍이 {1,3}, {2,4} 가 두 번 반복되고, 오른쪽 스도쿠에서도 세로 방향 숫자쌍이 {1,4}, {2,3} 으로 두번 반복되고 있습니다.
반면에 (나형)은 세로 방향으로 볼 때, 서로 다른 숫자쌍이 4쌍입니다. (나형) 의 왼쪽 스도쿠 1, 2행을 보면 세로 방향 숫자쌍이 {1,3}, {2,4}, {3,2}, {4,1} 이고, 오른쪽 스도쿠에서는 {1,4}, {2,3}, {3,1}, {4,2} 입니다.
(가형) 과 (나형) 의 이 차이는 3, 4 행을 채울때 효과가 나타납니다.
(3단계) 3, 4행 채우기
이제 3, 4행을 채워보겠습니다.
(가형) :
예를 들어, 2행이 (3,4,1,2) 인 경우, 각 열에 3, 4 행에서 사용할 수 있는 남은 숫자는
1열 {2,4}, 2열 {1,3}, 3열 {2,4}, 4열 {1,3} 입니다.
1열에 순서대로 2, 4 를 배치하면 3열에는 순서대로 4, 2 를 배치해야 합니다. 또, 1열에 4,2 로 배치하면 이번엔 3열에 2, 4 로 배치해야 하니 이 때 경우의 수가 2가지 입니다.
2열과 4열도 마찬가지이므로 2가지가 가능하고, 따라서 4가지가 가능하죠.
또, 2행이 (4,3,2,1) 인 경우도 같은 방법으로 4가지가 가능합니다.
따라서 (가형) 은 8가지가 가능합니다.
(나형) :
위의 (가형) 과 같은 방식으로 따져보면, 쌍이 엇갈려있어서 이번엔 행조건과 박스 조건이 충돌하는 경우가 생기는데 이 때는 2가지가 가능합니다.
즉, 보다시피 1열의 3,4행의 (2,4) 를 순서를 바꿔서 (4,2) 로 바꾸면 나머지 2,3,4열이 고정되어 버립니다.
또,
따라서 (나형) 은 4가지가 가능합니다.
(4단계) 종합
따라서 1행을 (1,2,3,4) 로 고정했을 때 가능한 전체 격자의 수는
합쳐서 12가지 입니다.
여기에 1행을 고르는 24가지를 곱하면, 4×4 스도쿠의 전체 경우의 수는
이 됩니다.
3. n² × n² 일반화는 아직 아무도 모릅니다
n²×n² 격자에 n×n 박스를 두고 1부터 n² 까지 채우는 일반 스도쿠를 생각해 볼 수는 있지만,
n=4, 즉 16×16 스도쿠부터는 현재까지 정확한 경우의 수를 모릅니다. 슈퍼컴퓨터로 추정치 정도만 나와 있다라고 하네요.
4. 덕문여고 작년 1학년 내신 기출문제
마침, 작년에 인근 학교 기출에 나왔습니다.
좌석 배치를 자세히 보면, 4×4 격자에서 4행 4열 자리 한 칸만 비어있는 모양입니다. 그리고 조건 (가), (나), (다) 는 각각
(가) 박스 조건 (같은 구역에 같은 반이 2개 이상 안 됨)
(나) 행 조건 (같은 줄에 같은 반이 2개 이상 안 됨)
(다) 열 조건 (같은 열에 같은 반이 2개 이상 안 됨)
인데, 즉, 1, 2, 3, 4 대신 A, B, C, D 를 쓰는 한 칸 빠진 4×4 스도쿠 입니다.
그리고, 어떤 세 반은 4번씩, 나머지 한 반은 3번 등장하고, 1행 1열이 A반이라 했습니다.
그러므로, 4×4 스도쿠에서 1행1열에 1을 놓고 (숫자 1이 A반이라 합시다.) 스도쿠를 구성한 뒤 4행4열은 삭제해버리면 스도쿠 문제와 일대일대응이 성립합니다.
즉, 4×4 스도쿠가 288개 임을 알고 있으니 1행1열이 1로 고정된것은 균등분포하므로
가 됩니다.
참고로, 성립하는 4×4 스도쿠 288개에서 숫자 1, 2, 3, 4 중에 임의의 두 개를 스도쿠 전체에 교체해도 또 다른 성립하는 스도쿠가 나오므로 균등 분포는 쉽게 알 수 있구요.
따라서, 답은 ⑤ 72 입니다.
5. 결론
① 4×4 스도쿠의 경우의 수 288 은 시험에 나올만한 크기의 경우의 수이다.
② 9×9 스도쿠는 약 6.67 × 10^21 로 너무 크고, 16×16 이상은 아직 아무도 모른다.