Эвристический решатель судоку

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


Предлагается несколько эвристик (алгоритмы 1-4) и мета-алгоритм их применения. Эксперименты показали, что решались все предложенные задачи вне зависимости от уровня сложности, хотя формального доказательства строгости, полноты и сходимости у меня нет.

Правила судоку

• Используется поле 9х9 клеток, разбитое дополнительно на 3х3 блока по 3х3 клетки.
• В каждой клетке может находиться цифра от 1 до 9
• Не разрешается, чтобы две и более одинаковых цифр стояли по вертикали, горизонтали и внутри каждого из блоков 3х3
• Цель: полностью заполнить частично заполненное поле

Терминология

Поле — все поле судоку 9х9
Полная ячейка — ячейка, для которой установлено значение. Это может быть цифра, данная при постановке задачи, либо найденная в ходе работы алгоритма.
Пустая ячейка — ячейка, для которой значение еще не найдено.
Блок — один из блоков 3х3, которому принадлежит ячейка.
Прогноз — список возможных значений для пустых ячеек.
Длина прогноза — количество возможных значений для пустых ячеек.

Алгоритм № 0. Перерасчёт прогноза

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

Алгоритм № 1. Базовый контроль правил

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

Алгоритм № 2. Ищем дубли

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

Алгоритм № 3. Избыточный прогноз

Для каждой пустой ячейки + для каждой прогнозной цифры в этой ячейке ищем хотя бы одну другую пустую ячейку (в строке, колонке или блоке), где эта цифра тоже присутствует. Если не найдено, заполняем этой цифрой ячейку.

Алгоритм № 4. Частичный перебор с негативным контролем

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

Алгоритм META

Выполнять последовательно алгоритмы 1-4. Если результат работы какого-либо алгоритма привел к заполнению ячеек, проверить полноту заполнения поля. Если заполнено не до конца, то вернуться к Алгоритму 0. Если заполнено — проверить корректность заполнения в соответствии с правилами судоку и завершить работу.

У предложенного эвристического алгоритма главный недостаток — нет гарантии сходимости. Кроме того, предложенных четырёх эвристик может быть и недостаточно или они будут не очень эффективны. С благодарностью приму любые мысли по улучшению алгоритма, оценке его полноты и новые идеи по эвристикам.