Нерешаемые комбинации в игре "Пятнашки"

[Punk1911]

Здравствуйте!

Пишу игру Пятнашки для тренировки.
Комбинацию я делаю путем случайного перемешивания исходного массива чисел 0, 1, 2,.. 15.
Прочитал, что в игре половина комбинаций нерешаема.
Следовательно вопрос: как определить, что сгенерированная комбинация решаема и ее можно использовать?

Как я понял из Википедии, можно сделать так:
1) идти по полю игры слева направо и сверху вниз;
2) если число костяшки i+1 меньше i-ой костяшки, то Ki = 1. Иначе Ki = 0;
3) сложить все Ki и добавить число e, равное номеру ряда, где находится пустая клетка (нумерация рядов с 1);
4) если полученное число четное, то комбинация решаема.

Я прав?

[Arigato]

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

[Punk1911]

Как в таком случае определять, что ход корректный и не приведет к нерешаемой комбинации?

[min@y™]

да просто делай, как в педивикии написано, и всё.

[Аватар]

Делал бы как Аригато предложил - обратные рандомные перемещения от собранной комбинации. Ходов 30 наверно хватило бы с избытком

[Arigato]

Сообщение от Punk1911

Как в таком случае определять, что ход корректный и не приведет к нерешаемой комбинации?

Он не может привести к нерешаемой комбинации, потому как вы как бы играете, но наоборот, то есть всегда есть обратный путь. Ну а как проверить корректность хода - программно.

[Punk1911]

Нашел решение. Код не мой.
Когда не знал, что у пятнашек есть нерешаемые комбинации, то подумал, что автор данного кода зря наворотил столько строк. Я ошибался!

Тут как раз происходит расстановка костяшек от базовой позиции (1,2,3,..15, "пустышка") путем произвольных ходов.
Всем спасибо!

Код на C#:
Shuffle.txt