Стандартная судоку содержит 81 ячейку в сетке 9×9 и имеет 9 полей, каждое поле является пересечением первых, средних или последних 3 строк и первых, средних или последних 3 столбцов. Каждая ячейка может содержать число от одного до девяти, и каждое число может встречаться только один раз в каждой строке, столбце и поле. Судоку начинается с некоторых ячеек, содержащих числа ( подсказки ), и цель состоит в том, чтобы решить оставшиеся ячейки. Правильные судоку имеют одно решение. [ необходима цитата ] Игроки и исследователи используют широкий спектр компьютерных алгоритмов для решения судоку, изучения их свойств и создания новых головоломок, включая судоку с интересными симметриями и другими свойствами.
Существует несколько компьютерных алгоритмов, которые решают головоломки 9×9 ( n = 9) за доли секунды, но комбинаторный взрыв происходит по мере увеличения n , создавая ограничения на свойства судоку, которые можно построить, проанализировать и решить по мере увеличения n .
Некоторые любители разработали компьютерные программы, которые будут решать головоломки судоку, используя алгоритм обратного поиска , который является типом поиска методом грубой силы . [2] Обратный поиск - это поиск в глубину (в отличие от поиска в ширину ), потому что он полностью исследует одну ветвь до возможного решения, прежде чем перейти к другой ветви. Хотя было установлено, что существует приблизительно 5,96 x 1026 конечных сеток, алгоритм грубой силы может быть практичным методом решения головоломок судоку.
Алгоритм грубой силы посещает пустые ячейки в некотором порядке, последовательно заполняя цифры или возвращаясь назад, когда число оказывается недопустимым. [3] [4] [5] [6] Вкратце, программа решает головоломку, помещая цифру «1» в первую ячейку и проверяя, разрешено ли ей там находиться. Если нарушений нет (проверка ограничений строк, столбцов и ячеек), то алгоритм переходит к следующей ячейке и помещает в нее «1». При проверке нарушений, если обнаруживается, что «1» не разрешено, значение увеличивается до «2». Если обнаружена ячейка, в которой не разрешена ни одна из 9 цифр, то алгоритм оставляет эту ячейку пустой и возвращается к предыдущей ячейке. Затем значение в этой ячейке увеличивается на единицу. Это повторяется до тех пор, пока не будет обнаружено разрешенное значение в последней (81-й) ячейке.
Анимация показывает, как судоку решается этим методом. Подсказки головоломки (красные числа) остаются фиксированными, пока алгоритм проверяет каждую нерешенную ячейку возможным решением. Обратите внимание, что алгоритм может отбросить все ранее проверенные значения, если обнаружит, что существующий набор не соответствует ограничениям судоку.
Преимущества этого метода:
Недостатком этого метода является то, что время решения может быть медленным по сравнению с алгоритмами, смоделированными после дедуктивных методов. Один программист сообщил, что такой алгоритм может обычно требовать всего 15 000 циклов или целых 900 000 циклов для решения судоку, каждый цикл представляет собой изменение положения «указателя» при его перемещении по ячейкам судоку. [7] [8]
Другой подход, который также использует откат, исходит из того факта, что в решении стандартного судоку распределение для каждого отдельного символа (значения) должно быть одним из всего лишь 46656 шаблонов. В ручном решении судоку этот метод называется наложением шаблонов или использованием шаблонов и ограничивается заполнением только последних значений. Библиотека со всеми возможными шаблонами может быть загружена или создана при запуске программы. Затем каждому данному символу назначается отфильтрованный набор с теми шаблонами, которые соответствуют заданным подсказкам. На последнем этапе, фактической части отката, шаблоны из этих наборов пытаются объединить или наложить друг на друга неконфликтным образом, пока не будет найдена единственная допустимая комбинация. Реализация исключительно проста при использовании битовых векторов, поскольку для всех тестов требуются только побитовые логические операции вместо любых вложенных итераций по строкам и столбцам. Значительной оптимизации можно добиться, еще больше сократив наборы шаблонов во время фильтрации. Проверяя каждый сомнительный шаблон по всем сокращенным наборам, которые уже были приняты для других символов, общее количество шаблонов, оставшихся для возврата, значительно уменьшается.
И как и в случае со всеми методами решения судоку методом перебора, время выполнения можно значительно сократить, если сначала применить некоторые из самых простых методов решения, которые могут заполнить некоторые «легкие» значения.
Судоку можно построить так, чтобы оно работало против возврата. Если предположить, что решатель работает сверху вниз (как в анимации), то головоломка с небольшим количеством подсказок (17), без подсказок в верхней строке и с решением «987654321» для первой строки будет работать против алгоритма. Таким образом, программа потратит значительное время на «подсчет» вверх, прежде чем придет к сетке, которая удовлетворяет головоломке. В одном случае программист обнаружил, что программе грубой силы потребовалось шесть часов, чтобы прийти к решению для такого судоку (хотя и с использованием компьютера эпохи 2008 года). Такое судоку в наши дни можно решить менее чем за 1 секунду, используя исчерпывающую процедуру поиска и более быстрые процессоры. [ необходима цитата ]
Судоку можно решить с помощью стохастических (случайных) алгоритмов. [9] [10] Примером этого метода является:
Затем находится решение головоломки. Подходы к перетасовке чисел включают имитацию отжига , генетический алгоритм и поиск с запретами . Известно, что алгоритмы на основе стохастики быстры, хотя, возможно, не так быстры, как дедуктивные методы. Однако, в отличие от последних, алгоритмы оптимизации не обязательно требуют, чтобы задачи были логически разрешимыми, что дает им потенциал для решения более широкого круга задач. Известно, что алгоритмы, разработанные для раскраски графов, также хорошо работают с судоку. [11] Также возможно выразить судоку как задачу целочисленного линейного программирования . Такие подходы быстро приближаются к решению, а затем могут использовать ветвление к концу. Симплексный алгоритм способен решать правильные судоку, указывая, является ли судоку недействительным (нет решения). Если существует более одного решения (несобственный судоку), симплексный алгоритм, как правило, даст решение с дробными суммами, превышающими одну цифру в некоторых квадратах. Однако для правильного судоку методы линейного программирования presolve сами по себе выведут решение без необходимости симплексных итераций. Логические правила, используемые методами presolve для сокращения проблем LP, включают набор логических правил, используемых людьми для решения судоку.
Судоку также может быть смоделирована как проблема удовлетворения ограничений . В своей статье Судоку как проблема ограничений [12] Хельмут Симонис описывает множество алгоритмов рассуждений, основанных на ограничениях, которые могут быть применены для моделирования и решения проблем. Некоторые решатели ограничений включают метод моделирования и решения судоку, и программе может потребоваться менее 100 строк кода для решения простого судоку. [13] [14] Если код использует сильный алгоритм рассуждений, включение возврата необходимо только для самых сложных судоку. Алгоритм, объединяющий алгоритм на основе модели ограничений с возвратом, будет иметь преимущество в виде быстрого времени решения — порядка нескольких миллисекунд [15] — и возможности решать все судоку. [4]
Головоломки судоку можно описать как задачу точного покрытия или, точнее, задачу точного попадания в множество . Это позволяет изящно описать задачу и эффективно решить ее. Моделирование судоку как задачи точного покрытия и использование алгоритма, такого как алгоритм X Кнута и его техника Dancing Links , «является методом выбора для быстрого поиска [измеряемого в микросекундах] всех возможных решений головоломок судоку». [16] Альтернативным подходом является использование метода исключения Гаусса в сочетании с вычеркиванием столбцов и строк.
Пусть Q — матрица судоку 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, а X представляет собой общую строку, столбец или блок. N предоставляет символы для заполнения Q , а также набор индексов для 9 элементов любого X. Заданные элементы q в Q представляют собой одновалентное отношение от Q к N. Решение R является полным отношением и, следовательно, функцией . Правила судоку требуют, чтобы ограничение R на X было биекцией , поэтому любое частичное решение C , ограниченное X , является частичной перестановкой N.
Пусть T = { X : X — строка, столбец или блок Q }, так что T имеет 27 элементов. Расположение — это либо частичная перестановка, либо перестановка на N. Пусть Z — множество всех расположений на N. Частичное решение C можно переформулировать, включив правила в виде композиции отношений A (один к трем) и B, требующих совместимых расположений:
Решение головоломки, предложения по новому q для ввода Q , исходят из запрещенных расположений , дополнение C в Q x Z : полезные инструменты в исчислении отношений - это остатки :
доклад, представленный на Одиннадцатой международной конференции по принципам и практике программирования с ограничениями
