Интересные факты про пятнашки
Многие наверное еще с детства помнят популярную головоломку под названием «Пятнадцать» или «Пятнашки». Оказывается эта небольшая коробочка с ячейками 4х4 и 15 нумерованными квадратными шашками имеет любопытную историю, о которой мало кто из игроков подозревает.
Несмотря на распространенное заблуждение, что изобретателем игры был известный в то время американский шахматист и изобретатель головоломок Сэмюэл Лойд (который до самой смерти утверждал, что он изобрел головоломку), на самом деле авторство пятнашек принадлежит скромному почтовому служащему Ною Чэпмену, который 1874 году впервые показал головоломку друзьям. Со временем с рук на руки головоломка распространилась по всей Америке, ее производство быстро поставили на поток предприимчивые торговцы. Эх знал бы Ной о популярности своего детища заранее, так заранее оформил бы на него патент, а потом было уже слишком поздно.
Жизнь распорядилась иначе, изобретателя ровно на год опередил предпринематель Эрнест У. Кинси. оформив авторство на себя 1879 году. Тем временем в пятнашки играли уже повсеместно. Этому поспособствовали заказные статьи в газетах и интересный рекламный ход. В начале 1880 года некий Чарльз Певи, дантист из Вустера, предложив крупное денежное вознаграждение за решение задачи собирания головоломки с переставленными местами цифрами 14 и 15, которые нужно ходами поставить на место. На волне новой популярности весной того же года игра достигла Европы
Через некоторое время было проведено математическое описание головоломки, которое показало что половина вариантов задач, в том числе и задача с 14 и 15, не имеют решения, а максимальная комбинация всевозможных вариантов достигает 20 922 789 888 000.
Чтобы подогреть интерес публики выпускались новые виды пятнашек с большим колличеством ячеек и использующие вместо цифр буквы и кусочки картинки. Так головоломка дожила до времен компьютерной техники, где ей тоже нашли применение. С 1960-х годов ее регулярно используют в исследованиях возможностей Искусственного Интелекта. Головоломка 3 × 3 легко решается любым алгоритмом поиска. Пятнашки 4 × 4 решаются современными ИИ за несколько миллисекунд. А для оптимального решения головоломки 5 × 5 требуются больши́е затраты ресурсов даже с применением современных компьютеров и алгоритмов, а время занимает до нескольких недель. Оптимальное решение произвольных конфигураций головоломки 6 × 6 до сих пор находится за пределами возможностей современных компьютеров.
