Что такое пятнашки?
Пятнашки - это плоское поле из плиток с ровно одной пустой клеткой. Плитки двигаются только сдвигом в пустую клетку, их нельзя поднимать. Цель - расставить плитки по порядку, обычно слева направо и сверху вниз. Самый известный вариант - поле 4×4 с пятнадцатью пронумерованными плитками, придуманное в 1870-х и прославленное Сэмом Лойдом.
Чем отличаются пятнашки, восьмёрка и «игра в 15»?
Это одна и та же семья головоломок, названная по числу плиток. Пятнашки, «игра в 15» и 15 puzzle - поле 4×4 с пятнадцатью плитками. Восьмёрка (8 puzzle) - поле 3×3 с восемью плитками. Поле 5×5 называют 24 puzzle. Число всегда равно количеству плиток, то есть на единицу меньше числа клеток.
За сколько ходов можно собрать пятнашки?
Зависит от размера поля. Любая позиция 3×3 собирается не более чем за 31 ход. Любая позиция 4×4 - не более чем за 80 ходов; это доказано полным компьютерным перебором и называется «числом Бога» для пятнашек. Для 5×5 точный максимум неизвестен: самые сложные найденные позиции требуют не меньше 152 ходов, и ни одна не требует больше 208. Человек, собирая вручную, обычно тратит в два-четыре раза больше оптимального.
Почему пятнашки не собираются? Нерешаемая комбинация
Потому что ровно половина всех расстановок нерешаема: вторая половина недостижима сдвигами, сколько бы ходов вы ни сделали. Проверка - подсчёт чётности: выпишите плитки в порядке чтения и посчитайте инверсии, то есть пары, где большее число стоит раньше меньшего. На поле с нечётной стороной (3×3, 5×5) позиция решаема, когда это число чётно. На поле с чётной стороной (4×4, 6×6) прибавьте номер строки с пустой клеткой, считая снизу от единицы; позиция решаема, когда сумма нечётна. Собранное поле даёт 0 + 1 = 1.
Как играть в пятнашки и какая стратегия работает лучше всего?
Цель - сдвигами выстроить плитки по порядку, а стратегия одна: собирайте слоями и никогда не ломайте готовый слой. Сначала верхний ряд, потом левый столбец, а оставшееся считайте меньшей головоломкой. Повторяйте, пока не останется угол 2×2, и докрутите последние три плитки. Последние две плитки каждого ряда ставьте вместе, а не по одной. Метод одинаково работает на 3×3, 4×4, 5×5 и больше.