스도쿠 완성판은 몇 개일까 — 4×4는 288개, 9×9는 22자리 수입니다

6×6은 2,820만 개

6×6 스도쿠는 1~6을 쓰고 상자가 2×3입니다. 신문 퍼즐 난에서 가끔 보이는 크기예요.

판	스도쿠 완성판	가로·세로만 지킨 판	상자 규칙까지 통과
4×4	288	576	50%
6×6	28,200,960	812,851,200	3.47%

6×6은 한 판씩 전부 만들어 세는 데 40초가 걸렸습니다. 결과는 28,200,960개로, 알려진 값과 한 자리도 다르지 않았습니다. 첫 줄을 1 2 3 4 5 6으로 고정해서 세면 39,168개가 나오고, 여기에 첫 줄을 늘어놓는 방법 720가지를 곱해도 같은 수가 됩니다.

오른쪽 끝 칸을 보세요. 4×4에서는 상자 규칙이 절반을 남겼는데, 6×6에서는 3.47%만 남깁니다. 판이 커질수록 상자 조건이 훨씬 세게 걸러 내는데도 2,820만 개가 남습니다.

9×9는 22자리 수

우리가 평소에 푸는 9×9는 직접 세지 못했습니다. 대신 이미 계산된 값이 있습니다. 2005년 버트람 펠겐하우어와 프레이저 자비스가 컴퓨터로 계산한 결과로 알려진 값입니다.

9×9 완성판: 6,670,903,752,021,072,936,960개

22자리 수이고, 우리말 단위로 읽으면 약 66해 7천경입니다.

감을 잡기 위해 한 가지 계산을 해 봤습니다. 6×6을 셀 때 속도는 1초에 약 70만 판이었습니다. 이 속도로 9×9를 한 판씩 센다면 약 3억 년이 걸립니다. 그래서 알려진 계산은 한 판씩 세지 않고, 맨 위 세 줄을 채우는 방법을 서로 바꿔 만들 수 있는 것끼리 묶은 뒤 나머지 여섯 줄만 따로 세는 식으로 일을 줄였다고 합니다.

크기가 커질 때 늘어나는 폭도 비교해 볼 만합니다.

넘어갈 때	늘어난 배수
4×4 → 6×6	97,920배
6×6 → 9×9	약 236조 배

대칭으로 묶으면 — 4×4는 딱 두 종류

288개가 전부 제각각일까요? 그렇지 않습니다. 어떤 판을 가지고

• 숫자 이름을 바꾸거나(1과 3을 맞바꾸기 등)
• 같은 띠 안에서 두 줄을 맞바꾸거나, 위아래 띠를 통째로 맞바꾸거나
• 세로 방향도 같은 식으로 바꾸거나
• 대각선을 기준으로 뒤집어도

여전히 규칙을 지키는 판이 나옵니다. 이렇게 서로 바꿔 만들 수 있는 판을 한 무리로 묶어 봤습니다. 결과는 단 두 무리였습니다.

무리 1 (96판)      무리 2 (192판)
1 2 3 4            1 2 3 4
3 4 1 2            3 4 1 2
2 1 4 3            2 3 4 1
4 3 2 1            4 1 2 3

288개의 완성판은 사실 이 두 판을 이리저리 돌리고 바꿔 부른 것입니다.

9×9에도 같은 셈이 있습니다. 대칭을 걸러 낸 본질적으로 다른 9×9 완성판은 5,472,730,538개(약 54억 7천만 개)로, 2006년에 계산된 것으로 알려져 있습니다. 전체 개수를 이 수로 나누면 약 1조 2,189억인데, 이 값은 9×9 판에 걸 수 있는 대칭의 가짓수 1,218,998,108,160과 거의 같습니다. 대부분의 판이 대칭을 걸었을 때 모두 다른 모양이 된다는 뜻입니다.

힌트는 몇 개까지 줄일 수 있나

이제 반대 방향입니다. 완성판에서 칸을 지워 문제를 만들 때, 답이 여전히 하나뿐이려면 몇 칸을 남겨야 할까요.

4×4는 칸이 16개라 모든 경우를 다 볼 수 있습니다. 288판 각각에 대해, 16칸 중 어느 칸을 힌트로 남길지 65,536가지를 전부 확인했습니다.

힌트 개수	확인한 문제 수	답이 하나인 문제	비율
3개	161,280	0	0%
4개	524,160	25,728	4.91%
5개	1,257,984	284,160	22.59%
6개	2,306,304	1,041,408	45.15%
8개	3,706,560	2,961,024	79.89%
12개	524,160	522,624	99.71%
13개 이상	—	전부	100%

힌트 3개로는 단 한 번도 답이 하나로 정해지지 않았습니다. 가장 운이 좋은 배치도 가능한 답이 3개 남았습니다. 4개부터 처음 답이 하나인 문제가 나오고, 그런 문제는 모두 25,728개입니다. 예를 들면 이런 판입니다.

. . . .
3 . . 2
. 1 4 .
. . . .

빈칸 12개가 이 네 숫자만으로 전부 정해집니다(답은 위 무리 1의 판입니다).

재미있는 점은 두 무리가 여기서 갈린다는 것입니다. 무리 1의 판은 힌트 4개로 답이 하나가 되는 배치가 판마다 12가지뿐인데, 무리 2의 판은 128가지나 됩니다. 무리 1은 대칭을 걸었을 때 자기 자신으로 돌아오는 방법이 무리 2의 두 배라서(그래서 판 수가 절반입니다), 힌트가 적으면 닮은 다른 판과 구분하기가 그만큼 어렵습니다.

반대쪽 끝도 봤습니다. 힌트를 12개나 줘도 답이 둘인 경우가 있습니다. 남은 빈칸 네 개가 직사각형 꼭짓점에 놓이고 그 자리에 두 숫자가 엇갈려 들어가 있으면, 두 숫자를 맞바꿔도 규칙이 깨지지 않는 경우가 있기 때문입니다. 13개 이상이면 언제나 답이 하나입니다.

9×9의 경계는 17개

9×9에서 같은 질문의 답은 17개입니다. 힌트 17개로 답이 하나인 문제는 오래전부터 수만 개가 모여 있었지만, 16개로는 정말 불가능한지가 오랫동안 증명되지 않았습니다. 2012년 게리 맥과이어 연구팀이 모든 완성판을 대상으로 컴퓨터 탐색을 돌려 16개 힌트로는 답이 하나인 문제가 없다는 것을 보였다고 알려져 있습니다.

규칙만으로 알 수 있는 부분도 있습니다. 힌트에 두 숫자가 통째로 빠져 있으면, 완성판에서 그 두 숫자를 서로 맞바꿔도 힌트와 규칙이 모두 맞습니다. 그래서 답이 하나이려면 힌트에 최소 8종류의 숫자가 보여야 합니다. 17은 이런 논리로는 나오지 않아 전수 탐색이 필요했습니다.

참고로 슬롯플레이의 스도쿠 어려움 난이도는 힌트 28개입니다. 경계인 17개보다 11개 많지만, 힌트가 줄어들 때 실마리가 얼마나 빨리 사라지는지는 난이도 글에서 따로 셌습니다.

정리하면

• 4×4 스도쿠 완성판은 288개, 6×6은 28,200,960개 — 둘 다 직접 전부 세어 확인
• 상자 규칙은 가로·세로만 지킨 판 중 4×4에서 50%, 6×6에서 3.47%만 남깁니다
• 9×9는 6,670,903,752,021,072,936,960개로 알려져 있고, 한 판씩 세면 약 3억 년
• 대칭으로 묶으면 4×4는 두 종류, 9×9는 5,472,730,538종류(알려진 값)
• 답이 하나가 되는 최소 힌트는 4×4가 4개(직접 계산), 9×9가 17개(2012년 증명)

자주 묻는 질문

9×9 스도쿠 완성판은 모두 몇 개인가요?

6,670,903,752,021,072,936,960개로 알려져 있습니다. 2005년 컴퓨터 계산으로 나온 22자리 수이며, 대칭(숫자 바꾸기, 줄 바꾸기, 뒤집기 등)으로 서로 바꿀 수 있는 판을 하나로 묶으면 5,472,730,538개가 됩니다.

4×4 스도쿠는 몇 개인가요?

288개입니다. 이 글에서 모든 판을 직접 만들어 셌습니다. 첫 줄을 늘어놓는 방법 24가지와, 첫 줄을 정했을 때 나머지를 채우는 방법 12가지를 곱한 값과 같습니다. 대칭으로 묶으면 두 종류뿐입니다.

스도쿠 문제가 언젠가 바닥나지는 않나요?

그럴 걱정은 없습니다. 9×9 완성판만 22자리 수만큼 있고, 한 완성판에서도 어느 칸을 지우느냐에 따라 다른 문제가 수없이 나옵니다.

힌트가 몇 개 이상이어야 답이 하나인가요?

9×9에서는 최소 17개입니다. 16개 이하로는 답이 하나인 문제가 없다는 것이 2012년 전수 탐색으로 증명됐다고 알려져 있습니다. 4×4에서는 이 글의 계산으로 최소 4개가 필요하고, 3개로는 어떤 배치도 답이 하나로 정해지지 않았습니다.

힌트가 많으면 언제나 답이 하나인가요?

아닙니다. 4×4에서는 힌트를 12개나 줘도 답이 두 개인 경우가 있었습니다. 남은 빈칸 네 개가 직사각형 꼭짓점에 있고 두 숫자가 엇갈려 있으면 서로 맞바꿀 수 있기 때문입니다. 그래서 문제를 만들 때는 힌트 개수가 아니라 답이 하나인지를 따로 검사합니다.

6×6 스도쿠는 몇 개인가요?

2×3 상자를 쓰는 6×6은 28,200,960개입니다. 이 글에서 모든 판을 직접 만들어 세었고 40초가 걸렸습니다. 같은 크기에서 가로·세로만 겹치지 않게 채운 판은 812,851,200개라, 상자 규칙까지 통과하는 판은 3.47%입니다.

함께 읽기

• 스도쿠 쉬움과 어려움은 뭐가 다를까 — 힌트 45개와 28개의 차이
• 스도쿠 푸는 법 — 규칙과 기초 풀이 요령
• 판이 커지면 왜 어려워질까 — 틱택토부터 오목까지
• 지뢰찾기·솔리테어·숫자야구까지 — 무료 두뇌게임 5종 정리

슬롯플레이의 스도쿠는 코인 차감이 없는 무료 두뇌게임입니다. 완료 시간은 난이도별 명예 기록으로만 남으며 현실 가치 보상은 제공하지 않습니다.

---

재현 방법. 완성판은 칸을 왼쪽 위부터 하나씩 채우며 가로·세로·상자에 겹치지 않는 숫자만 넣는 되추적(백트래킹)으로 전부 만들어 셌습니다. 6×6은 첫 줄을 고정하지 않은 전수 계산과, 첫 줄을 고정하고 720을 곱한 계산을 둘 다 돌려 같은 값을 얻었습니다. 4×4 힌트 분석은 남긴 칸이 일치하는 완성판이 자기 자신 하나뿐일 때 "답이 하나"로 셌습니다. 9×9 개수, 본질적으로 다른 판의 수, 17개 증명은 직접 계산하지 않은 알려진 결과입니다.