Пишу игру "Пятнашки". На начальном этапе расставлял фишки рандомом. Но, оказывается, что половина таких расстановок не имеет решения.
Может кто-нибудь уже писал подобную игру? Какой критерий того, что пятнашки могут быть собраны?

Временно решил проблему следующим образом: заполняю массив собранного поля, и в случайном порядке перемещаю фишки

Ты эта - чет/нечет считаешь? Там половина не рабочих

Я знаю, что там половина не рабочих расстановок.
Все варианты подсчета, которые я находил в инете, при проверке не работают. То ли я не так понимаю.
Давай алгоритм, буду думать.

Лучше не заморачиваться, а делать обратную перестановку. Т.е. сдвигать фишки так как это делает игрок, только от начального положения и рандомно. Для компьютера 1000 сдвигов не проблема, займёт доли секунды.

Хотя, можно проверить любую начальную позицию на правильность. Просто нужно проверить количество парных перестановок, необходимых для того, чтобы фишки стали по порядку. Если число перестановок нечётное, то расклад не верный. Парная перестановка - это снятие с поля двух фишек и смена их местами.
Т.е. первым ходом снимаем с поля единичку и ставим на её место фишку которая стоит на первом месте. Единичку ставим на освободившееся место. Потом повторяем тоже самое для двойки и т.д.
До конца не уверен, давно это было.

> заполняю массив собранного поля, и в случайном порядке перемещаю
> фишки


Вообще-то именно так и делают большинство реализаций этой игры. Проще, без заморочек.