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

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

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

Оптимизируйте, исключив ненужные итерации

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

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

Теперь, когда наша идея ясна, мы переходим к реализации с нашим кодом. Для этой задачи мы создадим 2 функции:

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

2. Функция allowValues(), которая имеет аналогичную логику с функцией isValid(), которую мы видели в части 1, однако в этом случае она извлекает для каждой ячейки список допустимых чисел.

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

Нам также нужно заменить функциюsolve() на новую функциюsolveWithCache(), которая ожидает словарного кеша в своем списке параметров и на этот раз выполняет итерацию только по списку допустимых значений для каждой ячейки, а не по всем числам 1–9.

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

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

Оптимизируйте, добавляя информацию в нашу программу

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

На доске судоку много информации, которая еще не интегрирована в логику нашего алгоритма:

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

Чтобы сделать это более понятным на наглядном примере:

Для первой строки данной доски мы извлекли допустимые значения для каждой ячейки и добавили их в скобки. Собирая значения из всех ячеек строки 1, мы замечаем, что число 6 появляется как значение-кандидат только в 2 ячейках, а числа 1, 5, 7, 9 появляются в 4 разных ячейках.

Это преобразуется в число 6, имеющее больше шансов преобладать в определенной ячейке, когда оно конкурирует с числами с более высокой частотой (на основе информации, извлеченной только из строки).

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

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

После последней модификации мы пробуем нашу программу и записываем время выполнения нашей программы:

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

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

Следующая идея состоит в том, чтобы интегрировать в наш алгоритм информацию, поступающую из столбца и блока ячейки. Как показано на следующем изображении, для ячейки [0][1] у нас есть допустимые значения [1,4,5,7,9].
На основе анализа частоты появления для всех ячеек, связанных с тот, который нас интересует, мы можем упорядочить список допустимых значений следующим образом: [4,7,1,5,9], который, как мы надеемся, ограничит неправильные предположения и, следовательно, итерации нашего алгоритма поиска с возвратом.

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

Как только в нашем новом коде не будет ошибок, мы попытаемся измерить производительность:

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

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

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