Эвристическая функция для применения A * sudoku

Question

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

, например, это входная сетка:

и теперь мы должны заполнить клетку (1,2).

Все узлы представляют собой разные сетки, которые представляют разные состояния. Коэффициент ветвления равен 4, поэтому у нас есть 4 возможности для следующей ячейки: 1, 2, 3 или 4, то есть 4 ребенка для каждого узла.

Как определить эвристическую функцию на узлах для применения A * на сетке?

Все, что я могу думать:

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

else, h(n)= [number of empty remain cells]. 

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

Answer 1

Одной из эвристических функций является выбор ячейки с максимальным количеством ограничений на ней.

E.g. в вашем примере вы можете выбрать (2,3) =>, так как у него есть только одна возможность поместиться (максимальное количество ограничений). После того, как вы сделали «ставку» (поместили номер), вы можете продолжить ту же стратегию => место S[2,3] = 2 => выбрать S[2,2] и так далее.

Ограничения, я имею в виду, сколько вариантов у вас есть на ячейку, учитывая ограничения в правилах судоку.

ч [клетки] = 1/(варианты # в коробку + #options на рядный + #options в колонки)

Это очень простая стратегия, хотя (один вариант упреждающего) , но более сложные стратегии состоят в том, чтобы объединить эту стратегию с логикой более высокого порядка => в основном:

h2 [cell] = h [cell-left] + h [cell-right] + ...;

Answer 2

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

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

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

Однако это не похоже на вашу проблему с дополнительным ограничением на то, как выбрать следующую ячейку для обработки, заданную вашим назначением. Если вам нужно придерживаться A *, эвристика, которую вы определили, верна, поскольку это допустимо. Как вы заметили, эвристическое значение будет одинаковым для всех узлов. Это приведет в основном к поиску в ширину и будет очень неэффективным.

Для получения дополнительной информации об информированном поиске и эвристике см. Главу 3 из Artificial Intelligence: a modern approach, Рассел и Норвиг.