Задачу судоку составляют так: берут готовую решённую доску и стирают из неё цифры. Сколько же всего существует решённых досок, подходящих под правила?
Для доски 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 — 28 200 960 вариантов
Это та же доска, что в мини-судоку 6×6 приложения NumberPlace, с блоками из 2 строк и 3 столбцов. Тем же способом зададим первую строку «1 2 3 4 5 6» и посчитаем: получится 39 168 досок. Первую строку можно расставить 6 × 5 × 4 × 3 × 2 × 1 = 720 способами, поэтому
39 168 × 720 = 28 200 960
Итого 28 200 960 вариантов. Это примерно в 100 000 раз больше, чем для 4×4.
Для доски 9×9 — около 6,67 × 10 в степени 21
Число решённых досок 9×9 равно
6 670 903 752 021 072 936 960
то есть примерно 6,67 × 10 в степени 21 (около 6,67 секстиллиона). Его нашли в середине 2000-х годов: доску разбили на полосы и блоки, разобрали случаи и посчитали на компьютере. Даже если считать по 100 миллионов вариантов в секунду, на это ушло бы больше двух миллионов лет.
Среди этих досок много таких, которые выглядят одинаково и отличаются лишь поворотом, отражением или переименованием цифр. Если считать такие «просто переставленные» доски одной, их остаётся около 5,5 миллиарда.
Задач ещё больше
Из одной решённой доски можно по-разному стирая цифры составить много разных задач. Приложение NumberPlace каждый раз создаёт решённую доску на месте и стирает из неё цифры, так получается задача (как составляют судоку). Встретить одну и ту же задачу дважды почти невозможно.
Сколько цифр нужно оставить, чтобы решение было единственным, рассказано в статье Какое наименьшее число подсказок?
