Привет Хабр! Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).



К сожалению, оригинал данной статьи написан для дебилов очень широкого круга читателей, в том плане, что тема рассматривается не очень глубоко, но довольно подробно. При этом поясняется только общий подход к решению задачи, без технических деталей, и, фактически, обрывается на самом интересном месте формулировкой «ну а дальше они посчитали на компьютере». В итоге я немного дополнил изложение своими комментариями: они либо отмечены курсивом, либо спрятаны под спойлеры. В них раскрываются некоторые технические моменты более подробно. Возможно, пост вместе с этими комментариями суммарно тянет на полноценную статью, нежели чем на просто перевод, но я решил оставить все как есть (на самом деле, я не нашел кнопки перевода перевода обратно в обычную статью, а создавать новую публикацию только ради этого было лень).

Введение

Судоку — это головоломка, которая завоевала мировую популярность с 2005 года. Для того, чтобы решить судоку, нужны только логика и метод проб и ошибок. Сложная математика появляются лишь при более пристальном рассмотрении: для подсчета количества различных сеток судоку нужна комбинаторика, чтобы определить количество этих сеток без учета всевозможных симметрий понадобится теория групп, а для решения судоку в промышленных масштабах — теория сложности алгоритмов.

Впервые головоломка судоку в известном нам виде была опубликована в 1979 году в американском журнале Dell Magazines под названием «Numbers in Place» за авторством Говарда Гэрнса (Howard Garns). В 1984 году судоку впервые было опубликовано в Японии в журнале Nikoli. Именно Маки Кадзи (Maki Kaji), президент компании Nikoli (которая, кстати, специализируется на всяких пазлах и логических играх), дал головоломке название «судоку», что в переводе с японского означает «одинокие числа». Когда игра стала популярной в Японии, на нее обратил внимание новозеландец Вэйн Гулд (Wayne Gould). Вэйн написал программу, которая могла генерировать сотни судоку. В 2004 году он опубликовал некоторые из этих пазлов в Лондонских газетах. Вскоре после этого лихорадка судоку охватила всю Англию. В 2005 году головоломка стала популярной в Соединенных Штатах. Судоку стали регулярно публиковаться во множестве газет и журналов, радуя людей по всему миру.

Классическая версия судоку имеет вид квадратной таблицы 9?9, итого — 81 ячейка. Эта таблица разделена на 9 блоков 3?3. В некоторых ячейках находятся числа из множества {1,2,3,4,5,6,7,8,9} (эти числа нельзя менять), остальные ячейки пусты. Цель игры — заполнить все пустые ячейки, используя только вышеупомянутые девять чисел, так, чтобы на каждой горизонтали, на каждой вертикали, а также в каждом блоке каждое из чисел присутствовало бы ровно один раз. Мы будем называть эти ограничения Главным Правилом игры.

Описанные выше правила относятся к судоку порядка 3. В общем же случае, судоку порядка n — это таблица n²?n², разделенная на n² блоков размера n?n каждый. И все это нужно заполнить числами от 1 до n² так, чтобы выполнялось Главное Правило.

Например, на следующей картинке можно видеть пример судоку, а также его решение:

Подходы к решению

Говорят, для решения судоку не нужна математика — это не правда. Это на самом деле означает, что не нужна только арифметика. Головоломка не зависит от того факта, что мы используем цифры от 1 до 9. Мы можем с легкостью заменить эти 9 цифр на буквы, цвета или сорта суши. Фактически, для решения судоку нужно применять такой вид математического мышления, как логическая дедукция.

Самая простая эвристика для решения судоку — сначала для каждой пустой клетки выписать всевозможные числа, которые туда можно записать, не противореча Главному Правилу, ориентируясь по числам, данным изначально. Если для какой-то ячейки возможен только один вариант — именно его нужно записать в эту ячейку.

Другой подход для решения — выбрать число, а после этого — строку, столбец или блок. После этого следует рассмотреть все позиции в строке/столбце/блоке и проверить, можно ли туда поместить выбранное число, не нарушая Главного Правила. Если число подходит только для одной позиции — можно смело его туда вписать. Как только это будет сделано, выбранное число может быть исключено из возможных вариантов для всех остальных пустых ячеек в соответствующих строке, столбце и блоке.

Обычно этих двух правил не достаточно для полного заполнения сетки судоку. Часто требуется более сложные методы для достижения прогресса, а иногда требуется перебирать варианты и откатываться в случае неудачного выбора. Более изощренная стратегия состоит в том, чтобы рассмотреть пары или тройки ячеек в строке, столбце или блоке. Может оказаться, что для рассматриваемой пары ячеек подходят только два числа из группы, но непонятно какое из них в какую из этих двух ячеек поместить. Однако, из этого можно заключить, что числа из данной пары не могут появиться на каких либо других местах в рассматриваемой группе. Это уменьшает количество вариантов в других пустых ячейках и помогает подобраться ближе к решению. Аналогично, если тройку чисел можно поместить только в определенную тройку позиций (непонятно в каком порядке), то эти три числа можно исключить из рассмотрения для всех остальных ячеек по соседству.

Заметим, что кроме данных эвристик существует множество других. Вы даже можете придумать свои собственные стратегии решения.

Когда ни одна из простых эвристик не помогает — нужно попробовать выбрать пустую ячейку с наименьшим числом вариантов и попробовать один из вариантов. В случае получения противоречия (повторяющиеся числа в строке, столбце или блоке) следует отменить все свои действия до момента выбора и попробовать другой вариант.

Упражнение: Попробуйте применить описанные выше методы на этом судоку:


В интернете можно найти множество других судоку любой сложности и на любой вкус.

Так сколько же их?

Это очень интересный вопрос. Так сколько же различных судоку 9?9? Сколькими способами можно заполнить таблицу 9?9 числами от 1 до 9 так, чтобы выполнялось Главное Правило? Мы опишем метод, с помощью которого Бертрам Фельгенхауэр (Bertram Felgenhauer) и Фразер Джарвис (Frazer Jarvis) посчитали это количество в начале 2006 года.

Сначала договоримся об обозначениях. Будем называть полосой тройку блоков, центры которых расположены на одной горизонтали. Итого мы имеем три полосы — верхнюю, нижнюю и среднюю. Стеком будем называть тройку блоков, центры которых расположены на одной вертикали. Стеков, как и полос, у нас тоже три — левый, правый и средний. Ячейку на пересечении i-й строки и j-го столбца будем обозначать как (i,j).

Приготовления окончены и мы готовы посчитать число N — количество различных судоку. Сперва обозначим все блоки судоку следующим образом:


Сколькими способами можно заполнить блок B1? Поскольку для блока B1 у нас 9 чисел, одно для кажой ячейки, в первую из них мы можем записать одно из чисел одним из 9 способов. Для каждого из этих 9 способов у нас есть 8 способов разместить одно из оставшихся чисел ровно 8 способами. Для третьей ячейки для каждого из этих 9?8 способов количество вариантов идти дальше — ровно 7. Мы, по сути, пытаемся построить всевозможные перестановки длины 9 и нужное нам количество способов заполнить блок B1 равно количеству этих перестановок — 9! = 9?8?7?6?7?4?3?2?1 = 362880. Начиная с судоку, в котором блок B1 заполнен определенным образом, мы можем получить судоку с любым другим заполнением блока B1 с помощью простого переобозначния чисел (вспомним, что нам неважно какие числа где находятся — главное знать где одинаковые числа, а где различные). Поэтому, для простоты, заполним блок B1 числами от 1 до 9 в порядке, показанном на рисунке:


Пусть количество судоку, в которых блок B1 заполнен именно так, как на картинке, равно N1. Общее количество судоку будет N1?9!, отсюда N1=N/9!.

Рассмотрим все способы заполнить первую строку в блоках B2 и B3. Поскольку 1, 2 и 3 уже присутствуют в блоке B1, эти числа больше не могут быть использованы в данной строке. Только числа 4, 5, 6, 7, 8 и 9 из второй и третьей строк блока B1 могут быть использованы в первой строке блоков B2 и B3.

Упражнение: Перечислите все возможные способы заполнения первой строки в блоках B2 и B3 с точностью до перестановки цифр. Подсказка: всего имеется десять способов разбиения шести чисел на две части по три, а меняя B2 на B3, мы получаем еще десять способов. Итого — двадцать.

Назовем два из этих вариантов чистыми верхними строками: когда числа {4,5,6}, как во второй строке блока B1 располагаются вместе в B2, а числа {7,8,9}, как в третьей строке блока B1, располагаются вместе в B3 (ну и случай, когда B2 и B3 поменяны местами). Все остальные способы — это смешанные верхние строки, поскольку там в первой строке B2 и B3 множества {4,5,6} и {7,8,9} смешаны друг с другом.

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

Упражнение: Подумайте немного о том, как можно заполнить первую полосу начиная с чистой верхней строки 1,2,3;{4,5,6};{7,8,9} (мы пишем a,b,c, если три числа идут в зафиксированном порядке и {a,b,c}, если эти числа могут идти в любом порядке). Сколько всего есть способов, считая различные способы порядка в B2 и B3? Верно, что этих способов столько же, сколько и для другой чистой строки 1,2,3;{7,8,9};{4,5,6}?

Помните, мы не меняем порядок в блоке B1, поскольку мы уже учитываем колчество сеток, которые получаются путем перемешивания девяки чисел в B1.

Оказывается, для чистой верхней строки 1,2,3;{4,5,6};{7,8,9} — ровно (3!)⁶ способов, поскольку нам обязательно нужно поместить {7,8,9};{1,2,3} на вторую строку в блоках B2 и B3, а {1,2,3};{4,5,6} — на третью строку. После этого мы можем произвольным образом менять местами числа в этих шести тройках в B2 и B3 для того, чтобы получить все конфигурации. Для второй чистой верхней строки ответ тот же, поскольку все, что мы меняется местами — это блоки B2 и B3.

Для случая смешанных верхних строк все неммого сложнее. Давайте рассмотрим верхнюю строку 1,2,3;{4,6,8};{5,7,9}. Далее первую полосу можно заполнить так, как показано на картинке ниже, где a, b и c — это числа 1, 2, 3 в любом порядке.


Как только число a выбрано, b и c — это оставшиеся два числа в любом порядке, поскольку они находятся в одних и тех же строках. Для a три способа выбора, а затем мы можем просто перемешать числа в шести тройках в B2 и B3 в любом порядке — и всегда будет получаться подходящая первая полоса. Итого, количество конфигураций — 3x(3!)⁶. Несложно показать, что в оставшихся семнадцати способах мы получим то же самое число.

Теперь мы можем посчитать общее количество различных верхних полос для фиксированного блока B1: 2х(3!)⁶+18x3x(3!)⁶=2612736. Первая часть суммы — это количество полос для чистых верхних полос, а вторая — для смешанных.

Вместо того, чтобы посчитать количество разничных полностью заполненных сеток для каждого из этих 2612736 вариантов, Фельгенхауэр и Джарвис сначала определили у каких из этих верхних полос одно и то же количество вариантов полного заполнения. Этот анализ сокращает количество полос, которые нам нужно будет рассмотреть для дальнейших рассчетов.

Есть несколько операций, которые оставляют количество полностью заполненных сеток неизменным: переназначение чисел, перестановка любых блоков в первой полосе, перемешивание столбцов в любом блоке, изменение порядка трех строк в полосе. Как только какие либо из операций меняют порядок чисел в B1 — мы просто переназначаем числа так, чтобы привести блок B1 к стандартному виду.

Когда мы меняем местами блоки B1, B2 и B3 — количество заполнений сеток сохраняется, поскольку мы начинаем с корректной сетки судоку, и единственный способ сохранить корректность в дальнейшем — это поменяить местами B4, B5, B6 и B7, B8, B9 так, как мы поменяли B1, B2, B3. В итоге все стеки останутся теми же самыми. Другими словами, каждое корректное заполнение всей сетки для одной верхней полосы дает ровно одно корректное заполнение сетки для другой верхней полосы, полученной перемешиванием блоков B1, B2, B3.

Упражнение: Убедитесь сами, что если поменять местами блоки B2 и B3 в следующей сетке, то единственный способ сохранить сетку корректной — это поменять местами B5 и B6, а также B8 и B9. Стеки остаются те же самые, но меняются их расположения.


Упражнение: Пусть у вас есть корректно заполненная сетка судоку и вы меняете местами некоторые столбцы в каком либо из блоков B1, B2 или B3. Что нужно дополнительно сделать с остальными столбцами, чтобы сетка судоку осталась корректной? Например, если вы поменяли местами первый и второй столбцы в блоке B2, как бы вы исправили оставшуюся часть сетки так, чтобы она все еще удовлетворяла Главному Правилу?

Последнее упражнение говорит нам о том, что каждое заполнение первой полосы дает нам уникальное заполнение для такой первой полосы, в которой столбцы упорядочены определенным образом внутри блоков.

Это наблюдение позволяет нам уменьшить количество первых полос, которые нам нужно рассмотреть. Согласно Фельгенхауэру и Джарвису, мы перемешиваем столбцы в блоках B2 и B3 таким образом, что значения в самой верхней строке идут в возрастающем порядке. После этого мы возможно меняем местами блоки B2 и B3 так, чтобы самое первое число в блоке B2 (левое верхнее) было меньше, чем самое первое число в блоке B3. Эта операция называется лексикографической редукцией. Поскольку для каждого из двух блоков у нас ровно 6 различных перестановок и всего 2 способа упорядочить блоки друг относительно друга, лексикографическая редукция говорит нам, что для любой первой полосы можно построить класс из 6²?2=72 первых полос с одним и тем же количеством полных заполнений сеток (и для всех элементов из каждого класса это построение будет приводить к этому же классу). Таким образом, нам теперь нужно рассмотреть только 2612736/72=36288 первых полос.


Для каждого из этих вариантов рассмотрим всевозможные перестановки трех верхних блоков: их ровно 6. А для каждого из этих вариантов имеется 6³ перестановок столбцов внутри всех блоков. После того, как мы все перемешали, вы переназначаем числа так, чтобы в блоке B1 они все шли в стандартном порядке. Мы также можем произвольно перемешать три верхние строки, после чего опять переназначить числа, чтобы блок B1 стал стандартным. После каждой из этих операций количество заполнение всей сетки для данной первой полосы останется неизменным. Фельгенхауэр и Джарвис при помощи компьютерной программы определили, что эти операции сокращают количество первых полос, которые имеет смысл рассматривать, с 36288 до всего лишь 416.

Упражнение: Рассмотрите определенную первую полосу. Проделайте над ней некоторые операции, которые сохраняют количество заполнений всей сетки судоку. Можете начать со следующего: поменяйте местами первую и вторую строки. После этого переназначьте числа в блоке B1, чтобы привести его к стандартной форме. Выполните лексикографическую редукцию.

Главное, на что следует обратить внимание: полоса, с которой мы начали, и полоса, которой закончили, имеют одинаковое количество заполнения всей сетки судоку. Поэтому вместо вычисления количества заполнений сеток для каждой полосы мы можем подсчитывать их количество только для одной из них.



Существует еще несколько операций, которые сокращают количество сеток для рассмотрения. Если у нас есть пара чисел {a,b} такая, что a и b находятся в одном столбце, причем a — на i-й строке, а b — на j-ой, и, ко всему прочему, есть такая же пара в другом столбце, причем для этого столбца a уже находится на j-ой строке, а b — на i-ой (т.е. эти четыре числа находятся в углах некоторого прямоугольника, и противоположные числа равны), то мы можем поменять местами числа в обеих парах и получить новую корректную полосу с тем же количеством конечных сеток. Например, в судоку, приведенном чуть выше, числа 8 и 9 в шестом и девятом столбцах формируют такую конфигурацию. Рассмотрев все возможные случаи, Фельгенхауэр и Джарвис сократили необходимое для рассмотрения число первых полос с 416 до 174.

Но и это еще не все. Они рассмотрели другие конфигурации одинаковых множеств (из трех и более чисел), лежащих друг напротив друга в двух различных столбцах или строках, которые можно поменять местами и ответ от этого не изменится. Это сокращает количество вариантов до 71, а если дополнительно рассмотреть эти варианты и применить там более сложные симметрии — количество полос для рассмотрения можно сократить до 44. И для каждой из этих 44 полос все остальные полосы в соответствующем классе имеют такое же количество полных заполнений всей сетки.


Пусть C — одна из 44 полос. Тогда количество способов, которым C можно дополнить до полной сетки судоку, обозначим на n_C. Нам также понадобится число m_C — общее количество полос, для которых количество конечных заполнений такое же, как и у C. Когда общее количество различных судоку будет равно N=?_Cm_Cn_C, то есть сумма m_Cn_C по всем 44 полосам.

Фельгенхауэр и Джарвис написали компьютерную программу для выполнения итоговых рассчетов. Они вычислили число N1 (количество корректных заполнений, в которых B1 в стандартной форме) для каждой из 44 полос. Затем они умножили это число за 9!, чтобы получить ответ. Они обнаружили, что количество всевозможных корректных сеток судоку 9 на 9 равно N=6670903752021072936960, что приблизительно равно 6.671?10²¹.

Продолжение следует

В следующей части мы посчитаем количество действительно различных судоку, считая что два судоку одинаковые, если они переходят друг в друга поворотами, отражениями, перемешиванием столбцов и так далее. Для этого мы погрузимся в теорию групп, познакомимся с леммой Бернсайда и, конечно же, напишем аццкую программу для подсчета ответа. В общем, не пропустите.