스도쿠 문제는 답이 되는 “완성된 판”에서 숫자를 지워서 만들어요. 그렇다면 규칙을 만족하는 완성된 판은 모두 몇 가지일까요?
4×4 판은 288가지
가장 작은 4×4(2×2 박스, 1~4)로 생각해 봐요. 예를 들면 다음과 같은 판이에요.
세로·가로·박스 어디에나 1~4가 하나씩 들어 있어요. 이런 판을 컴퓨터로 하나씩 전부 세어 보면 288가지가 있었어요.
첫 행을 정하면 세기 쉬워져요
전부를 세지 않고도 잘 줄이는 아이디어가 있어요.
완성된 판의 숫자는 “1과 2를 서로 바꾼다”처럼 이름을 바꿔도 여전히 완성된 판이에요. 첫 행이 “2 1 3 4”인 판도 1과 2를 바꾸면 첫 행이 “1 2 3 4”인 판이 돼요. 즉,
- 첫 행이 “1 2 3 4”인 판만 세고,
- 첫 행을 늘어놓는 방법의 수(4×3×2×1=24가지)를 곱하면
전체 수를 알 수 있어요. 4×4에서는 첫 행이 “1 2 3 4”인 판이 12가지라서, 12×24=288가지예요.
6×6 판은 2820만 960가지
NumberPlace의 6×6 미니와 같은 2행×3열 박스의 판이에요. 같은 방법으로 첫 행을 “1 2 3 4 5 6”으로 정하고 세면 39,168가지가 있었어요. 첫 행을 늘어놓는 방법은 6×5×4×3×2×1=720가지니까,
39,168 × 720 = 28,200,960
으로 2820만 960가지예요. 4×4의 약 10만 배가 돼요.
9×9 판은 약 6.67×10의 21제곱 가지
9×9의 완성된 판은
6,670,903,752,021,072,936,960 가지
로, 약 6.67×10의 21제곱 가지(대략 67해 가지)로 알려져 있어요. 2000년대 중반에 판을 띠와 박스로 나눠 경우를 나누고, 컴퓨터로 세어서 구했어요. 1초에 1억 가지씩 세어도 200만 년이 넘게 걸리는 수예요.
이 안에는 판을 돌리거나 뒤집거나 숫자의 이름을 바꾸기만 했을 뿐 같아 보이는 것도 아주 많이 들어 있어요. 이런 “보기만 바꾼” 것을 같은 것으로 보면 약 55억 가지까지 줄어든다고 해요.
문제는 훨씬 더 많아요
하나의 완성된 판에서 숫자를 지우는 방법을 바꾸면 다른 문제를 여러 개 만들 수 있어요. NumberPlace는 매번 그 자리에서 완성된 판을 만들고, 거기서 숫자를 지워 문제를 만들어요(스도쿠 만드는 법). 같은 문제를 만날 일은 거의 없어요.
몇 개를 남겨야 답이 하나로 정해지는지는 힌트는 최소 몇 개?에서 소개해요.
