Создание и решение головоломок судоку

Реализация алгоритма поиска с возвратом в Javascript и Ruby

Обновлять:

Спасибо edh_developer из сообщества разработчиков за помощь в выявлении проблемы с созданием нескольких возможных досок. Код сути обновлен.

Судоку

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

Игра Судоку начинается с сетки 9x9, частично заполненной значениями от 1 до 9. Цель игрока - заполнить все оставшиеся поля значениями от 1 до 9. Однако каждое число, которое вставляет игрок, должно соответствовать трем строгим правилам:

Каждое значение 1–9 может присутствовать только один раз подряд. Таким образом, в приведенном выше примере доски цифры 5, 3 и 7 не могут быть записаны ни в одну из пустых ячеек в первой строке.
Каждое значение 1–9 может присутствовать в столбце только один раз. Таким образом, в приведенном выше примере доски 5, 6, 8, 4 и 7 не могут быть записаны ни в одну из пустых ячеек в первом столбце.
Каждое значение 1–9 может присутствовать только один раз в пределах области сетки. Область сетки - это меньшая сетка 3x3 на большой доске для судоку. Эти области можно увидеть на приведенной выше доске по их полужирным границам. Например, верхняя левая область содержит значения 5, 3, 6, 8 и 9, поэтому эти значения нельзя снова поместить ни в одну из пустых ячеек, оставшихся в этой области.

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

Возврат

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

Реализация

Я реализовал решение для поиска с возвратом как в Javascript, так и в Ruby. Я описал процесс и компоненты в Javascript ниже, но полный код как для Ruby, так и для Javascript можно найти внизу этой статьи.

Критерии размещения

Чтобы приступить к реализации этого алгоритма, мы должны сначала определить, каковы наши критерии успеха: rowSafe проверяет уникальность значений в строке, colSafe проверяет их в столбце и boxSafe в сетке 3x3. Затем нам нужно оценить, указаны ли координаты emptyCell (который является объектом JS или хешем Ruby, содержащим обе координаты).

Чтобы проверить строку, мы можем выбрать строку puzzleArray, которая указана в координатах emptyCell, и посмотреть, содержит ли она значение num, которое мы пытаемся вставить, путем поиска индекса этого значения.

Чтобы проверить столбец, мы можем проверить индекс столбца emptyCell для каждой строки и посмотреть, содержит ли какой-либо из них это значение. В Javascript .some() вернет истину, если хотя бы одно из значений массива соответствует условию.

Условия области более сложны, потому что мы должны сначала определить, к какому региону принадлежит ячейка. Каждая область начинается в строках 0, 3 и 6 и столбцах 0, 3 и 6. Используя комбинацию вычитания и модуля с координатами пустой ячейки, мы можем определить крайнюю левую верхнюю ячейку области, в которой находится ячейка. принадлежит. Затем мы просматриваем регион и ищем совпадение.

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

Создание игрового поля

Чтобы создать игровую доску, мы сначала создаем полностью заполненную (и правильно решенную) доску из совершенно пустой доски. Диапазон значений от 1 до 9 перемешивается в начале каждой итерации, обеспечивая низкую вероятность того, что каждая новая игра будет похожей. Поскольку за каждым успешным размещением числа будет следовать еще одна попытка разместить число, эта fillPuzzle функция будет рекурсивно вызывать себя. Поскольку это может быть немного сложно, давайте обрисуем шаги, прежде чем мы увидим код:

Получите пустую матрицу 9x9, заполненную нулями.
Просканируйте матрицу на предмет следующей ячейки с текущим нулевым значением.

Произведите случайный выбор массива [0,1,2,3,4,5,6,7,8,9] и попытайтесь поместить первое значение этого перемешанного массива в пустую ячейку, найденную выше.
Вставьте условие, чтобы прервать скрипт, если плата не сгенерировала в течение определенного количества итераций. Большинство плат будут генерировать менее 500 мс, но случайная генерация иногда может приводить к длительному времени ожидания. Я расскажу об этом подробнее в разделе инициализации.
Если значение из перемешанного массива проходит все проверки безопасности, вставьте его и вернитесь к шагу 2.
Если значение из перемешанного массива не проходит проверку безопасности, верните ячейку в ноль, вернитесь к ранее размещенному числу и попробуйте изменить его на следующее возможное значение из перемешанного массива и повторите.

Создание игровой доски

Ура! У нас есть полностью заполненная доска для судоку, соответствующая всем критериям игры! Однако, если вы действительно хотите поиграть в игру, вам нужно «проделать несколько дыр» в ней, чтобы сделать ее доступной для игры. Мы можем удалить эти ячейки произвольно; однако мы должны убедиться, что удаление значения создает доску, которую все еще можно решить, И что это приводит к уникальному решению - поскольку есть только один способ поставить числа и выиграть.

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

Полученные результаты

Осталось только запустить скрипт и сразу же получить startingBoard, solvedBoard и список removedVals! Обратите внимание, что в функции инициализации newStartingBoard мы будем try создать игру. Большинство игр будет создано за fillPuzzle выдаст ошибку и прервет скрипт через заданное время. Мы будем catch эту ошибку и использовать ее для повторного запуска функции инициализации. Быстрее отказаться от головоломок с аномально долгим временем генерации и начать заново, чем ждать их решения.