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

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

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

Техники

Возврат

Некоторые любители разработали компьютерные программы, которые решают головоломки судоку, используя алгоритм поиска с возвратом , который представляет собой разновидность поиска методом грубой силы . ^[2] Обратный поиск — это поиск в глубину (в отличие от поиска в ширину ), поскольку он полностью исследует одну ветвь в поисках возможного решения, прежде чем перейти к другой ветви. Хотя установлено, что примерно 5,96 х 10 ²⁶ окончательные сетки существуют, алгоритм грубой силы может быть практическим методом решения головоломок судоку.

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

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

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

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

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

Другой подход, который также использует возврат, основан на том факте, что при решении стандартного судоку распределение каждого отдельного символа (значения) должно быть одним из 46656 шаблонов.В ручном решении судоку этот метод называется наложением шаблонов или использованием шаблонов и ограничивается заполнением только последних значений.Библиотека со всеми возможными шаблонами может быть загружена или создана при запуске программы. Затем каждому данному символу присваивается отфильтрованный набор с теми шаблонами, которые соответствуют заданным подсказкам.На последнем этапе, собственно части обратного отслеживания, шаблоны из этих наборов пытаются объединить или наложить неконфликтным образом, пока не будет найдена одна допустимая комбинация.Реализация исключительно проста при использовании битовых векторов, поскольку для всех тестов необходимы только побитовые логические операции вместо каких-либо вложенных итераций по строкам и столбцам.Значительной оптимизации можно добиться за счет еще большего сокращения наборов шаблонов во время фильтрации. Путем проверки каждого сомнительного паттерна со всеми сокращенными наборами, которые уже были приняты для других символов, общее количество паттернов, оставшихся для обратного отслеживания, значительно уменьшается.

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

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

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

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

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

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

Программирование ограничений

Судоку также можно смоделировать как задачу удовлетворения ограничений . В своей статье « Судоку как проблема с ограничениями » ^[12] Хельмут Симонис описывает множество алгоритмов рассуждения, основанных на ограничениях, которые можно применять для моделирования и решения проблем. Некоторые решатели ограничений включают в себя метод моделирования и решения судоку, а для решения простого судоку программе может потребоваться менее 100 строк кода. ^[13]^[14] Если в коде используется сильный алгоритм рассуждения, возврат назад необходим только для самых сложных судоку. Алгоритм, сочетающий алгоритм, основанный на модели ограничений, с обратным отслеживанием, будет иметь преимущество быстрого решения - порядка нескольких миллисекунд. ^[15] - и возможность решать все судоку. ^[16]

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

Головоломки судоку можно описать как задачу точного покрытия или, точнее, задачу точного набора попаданий . Это позволяет элегантно описать проблему и найти эффективное решение. Моделирование судоку как точной задачи покрытия и использование такого алгоритма, как алгоритм X Кнута и его техника «Танцующие звенья» , «является предпочтительным методом для быстрого поиска [измеряется в микросекундах] всех возможных решений головоломок судоку». ^[17]Альтернативный подход — использование исключения Гаусса в сочетании с вычеркиванием столбцов и строк.

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

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

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

Q\xrightarrow {A} T\xrightarrow {B} Z\quad {\text{with}}\quad A;B\subseteq C.

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

A\backslash C={\overline {A^{T};{\bar {C}}}}

отображает T в Z и

C/B={\overline {{\bar {C}};B^{T}}}

отображает Q в T.

См. также

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

Ссылки

^ «Звездный взрыв - полярный график» Полярная диаграмма, показывающая путь решения судоку (Звездный взрыв) с использованием процедуры исчерпывающего поиска и комментариев к судоку с 17 подсказками.
^ http://intelligence.worldofcomputing/brute-force-search Поиск грубой силы, 14 декабря 2009 г.
^ «Возврат – Набор 7 (Судоку)» . Гики для Гиков . Архивировано из оригинала 28 августа 2016 г. Проверено 24 декабря 2016 г.
^ Норвиг, Питер. «Решение всех головоломок судоку» . Питер Норвиг (персональный сайт) . Проверено 24 декабря 2016 г.
^ «Таблица ячеек, посещенных для решения» Диаграмма, показывающая путь решения сложного судоку.
^ Зеленский, Джули (16 июля 2008 г.). Лекция 11 | Абстракции программирования (Стэнфорд) . Стэнфордский факультет компьютерных наук.
^ «Звездный взрыв Лев - полярный график» Полярная диаграмма, показывающая путь решения судоку (Звездный взрыв Лев) с использованием процедуры исчерпывающего поиска.
^ «Диаграмма ячеек, посещенных для решения» Диаграмма, показывающая путь решения сложного судоку с использованием процедуры исчерпывающего поиска.
^ Льюис, Р. (2007) Метаэвристика может решить головоломки судоку. Журнал эвристики, том. 13 (4), стр. 387-401.
^ Перес, Меир и Марвала, Чилидзи (2008) Подходы к стохастической оптимизации для решения судоку arXiv:0805.0697.
^ Льюис, Р. Руководство по раскраске графов: алгоритмы и приложения . Международное издательство Springer, 2015.
^ Симонис, Хельмут (2005). «Судоку как проблема с ограничениями». CiteSeerX 10.1.1.88.2964 . документ, представленный на Одиннадцатой Международной конференции по принципам и практике программирования с ограничениями
^ Несколько авторов. «Решатель программирования ограничений Java» (Java) . ЯКоП . Кшиштоф Кучинский и Радослав Шиманек . Проверено 8 декабря 2016 г.
^ Роллор. «Судокусолвер» (С++) . Гитхаб . Роллор . Проверено 8 декабря 2016 г.
^ «Судоку — Розеттский код» . Rosettacode.org . Проверено 30 ноября 2021 г.
^ Норвиг, Питер. «Решение всех головоломок судоку» . Питер Норвиг (персональный сайт) . Проверено 24 декабря 2016 г.
^ Хэнсон, Роберт М. (16 августа 2022 г.). «Точная матрица обложек» .

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

http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html Объяснитель судоку Николя Джуллерата (популярно для оценки судоку в целом). Архивировано 12 ноября 2013 г. на Wayback Machine.
Алгоритм решения головоломок судоку с карандашом и бумагой

[difficult_17_clue-1] «Звездный взрыв - полярный график» Полярная диаграмма, показывающая путь решения судоку (Звездный взрыв) с использованием процедуры исчерпывающего поиска и комментариев к судоку с 17 подсказками.

[2] ttp://intelligence.worldofcomputing/brute-force-search Поиск грубой силы, 14 декабря 2009 г.

[3] «Возврат – Набор 7 (Судоку)» . Гики для Гиков . Архивировано из оригинала 28 августа 2016 г. Проверено 24 декабря 2016 г.

[4] Норвиг, Питер. «Решение всех головоломок судоку» . Питер Норвиг (персональный сайт) . Проверено 24 декабря 2016 г.

[5] «Таблица ячеек, посещенных для решения» Диаграмма, показывающая путь решения сложного судоку.

[Zelenski-6] Зеленский, Джули (16 июля 2008 г.). Лекция 11 | Абстракции программирования (Стэнфорд) . Стэнфордский факультет компьютерных наук.

[7] «Звездный взрыв Лев - полярный график» Полярная диаграмма, показывающая путь решения судоку (Звездный взрыв Лев) с использованием процедуры исчерпывающего поиска.

[8] «Диаграмма ячеек, посещенных для решения» Диаграмма, показывающая путь решения сложного судоку с использованием процедуры исчерпывающего поиска.

[Lewis,_R_(2007)_pp_387-401-9] Льюис, Р. (2007) Метаэвристика может решить головоломки судоку. Журнал эвристики, том. 13 (4), стр. 387-401.

[Perez,_Meir_and_Marwala,_Tshilidzi_(2008)-10] Перес, Меир и Марвала, Чилидзи (2008) Подходы к стохастической оптимизации для решения судоку arXiv:0805.0697.

[Lewis2015-11] Льюис, Р. Руководство по раскраске графов: алгоритмы и приложения . Международное издательство Springer, 2015.

[12] Симонис, Хельмут (2005). «Судоку как проблема с ограничениями». CiteSeerX 10.1.1.88.2964 . документ, представленный на Одиннадцатой Международной конференции по принципам и практике программирования с ограничениями

[13] Несколько авторов. «Решатель программирования ограничений Java» (Java) . ЯКоП . Кшиштоф Кучинский и Радослав Шиманек . Проверено 8 декабря 2016 г.

[14] Роллор. «Судокусолвер» (С++) . Гитхаб . Роллор . Проверено 8 декабря 2016 г.

[15] «Судоку — Розеттский код» . Rosettacode.org . Проверено 30 ноября 2021 г.

[16] Норвиг, Питер. «Решение всех головоломок судоку» . Питер Норвиг (персональный сайт) . Проверено 24 декабря 2016 г.

[17] Хэнсон, Роберт М. (16 августа 2022 г.). «Точная матрица обложек» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]