Пятнашки.

Вроде любой.
Насколько помню можно кататься паровозиком по нижним 2м клеткам, и на поворотах изменить порядок

Нативной не видал, но есть браузерные, например вот:
http://ababasoft.com/kids/15.html

> Любое случайное начальное расположение костей можно сложить?
Нет.

Есть, кстати, нативная для линя реализация данной головоломки?

встроенная в ядро чтоли? ))) В кде есть виджет

Какой тогда прикол от игры, если не любая случайная комбинация складывается.

ЕМНИП, складывается ровно половина всех возможных раскладов.

помницо делал такую лабу в универе. начальное состояние генерировал так: дырка делала 256 шагов в произвольных направлениях

Кто то в детстве Перельмана не читал.

Там 50/50 комбинации - в одних сложить можно, а в других последние две местами поменять не получится, вроде (хотя можно считать, что сложил).
В универе курсе на 1м писал прогу, которая собирает пятнашки, надо бы алгоритм вспомнить, там не очень сложно.

Да, ровно половину комбинаций сложить нельзя - если в конце получается 14,13,15.

Вот хороший алгоритм: http://www.chessandpoker.com/fifteen-puzzle-solution.html