Пятнашки бесплатно | Двигайте фишки и попробуйте 14-15 Сэма Лойда

Как это работает

Щёлкните фишку рядом с пустой клеткой, чтобы сдвинуть её туда, или фишку дальше в том же ряду или столбце, чтобы сдвинуть всю линию.
Расставьте фишки обратно по порядку, начиная с 1 в левом верхнем углу, так чтобы пустая клетка оказалась в правом нижнем углу.
Застряли? Нажмите «Решить» и посмотрите, как головоломка решается до конца, или «Шаг», чтобы идти по одному ходу. Затем сохраните PNG.

Как играть

Двигаться может только фишка рядом с пустой клеткой, и она переходит в пустую клетку. Щёлкните фишку дальше в ряду или столбце пустой клетки, и все фишки между ними сдвинутся вместе с ней; клавиши со стрелками сдвигают фишку с соответствующей стороны от пустой клетки. «Ходы» считают каждую фишку, которая сдвигается, а «Отменить» возвращает назад один сдвиг. «Размер» переключает между игрой в 8 на поле 3×3, игрой в 15 и игрой в 24 на поле 5×5.

Половину всех позиций решить нельзя

Выньте две фишки, поменяйте их местами — и головоломку уже никогда не решить. Каждый сдвиг меняет местами пустую клетку и фишку, а чтобы вернуться в свой угол, пустой клетке нужно чётное число сдвигов, поэтому фишки можно переставить только чётным числом обменов. А один обмен — это нечётное число. Из 20 922 789 888 000 способов заполнить 16 клеток достижима ровно половина. Позиция 14-15 Лойда находится в другой половине.

Как работает «Решить»

«Решить» ищет путь назад с помощью A*. Поиск ориентируется на то, насколько каждая фишка далека от своей клетки, и добавляет по два хода за каждую пару фишек, которые стоят в своём ряду или столбце, но в неправильном порядке. На поле 3×3 он находит кратчайшее решение, которое никогда не длиннее 31 хода. На больших полях он довольствуется коротким решением, найденным сразу, а не кратчайшим, поиск которого может занять много времени: самым трудным позициям 4×4 нужно 80 ходов.

Часто задаваемые вопросы

Можно ли решить любую позицию в пятнашках?

Только половину всех расстановок. На поле 4×4 позицию можно решить, когда число пар фишек, стоящих в неправильном порядке, плюс номер ряда пустой клетки, считая снизу, — нечётное. «Перемешать» создаёт только решаемые позиции.

Что такое головоломка 14-15 Сэма Лойда?

Это решённая расстановка, в которой 14 и 15 поменяны местами. Лойд рассказывал о премии в 1000 долларов за её решение, но никакая последовательность сдвигов её не решит: один обмен — это нечётная перестановка, а сдвиги дают только чётные.

Сколько ходов занимает решение?

Самым трудным позициям игры в 15 нужно 80 ходов, а случайной — в лучшем случае около 50. Игре в 8 никогда не нужно больше 31. «Решить» находит кратчайшее решение на поле 3×3, а на больших полях — короткое, не всегда кратчайшее.

Почему один щелчок иногда сдвигает несколько фишек?

Щелчок по фишке в ряду или столбце пустой клетки сдвигает её и все фишки между ней и пустой клеткой — так же, как вы толкали бы их в настоящей головоломке. «Ходы» считают каждую сдвинутую фишку.

Что-нибудь загружается?

Нет. Головоломка рисуется на холсте в браузере. Кнопка «Сохранить» скачивает PNG. Кнопка «Редактировать» открывает это изображение в редакторе PictorX.