Эвристика для пятнашек.

[puffyreg]

Прочитал, алгоритм для решения пятнашек 3х3. Использовался алгоритм A* эвристика там была = Количество ходов + Неправильно расположенные элементы. Так вот меняется ли она при переходе с 3х3 на 4х4 пятнашки. Ну или вообще какую эвристику выбрать для 4х4 пятнашек.

[Paragraph]

Корректная эвристика не зависит от размера доски. Но вам надо убедиться, что она корректна.

Для 4x4 понадобится достаточно памяти для хранения priority queue. Если исходное состояние случайно и терминальное состояние недостижимо, то а-стар попытается посетить все возможные ветки поиска. А для такой доски это много.

[FomaNeverov]

https://resetius.ru/programs/15.html

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