Пятнашки
Пятнашки — это коробка с пятнадцатью пронумерованными фишками и одной пустой клеткой. Сдвигами расставьте фишки обратно по порядку, и головоломка решена. Она выглядит простой, но в 1880 году вызвала повальное увлечение, а за ней стоит одно из самых изящных доказательств занимательной математики: половину всех позиций решить невозможно.
Повальное увлечение 1880 года
Головоломка появилась в штате Нью-Йорк в 1870-х годах; её изобретателем обычно называют Нойеса Чепмена, почтмейстера из Канастоты. В начале 1880 года она стала повальным увлечением — сначала по всем Соединённым Штатам, а затем и в Европе.
14-15 Сэма Лойда
Американский составитель головоломок Сэм Лойд позже утверждал, что изобрёл эту головоломку, и рассказывал о премии в 1000 долларов тому, кто решит её в позиции, где поменяны местами только 14 и 15. Премию никто не получил, и никто не мог: эту позицию решить нельзя. Его притязания на изобретение тоже были неправдой.
Почему половина позиций невозможна
Считайте пустую клетку шестнадцатой фишкой. Каждый сдвиг меняет местами пустую клетку и одну фишку. Чтобы вернуться в свой угол, пустая клетка должна сдвинуться влево столько же раз, сколько вправо, и вверх столько же раз, сколько вниз, поэтому позиция с пустой клеткой в её углу всегда отстоит от решённого порядка на чётное число обменов. Обмен 14 и 15 — это один обмен, то есть нечётное число, поэтому эту позицию никакими сдвигами не получить. В 1879 году Уильям Джонсон и Уильям Стори доказали, что достижима ровно половина всех расстановок.
Проверка для любой позиции
Посчитайте пары фишек, которые стоят в неправильном порядке, если читать коробку ряд за рядом. На поле 3×3 или 5×5 позицию можно решить, когда это число чётное. На поле 4×4 прибавьте номер ряда пустой клетки, считая снизу: позицию можно решить, когда сумма нечётная.
Решение на компьютере
Компьютер может искать путь назад с помощью A*: этот поиск всегда сначала рассматривает самую многообещающую позицию. Он оценивает, сколько ходов ещё нужно, по тому, насколько каждая фишка далека от своего места, и добавляет по два хода за каждую пару фишек, которые мешают друг другу в своём ряду или столбце. На больших полях найти кратчайшее решение становится очень трудно. Самым трудным позициям игры в 15 нужно 80 ходов, а игре в 8 никогда не нужно больше 31.
Попробуйте в PictorX
Откройте «Пятнашки» и щёлкните фишку, чтобы сдвинуть её. «Перемешать» смешивает фишки в новую решаемую позицию, «Решить» проигрывает решение ход за ходом, а «Показать фишки на месте» окрашивает номера фишек, которые уже стоят на своих местах. Выберите «14-15 Лойда», чтобы увидеть невозможную позицию, а «Размер» переключает поле между 3×3, 4×4 и 5×5.
Часто задаваемые вопросы
Кто придумал пятнашки?
Изобретателем обычно называют Нойеса Чепмена, почтмейстера из Канастоты (штат Нью-Йорк); это было в 1870-х годах. Более позднее заявление Сэма Лойда об этом было ложным.
Можно ли решить головоломку 14-15?
Нет. Она отстоит от решённого порядка на один обмен, а любая позиция, достижимая сдвигами, отстоит на чётное число обменов.
Сколько позиций в пятнашках?
16 клеток можно заполнить 20 922 789 888 000 способами. Ровно половина из них, 10 461 394 944 000, достижима сдвигами.
PictorX что-нибудь загружает?
Нет. Головоломка рисуется на холсте в браузере. Кнопка «Сохранить» скачивает PNG, а кнопка «Редактировать» открывает это изображение в редакторе PictorX.
Сопутствующие инструменты
Пятнашки
Играйте в классические пятнашки в браузере: деревянные фишки на поле 3×3, 4×4 или 5×5. Перемешивайте, сдвигайте целые ряды за раз, попробуйте невозможную позицию 14-15 Сэма Лойда или посмотрите, как «Решить» доводит игру до конца.
Ханойская башня
Перенесите в браузере башню из дисков между тремя стержнями. По одному диску, никогда больший на меньший. Кратчайшее решение — 2ⁿ − 1 ходов.
Ханойская башня
Ханойская башня: три стержня, по одному диску, и никогда больший на меньший. Кратчайшее решение — 2ⁿ−1 ходов. Эдуард Люка представил головоломку в 1883 году.
Ход коня
Проведите шахматного коня по всем полям доски, побывав на каждом ровно один раз. Играйте сами с подсказками Варнсдорфа или смотрите, как «Решить» завершает открытый или замкнутый маршрут. Сохраните путь в PNG.
Восемь ферзей
Расставьте восемь ферзей на шахматной доске так, чтобы ни один не бил другого. Попробуйте сами, посмотрите, как поиск с возвратом шаг за шагом находит решение, и переберите все 92 решения.
Муравей Лэнгтона
Запустите муравья Лэнгтона в браузере. Посмотрите на симметрию, хаос и шоссе с циклом в 104 шага, а затем попробуйте многоцветные правила, нескольких муравьёв, шестиугольную сетку и турмитов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Играть в пятнашки