스도쿠 문제는 처음에 들어 있는 숫자(힌트)만을 단서로 답이 하나로 정해지도록 만들어요. 힌트가 너무 적으면 답이 둘 이상이 되어 버려요. 그렇다면 힌트는 최소 몇 개 있으면 될까요?
9×9는 17개
9×9 판에서는 17개의 힌트로 답이 하나로 정해지는 문제가 있어요. 그리고 16개 이하로는 답이 하나로 정해지는 문제가 없다고 알려져 있어요.
16개로는 안 된다는 것은 2012년쯤 컴퓨터로 방대한 경우를 모조리 조사하는 방법으로 밝혀졌어요. 완성된 판의 수가 약 6.67×10의 21제곱 가지나 되니(스도쿠의 답은 몇 가지?), 그냥 전부 시도한 것이 아니라 조사할 범위를 잘 줄이는 궁리를 거듭해서 확인했다고 해요.
4×4에서 확인해 보기
작은 4×4(2×2 박스, 1~4)라면 전부 조사할 수 있어요. 완성된 판 288가지 각각에서 힌트를 고르는 방법을 전부 시도하면 다음과 같았어요.
| 힌트 | 답이 하나가 되는 고르는 방법 |
|---|---|
| 3개 | 0 |
| 4개 | 25,728 |
3개로는 어떻게 골라도 답이 하나로 정해지지 않아요. 4개라면 답이 하나로 정해지는 문제가 있어요. 예를 들면 다음 문제예요.
힌트는 겨우 4개지만 답은 하나뿐이에요.
즉 4×4에서는 최소 힌트가 4개예요.
힌트에 8종류의 숫자가 필요한 이유
9×9에서 답이 하나로 정해지는 문제는 힌트에 적어도 8종류의 숫자가 들어 있어요. 이유는 간단해요.
만약 힌트에 7과 8이 하나도 들어 있지 않다고 해 봐요. 답의 판에서 7과 8을 전부 서로 바꿔도 힌트는 그대로이고 규칙도 지켜져요. 그러면 답이 둘이 되어 버려요. 그래서 힌트에 나오지 않는 숫자는 많아야 한 종류뿐이에요.
힌트가 많다고 좋은 것도 아니에요
힌트가 17개 이상이라도 놓는 방식에 따라 답이 둘 이상이 될 수 있어요. 답이 하나인지는 힌트의 개수가 아니라 놓는 방식으로 정해져요.
또 힌트가 적을수록 어렵다고도 할 수 없어요. 난이도는 푸는 데 어떤 기법이 필요한지로 정해져요(세계에서 가장 어려운 스도쿠란).
NumberPlace의 9×9는 처음 숫자가 22~40개인 문제를 만들어요. 어느 문제나 답이 하나이고, 기법만으로 끝까지 풀 수 있음을 확인한 뒤에 내놓아요.
