АЛГОРИТМЫ

Решите головоломку судоку с помощью поиска с возвратом в Python

Изучите основы поиска с возвратом, решая головоломку судоку.

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

Отслеживание с возвратом - это не конкретный алгоритм, а метод решения проблем. Популярная на практике задача поиска с возвратом - решение головоломки судоку. Это часто задаваемая проблема на собеседовании по кодированию.

Мне было так весело, когда я учился решать судоку с возвратом. Наконец, настоящая проблема!

Эта статья покажет вам, как решить головоломку судоку с помощью поиска с возвратом в Python. Это поможет вам подготовиться к собеседованию по кодированию, а также улучшить свои навыки Python. А также вы получите массу удовольствия от решения реальной проблемы.

Table of Contents:
· Backtracking
· Sudoku 
· Let’s Start Coding
  ∘ Initializing the board:
  ∘ Checking column, row, and 3x3 grid: 
  ∘ Solver function:
  ∘ Complete code:
· Conclusion

Возврат

Как я сказал ранее, возврат - это метод решения проблем. Если проблема может быть решена путем принятия дополнительных решений, мы можем решить ее с помощью отслеживания с возвратом.

Согласно Википедии -

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

«постепенно создает кандидатов для решений и отказывается от кандидата…» - это самая важная часть. Алгоритм поиска с возвратом постепенно выстраивает решение. Проверяю каждый шаг. Если шаг приводит к правильному решению, он продолжается. Если шаг не удовлетворяет ограничениям проблемы, он удаляет шаг и возвращается назад, чтобы найти другие решения.

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

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

Судоку

Примечание. Судоку - популярная головоломка. Возможно, вы уже знаете правила. В таком случае пропустите эту часть.

Судоку - это игра-головоломка, в которой вам предоставляется доска 9x9. Доска частично заполнена. Вы должны заполнить доску числами от 1 до 9, но у вас есть некоторые ограничения:

  • Вы можете использовать только цифры от 1 до 9
  • Каждый столбец может содержать каждое число от 1 до 9 только один раз.
  • Каждая строка может содержать каждое число от 1 до 9 только один раз.
  • Каждая подсетка 3x3 на доске может содержать каждое число от 1 до 0 один раз.

Итак, после решения головоломки судоку каждая строка, каждый столбец и каждая подсетка 3x3 будут содержать каждое число от 1 до 9 ровно один раз.

Это пример доски для судоку. И решение для платы выше приведено ниже.

Популярная техника решения головоломки судоку называется техникой штриховки. Перед тем, как ввести число в поле, вы отметите соответствующую строку, столбец и поле 3x3. Если номер появлялся раньше в любом из этих мест, вы не берете номер и не проверяете наличие других номеров.

Но обучить этому человеческому мыслительному процессу компьютер сложно. Компьютеру нужен систематический процесс для решения проблемы. И этот процесс идет вспять.

Каждый раз, когда вы кладете номер в ячейку, вы проверяете его действительность. Если указание определенного числа не нарушает правил, вы указываете его там. В противном случае вы удалите его, сделаете шаг назад и проверьте другие решения.

Приступим к кодированию

Инициализация платы:

Мы будем использовать двумерный список для инициализации доски судоку. Вы также можете думать об этом как о списке списков. Будем изображать пустые квадраты нулями.

Проверка столбца, строки и сетки 3x3:

Как объяснялось ранее, мы должны заполнить каждый столбец, строку и сетку 3x3 числами от 1 до 9 без повторения. Мы напишем функцию с именем isPossible() для проверки трех условий.

Сначала мы проверяем строку. Если в строке есть дубликат, функция возвращает False. Точно так же, если есть дубликат в столбце и сетке 3x3, функция также возвращает False. Но если ни одно из трех условий не выполняется, дубликата нет, и можно поставить число. Затем функция возвращает True.

Давайте проверим, дает ли функция правильный результат. Если мы хотим поместить 2 во второй столбец первой строки, это нарушит условия. Потому что в той же сетке 3x3 есть 2. Значит, функция должна возвращать false.

print(isPossible(board, 0, 1, 2))
>> False

После запуска кода мы получим False.

Но здесь допустимо поставить 1. Так что он вернет True.

print(isPossible(board, 0, 1, 1))
>> True

Функция решателя:

Теперь напишем нашу solve() функцию. Функция проверит, подходит ли число к определенной позиции. Если он подходит, функция поместит туда номер. Но если он не подходит, он вернется и попытается уместить другое число.

Полный код:

А вот и полный код.

Теперь давайте запустим код и посмотрим на результат.

Результат соответствует нашему решению. Мы успешно решили головоломку с помощью алгоритма поиска с возвратом!

Заключение

В этой статье я показал вам, как решить головоломку судоку с помощью поиска с возвратом. Это популярная задача на практике поиска с возвратом. Если вы изучаете информатику, вы найдете это в своей учебной программе. Если вы готовитесь к собеседованию по кодированию, это может произойти в одном из ваших собеседований.

Вы также можете делать из этого хорошие проекты. Вы можете создать настольное приложение, которое графически визуализирует процессы при решении головоломки. Или вы можете создать игру-судоку и опубликовать ее. Вы также можете применить к нему компьютерное зрение. Вы можете разработать приложение, которое распознает числа на изображении доски для судоку, принимает их в качестве входных данных, а затем решает их.

Вот и все! Надеюсь, вы сочтете это полезным. Спасибо за уделенное время.

Больше контента на plainenglish.io