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

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

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

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

Методы [ править ]

Возврат [ править ]

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

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

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

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

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

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

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

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

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

Стохастические методы поиска / оптимизации [ править ]

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

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

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

Программирование с ограничениями [ править ]

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

Точная обложка [ править ]

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

Разработка (поиск) судоку [ править ]

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

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

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

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

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

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

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

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