Форум DL

Мой профиль

SP120
Solitaire Rus
Eng
Code:SOLIT

Есть поле 8X8. На поле есть 4 фишки. Фишку можно передвинуть (вверх, вниз, вправо, влево) на 1 клетку, если там свободно. Или перепрыгнуть через рядом стоящую фишку (верх, вниз, вправо, влево),
если там свободно. Задано стартовое расположение 4 фишек, и конечное расположение 4 фишек. Требуется определить можно ли попасть из стартового в конечное за 8 или меньше ходов. (Yes/No)

Рекурсия с меморизацией. Пронумеруем поле 1..64, Состояние поля можно описать 4 числами
(1...64) ==> размер меморизации 64⁴=16.7млн , по памяти это немного. Заметим что фишки одинаковые и нам не важно какую фишку, на какую позицию поставить ==> мы будем хранить числа в меморизации в порядке возрастания. Тогда кол-во заполненных ячеек меморизации будет (16.7млн/4!)=700 000. И даже меньше тк мы не учитываем, что 2 фишки не могут одновременно находится на одинаковых позициях и что НЕ ВСЕ состояния достижимы за 8 ходов.
Поэтому только небольшая часть меморизации будет заполнена. И решение должно успеть даже с учётом того что внутри процедуры надо отсортировать 4 числа и сгенерировать ходы.

______________________
=====

Мой профиль

Я использовал немного видоизмененное решение. Рекурсия с меморизацией, но только с двух сторон(от начального и конечного состояния). В этом случае глубина ограничена числом 4.
Этот метод, кажется, называется "Meet in the middle"