Алгоритмы решения судоку - Sudoku solving algorithms

Типичная головоломка судоку

Стандартный судоку содержит 81 ячейку в сетке 9 × 9 и 9 прямоугольников, каждое из которых является пересечением первых, средних или последних 3 строк, а также первых, средних или последних 3 столбцов. Каждая ячейка может содержать число от одного до девяти, и каждое число может встречаться только один раз в каждой строке, столбце и поле. Судоку начинается с некоторых ячеек, содержащих числа ( подсказки ), и цель состоит в том, чтобы разгадать оставшиеся ячейки. У правильных судоку есть одно решение. Игроки и исследователи используют широкий спектр компьютерных алгоритмов для решения судоку, изучения их свойств и составления новых головоломок, в том числе судоку с интересной симметрией и другими свойствами.

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

Методы

Возврат

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

Судоку, разработанная для работы против алгоритма грубой силы.

Некоторые любители разработали компьютерные программы, которые решают головоломки судоку с использованием алгоритма поиска с возвратом , который является разновидностью поиска методом грубой силы . Поиск с возвратом - это поиск в глубину (в отличие от поиска в ширину ), потому что он полностью исследует одну ветвь до возможного решения, прежде чем перейти к другой ветви. Хотя было установлено, что существует приблизительно 5,96 x 11 ²⁶ конечных сеток, алгоритм грубой силы может быть практическим методом решения головоломок судоку.

Алгоритм грубой силы посещает пустые ячейки в некотором порядке, последовательно заполняя цифры или возвращаясь, когда обнаруживается, что число недействительно. Вкратце, программа решила бы головоломку, поместив цифру «1» в первую ячейку и проверив, разрешено ли ей там находиться. Если нет никаких нарушений (проверка ограничений строки, столбца и поля), то алгоритм переходит к следующей ячейке и помещает «1» в эту ячейку. При проверке нарушений, если обнаруживается, что «1» не допускается, значение увеличивается до «2». Если обнаруживается ячейка, в которой не допускается ни одна из 9 цифр, алгоритм оставляет эту ячейку пустой и возвращается к предыдущей ячейке. Затем значение в этой ячейке увеличивается на единицу. Это повторяется до тех пор, пока не будет обнаружено допустимое значение в последней (81-й) ячейке.

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

Преимущества этого метода:

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

Недостатком этого метода является то, что время решения может быть медленным по сравнению с алгоритмами, смоделированными на основе дедуктивных методов. Один программист сообщил, что такой алгоритм обычно требует от 15 000 циклов или до 900 000 циклов для решения судоку, причем каждый цикл представляет собой изменение положения «указателя» при его перемещении по ячейкам судоку.

Судоку может быть сконструирован таким образом, чтобы не допускать возврата. Предполагая, что решатель работает сверху вниз (как в анимации), головоломка с несколькими подсказками (17), без подсказок в верхней строке и имеет решение «987654321» для первой строки, будет работать в противовес алгоритму. . Таким образом, программа потратит значительное время на «подсчет» вверх, прежде чем попадет в сетку, удовлетворяющую головоломке. В одном случае программист обнаружил, что программе грубой силы требуется шесть часов, чтобы найти решение для такого судоку (хотя и с использованием компьютера 2008 года). Такие судоку в настоящее время можно решить менее чем за 1 секунду, используя процедуру исчерпывающего поиска и более быстрые процессоры.

Стохастические методы поиска / оптимизации

Судоку можно решить с помощью стохастических (случайных) алгоритмов. Пример этого метода:

1. Произвольно присваивайте номера пустым ячейкам сетки.
2. Подсчитайте количество ошибок.
3. «Перемешайте» вставленные числа, пока количество ошибок не уменьшится до нуля.

Затем найдено решение загадки. Подходы к перетасовке чисел включают моделирование отжига , генетический алгоритм и запретный поиск . Алгоритмы, основанные на стохастике, известны своей быстродействием, хотя, возможно, и не такими быстрыми, как дедуктивные методы. Однако, в отличие от последнего, алгоритмы оптимизации не обязательно требуют, чтобы проблемы были логически решаемыми, что дает им возможность решать более широкий круг проблем. Известно, что алгоритмы, предназначенные для раскраски графов, также хорошо работают с судоку. Судоку также можно выразить как задачу целочисленного линейного программирования . Такие подходы быстро приближаются к решению, а затем могут использовать ветвление ближе к концу. Симплексный алгоритм способен решить правильную судоку, указывая , если судоку не является допустимым (без раствора). Если существует более одного решения (неподходящие судоку), симплексный алгоритм обычно дает решение с дробным количеством более одной цифры в некоторых квадратах. Однако для правильного судоку только методы предварительного решения линейного программирования позволят вывести решение без каких-либо симплексных итераций. Логические правила, используемые методами предварительного решения для сокращения проблем LP, включают набор логических правил, используемых людьми для решения судоку.

Ограниченное программирование

Судоку также можно смоделировать как проблему удовлетворения ограничений . В своей статье « Судоку как проблема с ограничениями» Хельмут Симонис описывает множество алгоритмов рассуждений, основанных на ограничениях, которые можно применять для моделирования и решения проблем. Некоторые решатели ограничений включают метод моделирования и решения судоку, а программе может потребоваться менее 100 строк кода для решения простого судоку. Если в коде используется строгий алгоритм рассуждений, включение отслеживания с возвратом необходимо только для самых сложных судоку. Алгоритм, объединяющий алгоритм на основе модели ограничений с обратным отслеживанием, будет иметь преимущество в виде быстрого времени решения и способности решать все судоку.

Точное покрытие

Головоломки судоку можно охарактеризовать как точную задачу прикрытия . Это позволяет элегантно описать проблему и найти эффективное решение. Моделирование судоку как проблемы с точным прикрытием и использование такого алгоритма, как алгоритм X Кнута, обычно решает судоку за несколько миллисекунд. Альтернативный подход - использование исключения Гаусса в сочетании с выделением столбцов и строк.

Отношения и остатки

Пусть Q будет матрицей судоку 9x9, N = {1, 2, 3, 4, 5, 6, 7, 8, 9}, а X представляет общую строку, столбец или блок. N поставляет символы для заполнения Q , а также множество индексов за 9 элементов любого X . Приведены элементы д в Q представляет собой частичную функцию от Q к N . Решение R является полным отношением и, следовательно, функцией . Правила судоку требуют, чтобы ограничение на R на X является взаимно однозначное соответствие , так что любое частичное решение С , ограничено к X , является частичной перестановки из N .

Пусть T = { X  : X - строка, столбец или блок Q }, поэтому T имеет 27 элементов. Расположение является либо перестановка или частичная перестановки на N . Пусть Z множество всех договоренностей по N . Частичное решение C может быть переформулировано, чтобы включить правила как композицию отношений A (один к трем) и B, требующих совместимости:

${\ displaystyle Q \ xrightarrow {A} T \ xrightarrow {B} Z \ quad {\ text {with}} \ quad A; B \ substeq C.}$

Решение головоломки, предложения по новому д ввести Q , исходят из запрещенных соглашений , то дополнение из С в Q х Z : полезные инструменты в исчислении отношения невязок : ${\ displaystyle {\ bar {C}},}$

${\ Displaystyle A \ обратная косая черта C = {\ overline {A ^ {T}; {\ bar {C}}}}}$отображает T в Z , и

${\ Displaystyle C / B = {\ overline {{\ bar {C}}; B ^ {T}}}}$карты Q на T .

Разработка (поиск) судоку

Судоку с 17 подсказками и диагональной симметрией.

Автоморфная Судоку с 18 ключей и двухсторонним диагональной симметрии.

17 подсказок судоку с похожей схемой. (Оранжевые круги: удаленные подсказки, зеленые круги: добавленные подсказки, синее подчеркивание: другая цифра).

18 разгадок судоку. (Горизонтальная симметрия).

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

Один из распространенных методов поиска судоку с определенной характеристикой называется поиском соседей . При использовании этой стратегии один или несколько известных судоку, которые удовлетворяют или почти удовлетворяют искомой характеристике, используются в качестве отправной точки, и эти судоку затем изменяются для поиска других судоку с искомым свойством. Изменение может заключаться в перемещении одной или нескольких позиций подсказок или удалении небольшого количества подсказок и замене их другим количеством подсказок. Например, из известного судоку поиск нового с одной подсказкой меньше может быть выполнен путем удаления двух подсказок и добавления одной подсказки в новом месте. (Это можно назвать поиском {-2, + 1}.) Затем каждый новый шаблон будет подвергаться исчерпывающему поиску всех комбинаций значений подсказок с надеждой, что одно или несколько дадут верный судоку (т. Е. Могут быть решены и имеют единственное решение). Также можно использовать методы для предотвращения повторного тестирования эквивалентных судоку.

В качестве конкретного примера, поиск судоку с 17 подсказками можно начать с известного судоку с 18 подсказками, а затем изменить его, удалив три подсказки и заменив их только двумя подсказками в разных положениях (см. Последние два изображения). Это может открыть новые судоку, но не будет немедленной гарантии, что они существенно отличаются от уже известных судоку. При поиске действительно новых (неоткрытых) судоку потребуется дополнительное подтверждение, чтобы убедиться, что каждая находка не является преобразованием уже известного судоку.

Смотрите также

• Судоку
• Математика судоку
  • § Судоку с несколькими подсказками (минимальное количество заданий)
  • § Автоморфные судоку
• Комбинаторный взрыв (со сводкой подсчета сетки судоку по сравнению с латинскими квадратами)
• Глоссарий судоку

использованная литература

внешние ссылки

• http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html Объяснение судоку от Николаса Джуллера (популярно для оценки судоку в целом)
• http://gsf.cococlyde.org/download/sudoku Sudoku от Гленна Фаулера (среди прочего, популярный за то, что оценивает самые сложные судоку)
• Карандашно-бумажный алгоритм решения головоломок судоку