Пятнашки

Об этом тесте

Пятнашки — механическая головоломка второй половины XIX века: рамка, пятнадцать пронумерованных костяшек, пустая клетка, и единственное движение — сдвиг костяшки, стоящей рядом с дыркой. В 1880-е годы они пережили огромную международную моду, которую подогревали публичные вызовы с обещанной награды за решение отдельных расстановок.

Эти вызовы были нечестными, и причина математическая: достижима только половина возможных расстановок. Элементарная операция игры никогда не позволяет просто поменять местами две костяшки, так что каждое второе перемешивание строго нерешаемо. Поле здесь всегда получается из собранной позиции цепочкой законных ходов, поэтому решение у него есть всегда.

Работающий метод иерархичен и противоречит интуиции. Костяшки не толкают к своим местам одну за другой: сначала полностью заканчивают первый ряд, потом запрещают себе его трогать, затем второй, а два последних ряда решают вместе, работая столбцами по два. Те, кто переваливает за триста ходов, почти всегда разбирают уже готовый ряд ради одной костяшки.

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

Считается число сдвигов до полного порядка от 1 до 15 с пустой клеткой в правом нижнем углу. Сдаться значит провалить попытку и получить ноль. Для собранного поля оценка из 100 начинается с 400 ходов и достигает максимума на 60 ходах.