Задачу судоку составляют так, чтобы по цифрам, стоящим в начале (подсказкам), решение определялось единственным образом. Если подсказок слишком мало, решений становится два и больше. Сколько же подсказок нужно как минимум?

Для 9×9 — 17

На доске 9×9 есть задачи, в которых решение определяется 17 подсказками. А при 16 и меньше подсказках, как считается, задач с единственным решением нет.

То, что 16 недостаточно, показали примерно в 2012 году, перебрав компьютером огромное число случаев. Решённых досок примерно 6,67 × 10 в степени 21 (Сколько существует решённых судоку), поэтому, как считается, их не просто перебирали, а многократно придумывали способы сократить область поиска.

Проверим на доске 4×4

Маленькую доску 4×4 (блоки 2×2, цифры от 1 до 4) можно проверить целиком. Для каждой из 288 решённых досок перебрали все способы выбрать подсказки, и вот что получилось.

ПодсказкиСпособы выбора с единственным решением
30
425 728

При трёх подсказках, как их ни выбирай, решение единственным не будет. При четырёх подсказках есть задачи с единственным решением. Например, такая.

112233441243

Подсказок всего четыре, но решение только одно.

112233441234341221434321

То есть на доске 4×4 наименьшее число подсказок — 4.

Почему в подсказках нужно 8 разных цифр

В задаче 9×9 с единственным решением в подсказках есть как минимум 8 разных цифр. Причина простая.

Допустим, что среди подсказок нет ни 7, ни 8. Если в решённой доске поменять местами все 7 и 8, подсказки не изменятся и правила останутся соблюдёнными. Тогда получится два решения. Поэтому цифр, которых нет среди подсказок, может быть не больше одной.

Много подсказок — тоже не всегда хорошо

Даже если подсказок 17 или больше, при некоторой расстановке решений может быть два и больше. Единственность решения определяется не числом подсказок, а расстановкой.

И чем меньше подсказок, тем труднее задача, тоже не всегда. Сложность определяется тем, какие приёмы нужны для решения (Самое трудное судоку в мире).

В режиме 9×9 приложения NumberPlace составляются задачи, где в начале стоит от 22 до 40 цифр. Каждая задача выдаётся только после проверки, что у неё одно решение и что её можно решить до конца одними приёмами.