Математика судоку

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

Математику можно использовать для изучения головоломок судоку , чтобы ответить на такие вопросы, как «Сколько существует заполненных сеток судоку?», «Каково минимальное количество подсказок в правильной головоломке?» и «Какими способами сетки судоку могут быть симметричными?», используя комбинаторику и теорию групп .

Анализ судоку обычно делится на анализ свойств нерешённых головоломок (таких как минимально возможное количество данных подсказок) и анализ свойств решённых головоломок. Первоначальный анализ был в основном сосредоточен на перечислении решений, и результаты впервые появились в 2004 году. ^[1]

Для классического судоку количество заполненных сеток составляет 6 670 903 752 021 072 936 960 (6,671 × 10 ²¹ ), что сводится к 5 472 730 538 существенно различных решений при преобразованиях, сохраняющих действительность. Существует 26 возможных типов симметрии , но они могут быть найдены только в примерно 0,005% всех заполненных сеток. Обычная головоломка с единственным решением должна иметь не менее 17 подсказок. Существует решаемая головоломка с не более чем 21 подсказкой для каждой решенной сетки. Самая большая минимальная головоломка, найденная до сих пор, имеет 40 подсказок в 81 ячейке.

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

Было найдено много судоку с 17 подсказками, хотя их поиск — нетривиальная задача. ^{[2] [3]} В статье 2014 года Гари МакГвайра, Бастиана Тугемана и Жиля Сиварио было доказано, что минимальное количество подсказок в любой правильной судоку составляет 17 с помощью исчерпывающего компьютерного поиска, основанного на перечислении множеств попаданий . ^[4]

Наименьшее количество подсказок в судоку с двусторонней диагональной симметрией (симметрия вращения 180°) считается равным 18, и по крайней мере в одном случае такой судоку также демонстрирует автоморфизм . Известно, что существует судоку с 24 подсказками, диэдральной симметрией (симметрия вращения 90°, которая также включает симметрию относительно обеих ортогональных осей, симметрию вращения 180° и диагональную симметрию), но неизвестно, является ли это количество подсказок минимальным для этого класса судоку. ^[5]

Число минимальных судоку (судоку, в которых ни одна подсказка не может быть удалена без потери уникальности решения) точно не известно. Однако статистические методы в сочетании с генератором ( 'Unbiased Statistics of a CSP – A Controlled-Bias Generator' ), ^[6] показывают, что существует приблизительно (с относительной ошибкой 0,065%):

• 3,10 × 10 ³⁷ различных минимальных головоломок,
• 2,55 × ¹⁰²⁵ минимальных головоломок, которые не являются псевдоэквивалентными (т.е. одинаковыми, но все экземпляры одной цифры заменены другой цифрой).

Существует множество вариантов судоку, частично характеризующихся размером ( N ) и формой их областей . Если не указано иное, обсуждение в этой статье предполагает классическое судоку, т. е. N =9 (сетка 9×9 и области 3×3). Прямоугольная судоку использует прямоугольные области размерностью строк-столбцов R × C. Другие варианты включают в себя области с неправильной формой или с дополнительными ограничениями (гиперкуб).

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

Решение судоку с точки зрения игрока было исследовано в книге Дени Бертье «Скрытая логика судоку» (2007) ^[7] , в которой рассматриваются такие стратегии, как «скрытые xy-цепочки».

Известно , что общая задача решения головоломок судоку на сетках n ² × n ² из n × n блоков является NP-полной . ^[8]

Головоломка может быть выражена как задача раскраски графа . ^[9] Цель состоит в том, чтобы построить 9-раскраску конкретного графа, заданную частичной 9-раскраской. Граф судоку имеет 81 вершину, по одной вершине на каждую ячейку. Вершины помечены упорядоченными парами ( x , y ), где x и y — целые числа от 1 до 9. В этом случае две различные вершины, помеченные ( x , y ) и ( x ′, y ′), соединены ребром тогда и только тогда, когда :

• x = x ′ (тот же столбец) или,
• y = y ′ (та же строка) или,
• ⌈ x /3 ⌉ = ⌈ x ′/3 ⌉ и ⌈ y /3 ⌉ = ⌈ y ′/3 ⌉ (та же ячейка 3×3)

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

Сетка решения судоку также представляет собой латинский квадрат . ^[9] Существует значительно меньше сеток судоку, чем латинских квадратов, поскольку судоку накладывает дополнительные региональные ограничения.

Как и в случае латинских квадратов, таблицы (сложения) или умножения ( таблицы Кэли ) конечных групп могут быть использованы для построения судоку и связанных с ними таблиц чисел. А именно, необходимо учитывать подгруппы и факторгруппы :

Возьмем, к примеру, группу пар, добавляя каждый компонент отдельно по модулю некоторого . Опуская один из компонентов, мы внезапно оказываемся в (и это отображение, очевидно, совместимо с соответствующими добавлениями, т.е. это гомоморфизм групп ). Говорят также, что последняя является фактор-группой первой, потому что некоторые когда-то различные элементы становятся равными в новой группе. Однако это также подгруппа, потому что мы можем просто заполнить недостающий компонент с помощью , чтобы вернуться к .${\displaystyle \mathbb {Z} _{n}\oplus \mathbb {Z} _{n}}$${\displaystyle n}$${\displaystyle \mathbb {Z} _{n}}$${\displaystyle 0}$${\displaystyle \mathbb {Z} _{n}\oplus \mathbb {Z} _{n}}$

В этом представлении мы записываем пример, Сетка 1 , для .${\displaystyle n=3}$

Каждая область судоку выглядит одинаково на втором компоненте (а именно как подгруппа ), потому что они добавляются независимо от первого. С другой стороны, первые компоненты равны в каждом блоке, и если мы представим каждый блок как одну ячейку, эти первые компоненты показывают один и тот же шаблон (а именно факторгруппу ). Как указано в статье о латинских квадратах, это латинский квадрат порядка .${\displaystyle \mathbb {Z} _{3}}$${\displaystyle \mathbb {Z} _{3}}$${\displaystyle 9}$

Теперь, чтобы получить судоку, давайте переставим строки (или, что эквивалентно, столбцы) таким образом, чтобы каждый блок был перераспределен ровно один раз в каждом блоке – например, упорядочим их . Это, конечно, сохраняет свойство латинского квадрата. Более того, в каждом блоке строки имеют различную первую компоненту по построению, и каждая строка в блоке имеет различные записи через вторую компоненту, потому что вторые компоненты блоков изначально образовывали латинский квадрат порядка (из подгруппы ). Таким образом, мы приходим к судоку (переименуйте пары в числа 1...9, если хотите). С примером и перестановкой строк выше мы приходим к Grid 2 .${\displaystyle 1,4,7,2,5,8,3,6,9}$${\displaystyle 3}$${\displaystyle \mathbb {Z} _{3}}$

Сетка 1 – Таблица сложения в${\displaystyle \mathbb {Z} _{3}\oplus \mathbb {Z} _{3}}$ (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (2,0) (2,1) (2,2) (2,1) (2,2) (2,0) (2,2) (2,0) (2,1) (0,0) (0,1) (0,2) (0,1) (0,2) (0,0) (0,2) (0,0) (0,1) (1,0) (1,1) (1,2) (1,1) (1,2) (1,0) (1,2) (1,0) (1,1)

Сетка 2 – Создание судоку (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (2,0) (2,1) (2,2) (0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (1,1) (1,2) (1,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (2,1) (2,2) (2,0) (0,1) (0,2) (0,0) (1,1) (1,2) (1,0) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (1,2) (1,0) (1,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (2,2) (2,0) (2,1) (0,2) (0,0) (0,1) (1,2) (1,0) (1,1)

Для того, чтобы этот метод работал, обычно не требуется произведение двух групп одинакового размера. Так называемая короткая точная последовательность конечных групп соответствующего размера уже делает эту работу. Попробуйте, например, группу с фактор- и подгруппой . Кажется очевидным (уже из аргументов перечисления), что не все судоку можно сгенерировать таким образом.${\displaystyle \mathbb {Z} _{4}}$${\displaystyle \mathbb {Z} _{2}}$

Судоку, области которого не являются (обязательно) квадратными или прямоугольными, известно как Jigsaw Sudoku. В частности, квадрат N × N , где N является простым числом, может быть выложен только нерегулярными N -мино . Для малых значений N было вычислено количество способов замостить квадрат (исключая симметрии) (последовательность A172477 в OEIS ). ^[10] Для N ≥ 4 некоторые из этих мозаик несовместимы ни с одним латинским квадратом; т. е. все головоломки судоку на такой мозаике не имеют решения. ^[10]

Ответ на вопрос «Сколько существует сеток судоку?» зависит от определения того, когда похожие решения считаются различными.

Для перечисления всех возможных решений два решения считаются различными, если какие-либо из соответствующих им (81) значений ячеек различаются. Симметрийные отношения между похожими решениями игнорируются, например, повороты решения считаются различными. Симметрии играют важную роль в стратегии перечисления, но не в подсчете всех возможных решений.

Первое известное решение для полного перечисления было опубликовано QSCGZ (Гюнтером Стертенбринк) в группе новостей rec.puzzles в 2003 году ^{[11] [12],} в результате чего было получено 6 670 903 752 021 072 936 960 (6,67 × 10 ²¹ ) различных решений.

В исследовании 2005 года Фельгенгауэр и Джарвис ^{[13] [12]} проанализировали перестановки верхней полосы, используемые в допустимых решениях. После того, как были определены симметрии Band1 и классы эквивалентности для частичных сеточных решений, были построены и подсчитаны завершения нижних двух полос для каждого класса эквивалентности. Суммирование завершений по классам эквивалентности, взвешенных по размеру класса, дает общее количество решений как 6 670 903 752 021 072 936 960, подтверждая значение, полученное QSCGZ. Впоследствии это значение было подтверждено много раз независимо. Позднее был разработан второй метод перечисления, основанный на генерации полос, который является значительно менее вычислительно интенсивным. Этот последующий метод привел к необходимости примерно 1/97 от количества циклов вычислений, как и исходные методы, но был значительно сложнее в настройке.

Точная структура группы симметрии судоку может быть выражена кратко с помощью сплетения (≀ ) . Возможные перестановки строк (или столбцов) образуют группу, изоморфную S ₃ ≀ S ₃ порядка 3! ⁴ = 1,296. ^[4] Вся группа перестановок формируется путем применения операции транспонирования (изоморфной C ₂ ) к двум копиям этой группы, одной для перестановок строк и одной для перестановок столбцов. Это S ₃ ≀ S ₃ ≀ C ₂ , группа порядка 1,296 ² × 2 = 3,359,232. Наконец, операции перемаркировки коммутируют с операциями перестановки, поэтому полная группа судоку (VPT) равна ( S ₃ ≀ S ₃ ≀ C ₂ ) × S ₉ порядка 1 218 998 108 160.

Множество эквивалентных сеток, которые могут быть получены с помощью этих операций (исключая перемаркировку), образует орбиту сеток под действием группы перестановок . Число существенно различных решений тогда равно числу орбит, которое может быть вычислено с помощью леммы Бернсайда . Неподвижные точки Бернсайда — это сетки, которые либо не изменяются при операции перестановки, либо отличаются только перемаркировкой. Для упрощения вычислений элементы группы перестановок сортируются по классам сопряженности , все элементы которых имеют одинаковое количество неподвижных точек. Оказывается, только 27 из 275 классов сопряженности группы перестановок имеют неподвижные точки; ^[14] эти классы сопряженности представляют различные типы симметрии (самоподобие или автоморфизм), которые можно найти в завершенных сетках судоку. Используя эту технику, Эд Рассел и Фрейзер Джарвис первыми вычислили количество существенно различных решений судоку, которое составило 5 472 730 538. ^{[14] [15]}

За исключением перемаркировки, все операции группы симметрии судоку состоят из перестановок ячеек, которые сохраняют решение , что поднимает вопрос о том, все ли такие перестановки ячеек, сохраняющие решение, находятся в группе симметрии. В 2008 году Авив Адлер и Илан Адлер показали, что все перестановки ячеек, сохраняющие решение, содержатся в группе, даже для общих сеток. ^[16]${\displaystyle n^{2}\times n^{2}}$

• Комбинаторный взрыв (с кратким изложением количества сеток судоку в сравнении с латинскими квадратами)
• Танцевальные ссылки
• Глоссарий судоку
• Судокян
• Код судоку

• Розенхаус, Джейсон ; Таалман, Лора (2011). Серьёзное отношение к судоку: математика, лежащая в основе самой популярной в мире головоломки с карандашом . Oxford University Press.

• Алгоритм разностной карты В. Элзера также решает судоку
• Головоломка «Судоку» — упражнение по программированию в ограничениях и Visual Prolog 7 Карстена Келера Холста (в Visual Prolog )
• В книге «Квадраты судоку и хроматические многочлены» Герцберга и Мёрти головоломки судоку рассматриваются как задачи раскраски вершин в теории графов .