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

Я выполняю задание, в котором я должен использовать звездочку для решения 15-головоломки (на языке C).

Эвристическая функция Манхэттенское расстояние (также известное как расстояние такси).

Нам дается пример ввода / вывода, где плата решается за 22 ходов и после расширения 395 узлов (состояний платы) (т.е. мы должны были посмотреть на дочерние элементы 395 узлов)

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

Проблема в том, что мое решение расширяет более 400 узлов , чтобы найти решение ( оптимально 22 хода, но другое ).

Я заметил, что число меняется в зависимости от порядка, в котором я генерирую дочерние узлы (перемещайте тайл пространства вверх, влево, вниз, вправо или в других направлениях).

Существует 24 способа перемещения тайла пространства вверх, вниз, влево и вправо для создания дочерних элементов, и я пробовал все из них, но ни один из них не расширил 395 узлов.

Почему это происходит?

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

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

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

Спасибо