Задачу судоку составляют так, чтобы по цифрам, стоящим в начале (подсказкам), решение определялось единственным образом. Если подсказок слишком мало, решений становится два и больше. Сколько же подсказок нужно как минимум?
Для 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 |
При трёх подсказках, как их ни выбирай, решение единственным не будет. При четырёх подсказках есть задачи с единственным решением. Например, такая.
Подсказок всего четыре, но решение только одно.
То есть на доске 4×4 наименьшее число подсказок — 4.
Почему в подсказках нужно 8 разных цифр
В задаче 9×9 с единственным решением в подсказках есть как минимум 8 разных цифр. Причина простая.
Допустим, что среди подсказок нет ни 7, ни 8. Если в решённой доске поменять местами все 7 и 8, подсказки не изменятся и правила останутся соблюдёнными. Тогда получится два решения. Поэтому цифр, которых нет среди подсказок, может быть не больше одной.
Много подсказок — тоже не всегда хорошо
Даже если подсказок 17 или больше, при некоторой расстановке решений может быть два и больше. Единственность решения определяется не числом подсказок, а расстановкой.
И чем меньше подсказок, тем труднее задача, тоже не всегда. Сложность определяется тем, какие приёмы нужны для решения (Самое трудное судоку в мире).
В режиме 9×9 приложения NumberPlace составляются задачи, где в начале стоит от 22 до 40 цифр. Каждая задача выдаётся только после проверки, что у неё одно решение и что её можно решить до конца одними приёмами.
