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

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

Анализ судоку обычно делится на анализ свойств нерешенных головоломок (например, минимально возможное количество заданных подсказок) и анализ свойств решенных головоломок. Первоначальный анализ был в основном сосредоточен на перечислении решений, и результаты впервые появились в 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]

Общее количество минимальных головоломок [ править ]

Количество минимальных судоку (судоку, в которых нельзя удалить ни одной подсказки без потери уникальности решения) точно неизвестно. Однако статистические методы в сочетании с генератором ( «Непредвзятая статистика CSP – генератор с контролируемым смещением» ) ^[6] покажем, что существуют приблизительно (с относительной погрешностью 0,065%):

3.10 × 10 ³⁷ отдельные минимальные головоломки,
2.55 × 10 ²⁵ минимальные головоломки, которые не являются псевдоэквивалентными (т.е. та же схема, в которой все экземпляры одной цифры заменяются другой цифрой).

Варианты [ править ]

Существует множество вариантов судоку, частично характеризующихся размером ( 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] Сеток судоку значительно меньше, чем латинских квадратов, поскольку судоку накладывает дополнительные региональные ограничения.

Судоку из групповых таблиц [ править ]

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

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

В этом представлении мы запишем пример Grid 1 для $n=3$ .

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

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

Сетка 1 – Таблица сложения в

\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)

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

Головоломка-судоку [ править ]

Судоку, области которого не обязательно являются квадратными или прямоугольными, называется судоку-головоломкой. В частности, квадрат размера 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 ₂ , группа порядка 1296. ² × 2 = 3 359 232. Наконец, операции перемаркировки коммутируют с операциями перестановки, поэтому полная группа судоку (VPT) равна ( S ₃ ≀ S ₃ ≀ C ₂ ) × S ₉ порядка 1 218 998 108 160.

Бернсайда Фиксированные и лемма точки

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

группы Полнота симметрии судоку

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

См. также [ править ]

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

Ссылки [ править ]

^ Линь, Ке Ин (2004), «Количество судоку», Журнал развлекательной математики , 33 (2): 120–24 .
^ «Уголок чата по программированию» .ic-net.or.jp. Архивировано из оригинала 12 октября 2016 г. Проверено 20 октября 2013 г. .
^ «Минимальное судоку» . Csse.uwa.edu.au. Архивировано из оригинала 26 ноября 2006 года . Проверено 20 октября 2013 г.
^ Jump up to: Перейти обратно: ^а ^б МакГуайр, Дж.; Тугеманн, Б.; Чиварио, Г. (2014). «Судоку с 16 подсказками не существует: решение задачи судоку с минимальным количеством подсказок». Экспериментальная математика . 23 (2): 190–217. arXiv : 1201.0749 . дои : 10.1080/10586458.2013.870056 .
^ Таалман, Лаура (2007), «Относясь к судоку серьезно», Math Horizons , 15 (1): 5–9, doi : 10.1080/10724117.2007.11974720 , JSTOR 25678701 , S2CID 126371771 . См., в частности, рисунок 7, с. 7.
^ Бертье, Дени (4 декабря 2009 г.). «Непредвзятая статистика CSP - генератор с контролируемым смещением» . Проверено 4 декабря 2009 г.
^ Бертье, Дени (ноябрь 2007 г.). Скрытая логика судоку (второе, исправленное и расширенное изд.). Лулу.com. ISBN 978-1847534729 .
^ Ято, Такаюки; Сета, Такахиро (2003). «Сложность и полнота поиска другого решения и его применение к головоломкам». IEICE Transactions по основам электроники, связи и информатики . Е86-А (5): 1052–1060.
^ Jump up to: Перейти обратно: ^а ^б Льюис, Р. Руководство по раскраске графов: алгоритмы и приложения . Международное издательство Springer, 2015.
^ Jump up to: Перейти обратно: ^а ^б де Рюитер, Йохан (15 марта 2010 г.). «О головоломках-судоку и связанных с ними темах (бакалаврская диссертация)» (PDF) . Лейденский институт передовых компьютерных наук (LIACS) .
^ QSCGZ (Гюнтер Стертенбринк) (21 сентября 2003 г.). «комбинаторный вопрос на 9х9 (загадки)» . Google Дискуссионная группа . Проверено 20 октября 2013 г.
^ Jump up to: Перейти обратно: ^а ^б Джарвис, Фрейзер (2 февраля 2008 г.). «Проблемы перечисления судоку» . Домашняя страница Фрейзера Джарвиса . Университет Шеффилда . Проверено 20 октября 2013 г.
^ Фельгенгауэр, Бертрам; Джарвис, Фрейзер (20 июня 2005 г.), Перечисление возможных сеток судоку (PDF) .
^ Jump up to: Перейти обратно: ^а ^б Эд Рассел и Фрейзер Джарвис (7 сентября 2005 г.). «Существует 5472730538 существенно разных сеток судоку... и группа симметрии судоку» . Домашняя страница Фрейзера Джарвиса . Университет Шеффилда . Проверено 20 октября 2013 г.
^ Эд Рассел, Фрейзер Джарвис (25 января 2006 г.). «Математика судоку II» (PDF) .
^ Адлер, Авив; Адлер, Илан (2008). «Фундаментальные преобразования сеток судоку» (PDF) . Математический спектр . 41 (1): 2–7.

Дальнейшее чтение [ править ]

Розенхаус, Джейсон ; Таалман, Лаура (2011). Серьезное отношение к судоку: математика самой популярной в мире головоломки с карандашами . Издательство Оксфордского университета.

Внешние ссылки [ править ]

V. Elser's difference-map algorithm also solves Sudoku
Головоломка-судоку — упражнение по программированию с ограничениями и Visual Prolog 7, Карстен Келер Холст (на Visual Prolog )
Квадраты судоку и хроматические полиномы» Герцберга « и Мурти рассматривают головоломки судоку как раскраски вершин задачи в теории графов .

[1] Линь, Ке Ин (2004), «Количество судоку», Журнал развлекательной математики , 33 (2): 120–24 .

[2] «Уголок чата по программированию» .ic-net.or.jp. Архивировано из оригинала 12 октября 2016 г. Проверено 20 октября 2013 г. .

[sudokumin-3] «Минимальное судоку» . Csse.uwa.edu.au. Архивировано из оригинала 26 ноября 2006 года . Проверено 20 октября 2013 г.

[:3-4] Jump up to: Перейти обратно: ^а ^б МакГуайр, Дж.; Тугеманн, Б.; Чиварио, Г. (2014). «Судоку с 16 подсказками не существует: решение задачи судоку с минимальным количеством подсказок». Экспериментальная математика . 23 (2): 190–217. arXiv : 1201.0749 . дои : 10.1080/10586458.2013.870056 .

[5] Таалман, Лаура (2007), «Относясь к судоку серьезно», Math Horizons , 15 (1): 5–9, doi : 10.1080/10724117.2007.11974720 , JSTOR 25678701 , S2CID 126371771 . См., в частности, рисунок 7, с. 7.

[Unbiased_Statistics_of_a_CSP_-_A_Controlled-Bias_Generator-6] Бертье, Дени (4 декабря 2009 г.). «Непредвзятая статистика CSP - генератор с контролируемым смещением» . Проверено 4 декабря 2009 г.

[7] Бертье, Дени (ноябрь 2007 г.). Скрытая логика судоку (второе, исправленное и расширенное изд.). Лулу.com. ISBN 978-1847534729 .

[8] Ято, Такаюки; Сета, Такахиро (2003). «Сложность и полнота поиска другого решения и его применение к головоломкам». IEICE Transactions по основам электроники, связи и информатики . Е86-А (5): 1052–1060.

[Lewis2015-9] Jump up to: Перейти обратно: ^а ^б Льюис, Р. Руководство по раскраске графов: алгоритмы и приложения . Международное издательство Springer, 2015.

[:16-10] Jump up to: Перейти обратно: ^а ^б де Рюитер, Йохан (15 марта 2010 г.). «О головоломках-судоку и связанных с ними темах (бакалаврская диссертация)» (PDF) . Лейденский институт передовых компьютерных наук (LIACS) .

[:15-11] QSCGZ (Гюнтер Стертенбринк) (21 сентября 2003 г.). «комбинаторный вопрос на 9х9 (загадки)» . Google Дискуссионная группа . Проверено 20 октября 2013 г.

[afj2-12] Jump up to: Перейти обратно: ^а ^б Джарвис, Фрейзер (2 февраля 2008 г.). «Проблемы перечисления судоку» . Домашняя страница Фрейзера Джарвиса . Университет Шеффилда . Проверено 20 октября 2013 г.

[afjarvis-13] Фельгенгауэр, Бертрам; Джарвис, Фрейзер (20 июня 2005 г.), Перечисление возможных сеток судоку (PDF) .

[sudgroup-14] Jump up to: Перейти обратно: ^а ^б Эд Рассел и Фрейзер Джарвис (7 сентября 2005 г.). «Существует 5472730538 существенно разных сеток судоку... и группа симметрии судоку» . Домашняя страница Фрейзера Джарвиса . Университет Шеффилда . Проверено 20 октября 2013 г.

[15] Эд Рассел, Фрейзер Джарвис (25 января 2006 г.). «Математика судоку II» (PDF) .

[16] Адлер, Авив; Адлер, Илан (2008). «Фундаментальные преобразования сеток судоку» (PDF) . Математический спектр . 41 (1): 2–7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Пазлы [ править ]

Минимальное количество данных [ править ]

Обычное судоку [ править ]

Симметричное судоку [ править ]

Общее количество минимальных головоломок [ править ]

Варианты [ править ]

Математический контекст ​ ​

Судоку из групповых таблиц [ править ]

Головоломка-судоку [ править ]

Решения [ править ]

Обычное судоку [ править ]

Все решения [ править ]

Принципиально разные решения [ править ]

Группа симметрии судоку [ править ]

Бернсайда Фиксированные и лемма точки

группы Полнота симметрии судоку

См. также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Математический контекст