Основное:    Определение | Что это такое? | История головоломки
Разновидности и вариации пятнашек | Заключение
Дополнительно:    Ссылки по теме | Об авторе — Дмитрий Аркадьев-Берлин

Определение

       Пятнашки («15 puzzle», «fihteen puzzle») — род механической головоломки с перемещением сегментов. Поле для пятнашек имеет форму квадрата 4х4, то есть на нем всего 16 мест для фишек (плиток). Чаще всего поле имеет вид доски, ящичка или рамки. Игровые фишки пронумерованы от 1 до 15, и одно место остается пустым, тем самым давая играющему возможность перемещать на это место другие фишки. В решенном («собранном») состоянии фишки должны быть выстроены по порядку от 1 до 15 слева направо, по возрастающей. Произвольно перемешивая фишки, упорядоченность головоломки нарушают, чтобы потом собрать ее заново.



Пятнашки ничуть не изменились и в наши дни.


Что это такое?

       Пятнашки являются третьей по известности и популярности механической головоломкой в мире, уступая только разве что «маститым» кубику Рубика и пазлам. Пятнашки открывают историю так называемых игр с дыркой — головоломок, в которых фишки перемещают по игровому полю, т.к. одно из мест на нем свободно. Если присмотреться, то и в пазлах и в кубике четко прослеживаются «пятнашковые» корни. Причем в последнем это заметно в большей степени: в кубике также необходимо серией перемещений восстановить изначальную упорядоченность элементов головоломки. Возьмите кубик Рубика 4х4, нанесите на грани числа от 1 до 15, оставив один сегмент пустым, и вы получите те же пятнашки. Сделайте так со всеми сторонами, и получаться объемные пятнашки сразу на 6 полях. Правда, собираться они будут уже по иному алгоритму.
       Бонус: Кубик Рубика. Пазлы. Пятнашки-пазл «Мона Лиза».



Пятнашки в виде пазлов.


История головоломки

       Родилась головоломка в 1870-х годах. В точной дате полной уверенности нет ни у кого, но чаще других называются 1874, 1876 и 1878 годы, из которых обычно предпочитают «за красивость» 1874 год. Что в нем такого красивого? Да ведь ровно 100 лет спустя будет изобретена другая великая головоломка — кубик Рубика!
       Приверженцы «красивостей» отмечают также, что изобретателем игры был никто иной, как почитаемый любителями головоломок Сэм Ллойд (Sam Loyd). Но на самом деле, он лишь утверждал, а не сделал. Настоящим изобретателем был некий почмейстер.
Факт
       Ллойд заявил, что изобрел пятнашки в 1891 году, тогда как уже в 1877 году аналогичная головоломка («Puzzle-Blocks») была запатентована почмейстером Нойесом Чепменом (Noyes Chapman) из Канастота (Canastot). А придумал прототип пятнашек Нойес еще раньше, в 1874 году. Но видимо у почмейстера напрочь отсутствовала коммерческая жилка, и популяризацией игры он совершенно не занимался.
       Эта «маленькая неувязочка» не помешала Ллойду до самой смерти с гордостью утверждать, что головоломку придумал именно он.
       В такие подробности люди предпочитали не вникать — «нам то какая разница, кто их там изобрел?!». Ведь именно Ллойд предложил 1000 долларов любому, кто правильно решит головоломку! Задачка казалась доверчивым обывателям совсем простой — всего-то и делов, что поменять местами числа 15 и 14. Остальные числа уже стояли на своих местах. 1000 долларов по тем временам была грандиозной суммой, и люди охотно «заглотили наживку»...
       Думается, родись Ллойд несколько раньше, подобная «выходка» вполне могла довести его до суда Линча.
       Кстати, даже в объявлении премии за решение Ллойд не был первым. Его опередил некий Чарльз Певи, зубодер из Массачусетса, провернувший это дело в 1880 году.
       Ллойд же провернул удачную двойную мистификацию. Во-первых — присвоив честь изобретения себе, во-вторых, в его призовом варианте не было решения. Головоломка не собиралась! Оставив в стороне моральную сторону его действий, отметим, что все же пятнашки стали широко известны именно благодаря Ллойду. Так что его можно считать если уж не автором, то в некотором роде соавтором головоломки.
       В общем, рекламная кампания Ллойда оказалась на редкость удачной — головоломки продавались миллионами. Вот только выиграть обещанные деньги, естественно, так никто и не смог. Данная головоломка имеет решение, если так называемый параметр беспорядка (число пар чисел, в которых большее число предшествует меньшему), четный. В варианте Ллойда необходимо было поменять местами только одну такую пару (15 и 14), что делало параметр беспорядка нечетным, а головоломку нерешаемой. Но в то время мало кто догадывался об этом, и началось «пятнашковое безумие», в котором приняли участие люди не только с родины головоломки, США, но и из европейских и азиатских государств, и даже из Новой Зеландии.



Карикатура, иллюстрирующая творившееся помешательство. В погоне за кажущимся близким решением люди забывали буквально обо всем.

Факт
       Ллойд, предлагая по тем временам большие деньги, знал, что ничем не рискует: композиция входит в число неразрешимых. Это аукнулось ему, когда он пытался запатентовать пятнашки — патентное бюро отвергло «игру, не имеющую решения».
Совет
       Следует помнить, что запутывая порядок плиток в пятнашках простым перемещением их по полю, мы получаем головоломку гарантированно имеющую решение. Если же их «перетасовывать», высыпав из коробки, а потом сложить хаотическим образом обратно, то в итоге мы можем получить задачку, с 50% вероятностью не имеющую решения.
       Вот что писал о тех событиях сын самого Ллойда, Сэм Ллойд-младший:
       «Премия в 1000 долларов тому, кто первым правильно решит эту головоломку, так и не была никем востребована, хотя тысячи людей утверждали, будто им удалось добиться желаемого. Люди теряли из-за головоломки «15–14» покой и сон. Рассказывали о владельцах лавок, которые забывали открывать свои заведения, о знаменитом священнике, который простоял всю зимнюю ночь под уличным фонарем, пытаясь припомнить, как ему удалось решить задачу. Самое удивительное во всех этих историях о головоломке «15–14» было то, что никто из «решивших» ее не мог вспомнить последовательность ходов, которая привела к победе. Рассказывали, будто лоцманы сажали суда на мели, а машинисты проскакивали без остановки железнодорожные станции. Известный балтиморский издатель рассказывал, как однажды он отправился на ленч и обнаружил, что сотрудники редакции и типографии самозабвенно играют в пятнадцать с полуночи, гоняя по тарелке кусочки пирога».



«Шутку» Ллойда повторила в 1999 году газета «Вечерняя Москва» (от 1.04.1999 г), так же пообещав читателям приз в 1000 долларов за решение композиции с перестановкой чисел 15 и 14.


       Ситуация с пятнашками была очень похожа на ситуацию с теоремой Ферма, безуспешно доказать которую пытались тысячи энтузиастов. Своими «решениями» они так утомили профессора Э. Ландау, по долгу службы вынужденному работать с приходящими в университет письмами, что бедняге пришлось заказать в типографии несколько сотен типовых бланков для таково вот ответа:
       «Уважаемый(ая) . . . . . . . .
Благодарю Вас за присланную Вами рукопись с доказательством Великой теоремы Ферма. Первая ошибка находится на стр. ... в строке ... . Из-за нее все доказательство утрачивает силу».
Профессор Э. М. Ландау
Цитата
       «За последние несколько недель вошла в моду новая игрушка-головоломка... и что от Атлантического океана до Тихого все население Соединенных Штатов прекратило работу и занимается только этой игрушкой; что в связи с этим вся деловая жизнь в стране замерла, ибо судьи, адвокаты, взломщики, священники, воры, торговцы, рабочие, убийцы, женщины, дети, грудные младенцы, — словом, все с утра до ночи заняты одним-единственным высокоинтеллектуальным и сложным делом... что веселье и радость покинули народ — на смену им пришли озабоченность, задумчивость, тревога, лица у всех вытянулись, на них появились отчаяние и морщины — следы прожитых лет и пережитых трудностей, а вместе с ними и более печальные признаки, указывающие на умственную неполноценность и начинающееся помешательство; что в восьми городах день и ночь работают фабрики, и все же до сих пор не удалось удовлетворить спрос на головоломку».
Марк Твен, «Американский претендент».
Факт
       Первая головоломка, принесшая коммерческий успех, была придумана Ллойдом, когда ему еще не исполнилось и двадцати лет. Разрезав картинку вдоль пунктирных линий и переставив ее части (не сгибая их при этом), мы увидим наездников, сидящих верхом на ослах. П. Т. Барнум приобрел у Ллойда право издания нескольких таких картинок и выпустил их в продажу миллионными тиражами под названием «П. Т. Барнум и его волшебные ослики». Говорят, что за несколько недель эта головоломка принесла Ллойду 10000 долларов. Не утратила она своей популярности и в наши дни.
С сайта http://stepanov.lk.net/


Левый и средний рисунки: А вот и разгадка «волшебных осликов»! Вместо того, что бы пристроить седоков на спины животных их следует разместить между ними.
Правый рисунок: сюжет головоломки Ллойду видимо навеял вот этот ковер.


Разновидности и вариации пятнашек

       Подробно останавливаться на вариациях, в которых только увеличены размеры поля, мы не будем. Собрать головоломку 4х4, 5х5…, 10-10 не столько сложнее, сколько просто дольше. Но есть ряд игр, в основу которых лег игровой механизм пятнашек (или внешняя схожесть с головоломкой), но игровой процесс которых имеет свои нюансы. Часть из них мы и рассмотрим ниже.

RATE YOUR...
       Головоломка, разновидность обычных пятнашек 4х4, но с подвохом. На плитки нанесены не числа, а буквы, которые в собранном состоянии образуют фразу RATE YOUR MIND PAL (что можно перевести как: «пораскинь мозгами, приятель»). Собранная головоломка показывается «жертве», и затем буквы перемешиваются. На первый взгляд бессистемно. На самом деле, «тасующий» загоняет букву R из слова YOUR в верхний угол, на место буквы R слова RATE. Большинство людей оставит букву R на «ее месте» — в левом верхнем углу, и будет пытаться расположить по порядку остальные буквы. Эта задача безнадежна, потому что, такая перестановка букв R, изменяет четность композиции и «жертва» решает ее фрагмент с нечетным параметром беспорядка. В лучшем случае у нее получится фраза «RATE YOUR MIND PLA». В русском варианте используется фраза (без знаков препинания) «СЛОН СПИТ СТОЯ. А ВЫ?». Для расстановки ловушки следует поменять местами буквы С в словах СЛОН и СПИТ.



«Честный» вариант надувательства по-ллойдовски. Задача имеет решение, хотя и неочевидное.


Broken heart («Разбитое сердце»)
       Эту головоломку недавно придумали в Японии. Доска в ней имеет размеры 17x17. Играют восемью плитками 6x5. Половина из них уложена горизонтально, а вторая половина — вертикально. В собранном состоянии на фишках виден рисунок сердечка. Перед игрой фишки перемешивают, а цель игры в том, чтобы переставить прямоугольники так, чтобы собрать сердце заново. Сделать это не так просто, как может показаться, ведь три «горизонтальных» прямоугольника не помещаются в одной строке, а три «вертикальных» — в одном столбце.



Кратчайшее известное решение головоломки требует 37 перемещений плиток.


Genius
       Автором головоломки является Милтон Бредли, запатентовавший ее в 1982 году. На поле 3х3 необходимо перемещать (по «пятнашечному» принципу) 8 плиток, подсвеченных светодиодами. Как только плитка занимает свое место, ее светодиод загорается. Цель игры — «зажечь» все плитки.



Головоломка Genius.


Virus
       Разновидность пятнашек с полем 4х4, запатентованная Довом Несисом в 1998 году. Плитки под пауком необходимо выстроить так, чтобы получился рисунок паутины. Сложности игре добавляет то, что оказавшись на своем месте, плитка, располагающаяся под одной из 6 лапок паука, блокируется и не принимает участие в дальнейшем перемещении.



«Жуткий, но симпатичный» паучок из головоломки Virus.


Sokoban («кладовщик», «грузчик»)
       Не стану утверждать, что игра явилась первой компьютерной вариацией пятнашек, но то, что она была (и есть) одной из самых известных, это совершенно точно. Автором (японец Хироуки Имабаячи (Hiroyuki Imabayashi) придумал ее в 1980 году. Суть классической игры в перемещении коробок по складу с тем, чтобы расставить их на отмеченные места. В игре есть ряд ограничений — коробки перемещать можно только по одной и нельзя их тянуть, а можно только толкать перед собой. Загнанная в угол коробка там и останется, а игру придется начинать заново.
       Бонус: кладезь сокобанов.



Благодаря простоте правил и обилию вариантов решения, игра не утратила популярности и по сей день. В данном случае «просто» не означает «легко».


Магический квадрат
       Головоломка с клетками и числами для любителей математики, не требующая для решения ничего, кроме листочка с бумагой и карандаша. В квадрате заданного размера необходимо расставить все числа так, чтобы сумма чисел, стоящих по вертикали, горизонтали и главным диагоналям была одинакова. Например, в квадрате 3х3 необходимо расставить цифры от 1 до 9, а в квадрате 4х4 числа от 1 до 16 и т.д. В первом случае сумма решения равна 15, во втором 34.
       Интересно, что в первоначальном варианте пятнашек почмейстера Чепмена как раз необходимо было сложить такой квадрат со сторонами 4х4. «Довел до ума» игру его сын Фрэнк Чепмен.
       Бонус: статья о магических квадратах из Википедии.



Если совладать с квадратом 3х3 под силу даже двоечнику, то над гигантами величиной 6х6 и более поломает голову даже хорошо образованный человек.


Минус-кубик
       Объемный вариант пятнашек, изобретенный М.И. Зубряевым и выпускаемый в СССР. В прозрачную коробку уложены 7 двуцветных кубиков. Одно место остается пустым. Перемещая кубики, необходимо сложить их так, чтобы каждая сторона «недокуба» была окрашена в свой цвет. Интересно, что головоломка выпускалась в двух вариантах, московском и свердловском. И при внешнем сходстве (игрушки различались только цветами), собрать свердловский вариант оказывалось гораздо труднее. Дело тут в различиях в начальном расположении кубиков в коробке, которое влияет на число доступных верных решений. У московского варианта таких решений было в 12 раз больше.
       Бонус: статья о головоломке из журнала «Квант».



Минус-кубик и его родной брат Кубер.


Минус-шарик
       Головоломка Минус-шарик напоминает вышеописанный минус-куб. Тот же прозрачный куб, но заполненный не кубиками, а шариками трех цветов. Для обеспечения возможности перемещения шариков одного шарика не хватает. Цель игры заключается в том, чтобы расставить шарики так, чтобы образовалось три слоя, окрашенных каждый в свой цвет.
       Существовал западный аналог головоломки, называющийся «Mad Marbles», в котором на месте центрального шарика располагалась крестовина.



Еще одно головоломное творение изобретателя Зубряева — Минус-шарик.


Sliding Piece Puzzle (головоломки с подвижными блоками)
       Большой и очень популярный на Западе пласт головоломок, к которому можно отнести и пятнашки, и большинство других головоломок из данной статьи. Игровой механизм головоломки уже знаком нам — существует ряд плиток (обычно различного размера и формы), которые надо упорядочить определенным образом, используя свободное место на игровом поле.
       Бонус: головоломка с 9-ю блоками.



Составить из такого разнородного набора деталей определенную фигурку – задача не из простых.


Заключение

       Сейчас пятнашки уже не вызывают вокруг себя того ажиотажа, который имел место больше века назад. Но если рассматривать ситуацию в целом, то своим грандиозным успехом (и тому, что про них не забыли и до сих пор) пятнашки были обязаны не только пресловутой «штуке баксов», но и тонкому балансу между сложностью головоломки и ее решаемостью (естественно, для вариантов, решение имеющих), которая обеспечивала удовольствие большинству людей, сумевших разгадать ее и радостно прочувствовать свой интеллект. Хотя число различных комбинаций, имеющих решение в игре, достаточно велико (10461394944000, учитывая пропущенную шестнадцатую плитку), так что наблюдательному и усидчивому человеку ее решение не покажется особо сложным.
       Максимальное количество ходов (при оптимальной игре), необходимых для решения головоломки размером 4х4, равно 80.



Даже не верится сейчас, что когда-то вокруг этой невзрачной коробочки кипели такие страсти.


Ссылки по теме

Русскоязычные
       " Механические головоломки — что это такое? — обзорно-классификационная статья с сайта — http://www.intelgame.ru/.
       " История создания головоломок — статья с сайта — http://tmn.fio.ru/works/.
       " История головоломок — с сайта — http://igrushka.kz/.
       " Алгоритм решения пятнашек с сайта — http://maxik.port33.ru/.
       " Разделяй и складывай! — факты из истории головоломок мира, статья с сайта — http://www.ng.ru/.
       " Головоломки Сэма Ллойда — статья с сайта — http://offline.computerra.ru/.
       " Уход в абстракцию — тематическая статья с сайта — http://rrc.dgu.ru/res/mikel.altonika.ru/.
       " Различные флеш-модификации пятнашек — с сайта — http://goft.altnet.ru/.
       " Sloyd 3 — интересный флеш-гибрид пятнашек и кубика Рубика, с сайта — http://onlineguru.ru/.

Англоязычные
       " The history of the 15 puzzle — история пятнашек с сайта — http://bd.thrijswijk.nl/.
       " Пятнашки онлайн с сайта — http://www.holotronix.com/.
       " 15 Puzzle — классические пятнашки с сайта — http://www.archimedes-lab.org/.
       " The 15 Puzzle book — книга о пятнашках в интернет-магазине http://www.amazon.com/.
       " Sliding puzzle — статья о «пятнашкоподобных» играх из Википедии.
       " Sliding Block Puzzles — страничка головоломок с сайта — http://www.cleverwood.com/.
       " Puzzle Patents — информация о патентах на наиболее интересные головоломки с 60-ых годов прошлого века.


Основное:    Определение | Что это такое? | История головоломки
Разновидности и вариации пятнашек | Заключение
Дополнительно:    Ссылки по теме | Об авторе — Дмитрий Аркадьев-Берлин