Как написать решатель судоку на Golang и сколько стратегий мы можем применить, чтобы добиться успеха?
Что такое судоку?
Судоку — это японское слово, которое означает числа должны оставаться одиночными. Я полагаю, что вы, должно быть, играли или слышали об этой игре, прежде чем прийти сюда. Подробнее можно посмотреть здесь.
В классическом судоку цель состоит в том, чтобы заполнить сетку 9 × 9 цифрами так, чтобы каждый столбец, каждая строка и каждая из девяти подсеток 3 × 3, составляющих сетку (также называемые «ящиками», «блоками», или «регионы») содержат все цифры от 1 до 9.
В дальнейшем предполагается, что головоломки судоку действительны, и они являются классическими. Другими словами, у головоломки должно быть хотя бы одно решение, а головоломки имеют размер 9х9.
Что такое Golang и почему я использую его для написания программы?
Официальное название Golang на самом деле Go, и некоторые называют его Golang, чтобы сформулировать язык программирования. Это статически типизированный, компилируемый язык, который считается C в 21 веке. Golang — многообещающий новый язык, и я всегда стремился его изучить. Я считаю, что лучший способ выучить и доказать, что вы знаете язык, — это создать на нем проект.
Стратегии решения судоку?
Как и многие другие, когда я был ребенком, я впервые столкнулся с судоку в газете и начал играть в нее без каких-либо руководств и стратегий. Ребенку было нетрудно найти способ быстрее решить судоку, сделав разумное предположение. Например, вы ищете ячейки с наименьшими возможностями, помещаете в них доступную цифру и продолжаете заполнять строку, столбец и подсетку. Если цифра подходит, вы переходите к следующей ячейке, в противном случае вы пробуете другой вариант. Однако будут случаи, когда вам нужно будет вернуться, чтобы удалить цифры, которые вы поставили ранее, чтобы освободить место для других ячеек. Эта стратегия настолько проста, что необразованный ребенок может обнаружить ее с первой же попытки решить судоку. Он имеет некоторое сходство с алгоритмом поиска с возвратом, о котором я расскажу чуть позже.
Как применить алгоритм возврата к судоку?
Всякий раз, когда нам нужно решить проблему, проще всего начать с поиска методом грубой силы. Откат — это своего рода усовершенствованный метод грубой силы. Чтобы лучше объяснить идею этого, я написал внешний интерфейс React, чтобы визуализировать процесс возврата судоку.
На гифке выше мы можем шаг за шагом увидеть, как работает возврат. В (0, 0) есть только два кандидата: 1 и 9. Сначала мы поместим в него 1, а единственный кандидат в (0, 1) — это 3. Однако мы увидим, что кандидатов не останется. для (0, 2, поэтому мы возвращаемся, чтобы попробовать другого кандидата в (0, 1). Однако других кандидатов для (0, 1) нет, поэтому нам нужно вернуться к (0, 0). Единственная альтернатива кандидат в (0, 0) равен 9, поэтому мы начинаем снова с (0, 0) с 9.
Хотя любой современный компьютер может выполнить расчет за секунду, никогда не стоит использовать грубую силу, когда есть другие варианты. Вышеупомянутое судоку решается за 80 шагов, но в худшем случае это может занять десятки тысяч шагов или даже больше. Из-за своей простоты и неэффективности откат судоку также называют наивным способом.
Разрушение проблемы
Обладая некоторыми базовыми знаниями в области программирования, вы можете легко заметить, что приведенный выше метод буквально является рекурсией. Давайте пересмотрим, когда использовать рекурсию в статье на GeeksforGeeks.
Задача, которую можно определить с помощью аналогичной подзадачи, рекурсия является одним из лучших решений для нее.
Судоку прекрасно описывается им. Но как судоку «задача, которую можно определить с помощью подобных подзадач?». Давайте думать так: каждый раз, когда мы помещаем число в ячейку, мы создаем новую головоломку судоку, которая немного отличается от предыдущей. Это можно упростить в виде дерева решений следующим образом:
Как реализовать вышеизложенное в Голанге?
Так как теперь у нас есть краткое представление о том, что делать дальше. Запачкаем руки! Во-первых, нам нужны вспомогательные функции для проверки текущей головоломки судоку. Есть три ограничения, которые должны быть соблюдены, чтобы он был действительным.
- Нет дубликатов в строке
- Нет дубликатов в столбце
- Нет дубликатов ни в одной из подсеток 3x3
Вот их реализация в Голанге
С помощью этих функций мы можем получить список кандидатов для каждой пустой ячейки. Когда для одной пустой ячейки нет доступных кандидатов, мы знаем, что некоторые предыдущие кандидаты должны быть неверными.
После того, как у нас есть способ проверки судоку, нам нужна функция, которая рекурсивно вызывает сама себя, пока мы не достигнем базового случая. Кстати, я сохранил каждый шаг, чтобы визуализировать процесс во фронтенде. Не обязательно решать проблему.
Что-нибудь, что мы можем попытаться улучшить эффективность?
Использование грубой силы для решения проблемы нежелательно, поэтому можно внести некоторые уточнения в попытке оптимизировать алгоритм поиска с возвратом, например, отсортировав пустые ячейки в зависимости от того, сколько у них кандидатов, от меньшего к большему.
На гифке выше мы сначала создаем список ячеек, отсортированных по кардинальности в порядке возрастания. Тем не менее, этот подход не гарантирует, что он будет быстрее. Для этой головоломки
53..7….6..195….98….6.8…6…34..8.3..17…2…6.6….28….419..5….8..79
Требуется 4209 попыток, чтобы решить его, если мы не сортируем ячейки, однако потребуется всего 90 попыток, если мы начнем с ячейки с наименьшим количеством кандидатов. Однако есть случаи, когда эффективнее не сортировать. Удача играет роль в поиске в глубину.
Последние мысли…
Есть еще несколько вещей, которые мы можем рассмотреть в этой статье, например, отправка большего количества горутин для прохождения судоку, бенчмаркинг для сравнения эффективности. Однако мне кажется, что лучше написать о них новые статьи, чем расширять эту. Обратите внимание, что я новичок в Golang, и я был бы очень признателен, если бы вы исправили мои ошибки или дали мне знать, как я могу улучшить содержание :) Я уверен, что ваши комментарии и поддержка сделает меня лучшим разработчиком Golang.
