Игра в 15 · поле 4×4
Классика. Пятнадцать плиток, одна пустая клетка и поле, которое хоть раз держал в руках каждый.
Нажмите или потяните плитку рядом с пустой клеткой. Стрелки тоже работают. Любая перемешанная позиция решаема.
Потому что на поле 4×4 из шестнадцати клеток лежат пятнадцать пронумерованных плиток, а шестнадцатая клетка пустая. Головоломку также называют «игрой в 15», такен, а в англоязычных странах 15 puzzle, Boss puzzle или Mystic Square. Она появилась в 1870-х и вызвала настоящую лихорадку в 1880 году.
Самые сложные позиции требуют ровно 80 оптимальных ходов. Это установлено полным компьютерным перебором и называется «числом Бога» для пятнашек. Если сдвиг нескольких плиток в одном ряду считать одним ходом, число снижается до 43. Типичная перемешанная позиция требует около 53 оптимальных ходов.
16! = 20 922 789 888 000 расстановок, из которых ровно половина, 10 461 394 944 000, решаема. Позиция решаема, когда сумма числа инверсий и номера строки с пустой клеткой, считая снизу от единицы, нечётна. Собранное поле даёт 0 + 1 = 1.
Секрет в порядке, а не в скорости. Соберите верхний ряд, потом левый столбец, и останется поле 3×3. Соберите его верхний ряд и левый столбец, и останется угол 2×2, который решается вращением. Два правила: никогда не ломать готовый ряд или столбец и ставить последние две плитки каждой линии вместе, короткой подготовкой, а не по одной.