Как найти алгоритм решения головомки Шишнашки?

Question

[Сергей]

Сделал андройдный клон игры Шишнашки - habrahabr.ru/post/269391, но никак не могу придумать как решать говоломку. Иногда получается собрать, но не все расклады. Задачу с перестановкой двух чисел тоже не получается решить (задача 1 в статье), а как раз такая ситуация и получается в конце чаще всего.
Единственное, что приходит в голову это перебрать все варианты перестановок, каким-то образом запомнить последовательность к каждому варианту и сравнивать текущей расклад с таблицей готовых решений. Но мне кажется объем всего этого будет какой-то нереальный. Наверняка есть более оптимальный путь решения. Может перебрать варианты решения не всех плиток, а только половины?...
Хочется доделать игру, но без функции подсказок игра получается неполноценной.

Answer 1

[Пума Тайланд]

Так там всего два варианта раскладка и они в друг друга никак не переходят

Comments

[Сергей]

Поясните, пожалуйста, не очень понимаю, как там может быть два расклада, да еще не переходящих друг в друга? Автор пишет, что все 16! раскладов решаются.

[Пума Тайланд]

Сергей: поменяйте в начальном раскладе местами 15 и 16 и вот вам будет второй который нельзя перевести в первый.

[Пума Тайланд]

Сергей: хотя там же не пятнашки