Алгоритм решения Peg Solitaire / Senku

Question

Мне нужно запрограммировать решатель для игры Пасьянс колышек / Сенку
Уже есть вопрос здесь , но предложенный ответ - это алгоритм грубой силы с возвратом, которыйэто не решение, которое я ищу.
Мне нужно найти эвристику, чтобы применить алгоритм A *.Оставшиеся колышки не являются хорошей эвристикой, поскольку каждый ход отбрасывает один колышек, поэтому стоимость всегда одинакова.
Есть идеи?

Answer 1

Я читал газету об этой проблеме ссылка , и они предлагают 3 эвристики:

1 - Количество узлов, доступных для следующего шага, учитывая, что чем больше доступных шагов следующего, тем лучше узел.

2 - Количество изолированных колышков - чем меньше изолированных колышков, тем лучше узел.

3 - Чем меньше колышков на доске, тем лучше узел.

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

Answer 2

Вы можете сделать, как предложено Россумом. Другой вариант - использовать сумму расстояний (или некоторую другую функцию расстояний) от центра. Или вы могли бы объединить два.