Посчитайте способы заполнить решётку 9 × 9 так, чтобы каждая строка, каждый столбец и каждый блок содержали цифры от 1 до 9 по одному разу. Ответ — 6 670 903 752 021 072 936 960, и первая ссылка показывает это как 6.6709037520211⋅10+21 через разложение на простые множители 2²⁰·3⁸·5·7·27 704 267 971; вторая, третья и четвёртая ссылки — три из этих множителей, 9!, 2²⁰ и 3⁸, а большое простое в конце — то, что рождает разбор случаев, когда замкнутой формулы никто не нашёл. Фельгенхауэр и Джарвис сделали это в 2005 году, классифицировав способы, которыми можно достроить верхнюю полосу из трёх блоков, и перемножив случаи.
Почти всё это число — та же решётка в другом наряде. Переименовать цифры, переставить строки внутри полосы, поменять полосы местами, транспонировать: это симметрии головоломки, и одни только 9! способов переименования (вторая ссылка) уменьшают число в 362 880 раз, прежде чем пробуют что-либо ещё. С точностью до всех симметрий остаётся 5 472 730 538 существенно различных решёток, полученных леммой Бёрнсайда, а не делением, потому что некоторые решётки симметричны и при простом частном их насчитали бы слишком мало. Число, важное для тех, кто решает головоломки, ещё меньше: головоломка — это решётка с убранными подсказками, семнадцать — наименьшее число подсказок, которое может однозначно задать решение (доказано в 2012 году после исчерпывающего поиска, стоившего года машинного времени), а у всякой решётки с шестнадцатью или меньшим числом подсказок есть либо второе решение, либо ни одного.
Ответ
6.6709037520211⋅10+21
Как его читать
Разложение числа решёток на простые множители в поле вычислений. Вторая ссылка — 9!, число способов переименовать цифры.
Источник
Bertram Felgenhauer and Frazer Jarvis, 'Mathematics of Sudoku I', 2005, for the total number of completed grids and the 5 472 730 538 classes under symmetry; the minimum of 17 clues for a puzzle with one solution was proved by McGuire, Borgström and Sudergren in 2012
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.