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

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

Воспользуйтесь всеми преимуществами информации о доске

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

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

Этот атрибут изображен в следующей таблице: после анализа допустимых значений для каждой пустой ячейки 1-го блока мы делаем наблюдение, что 4 появляется только в списке значений для ячейки [0][1]. Поэтому мы можем мгновенно установить значение ячейки [0][1] равным 4 и избавить наш алгоритм от дорогостоящих операций.

То же самое относится к столбцам и строкам, поэтому цель состоит в том, чтобы интегрировать в нашу функциюorderedValidValues() логику для уже добавленного значения на доску:

Мы получаем следующие результаты для нашего нового холода:

Время выполнения вышеуказанной программы: 3,7023189067840576 с.

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

Гибридное решение: сканирование доски и рекурсия

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

Вот как будет выглядеть начало такого исполнения вручную:

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

Давайте посмотрим, что произойдет, когда мы просканируем доску во второй раз:

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

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

Теперь давайте вручную запустим наш пример доски судоку, чтобы увидеть, что происходит на самом деле.

Мы видим, что нескольких итераций нашей функции сканирования достаточно для решения головоломки, нашей программе не нужно было проходить алгоритм возврата.
Тем не менее, мы ожидаем, что будут также головоломки судоку, в которых прогресс функции сканирования будет остановлен после нескольких итераций, после чего должен быть доступен возврат в качестве варианта Плана Б.

Наконец, давайте посмотрим, как наша программа справляется с эталонным тестом из 50 судоку, который мы использовали в этой серии статей:

Время выполнения вышеуказанной программы: 0,7639837265014648 с.

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

Если вы пропустили первую часть серии, вы можете прочитать ее здесь.

Спасибо за прочтение!