Мир устроен так, что вещи в нем могут жить дольше, чем люди, иметь разные имена в разное время и в разных странах. Игрушка, которую вы видите на рисунке, известна в нашей стране как «головоломка адмирала Макарова». В других странах она имеет другие имена, из которых наиболее часто встречающиеся — «дьявольский крест» и «чертов узел».
Этот узел связывается из 6 брусков квадратного сечения. В брусках имеются пазы, благодаря которым и возможно скрещивание брусков в центре узла. Один из брусков не имеет пазов, он закладывается в узел последним, а при разборке вынимается первым.
Купить одну из таких головоломок можно, например, на my-shop.ru
А так же вот различные вариации на тему раз, два, три, четыре, пять, шесть, семь, восемь.
Автор этой головоломки неизвестен. Появилась она много веков назад в Китае. В ленинградском Музее антропологии и этнографии им. Петра Великого, известном как «Кунсткамера», хранится старинная, сандалового дерева шкатулка из Индии, в 8 углах которой пересечения брусков каркаса образуют 8 головоломок. В средние века моряки и купцы, воины и дипломаты забавлялись такими головоломками и заодно развозили их по свету. Адмирал Макаров, дважды бывавший в Китае до своей последней поездки и гибели в Порт-Артуре, привез игрушку в Петербург, где она вошла в моду в светских салонах. В глубину России головоломка проникала и другими дорогами. Известно, что в деревню Олсуфьево Брянской области чертов узел принес солдат, вернувшийся с русско-туредкой войны.
Сейчас головоломку можно купить в магазине, но приятнее сделать ее своими руками. Наиболее подходящий размер брусков для самодельной конструкции: 6х2х2 см.
Многообразие чертовых узлов
До начала нашего века, за несколько сот лет существования игрушки в Китае, Монголии и Индии было придумано более ста вариантов головоломки, отличающихся между собой конфигурацией вырезов в брусках. Но самыми популярными остаются два варианта. Показанный на рисунке 1 решается довольно легко, просто его и изготовить. Именно эта конструкция использована в древней индийской шкатулке. Из брусков рисунка 2 складывается головоломка, которая называется «Чертов узел». Как вы догадываетесь, свое название она получила за трудность решения.
Рис. 1 Простейший вариант головоломки «чёртов узел»
В Европе, где, начиная с конца прошлого века, «Чертов узел» получил широкую известность, энтузиасты стали придумывать и делать наборы брусков с разными конфигурациями вырезов. Один из наиболее удачных комплектов позволяет получать 159 головоломок и состоит из 20 брусков 18 видов. Хотя все узлы внешне неразличимы, они совершенно по разному устроены внутри.
Рис. 2 «Головломка адмирала Макарова»
Болгарский художник, профессор Петр Чуховски, автор множества причудливых и красивых деревянных узлов из разного количества брусков, тоже занимался головоломкой «Чертов узел». Он разработал набор конфигураций брусков и исследовал всевозможные комбинации 6 брусков для одного простого его поднабора.
Настойчивее всех в таких поисках был голландский профессор математики Ван де Боер, который своими руками сделал набор из нескольких сотен брусков и составил таблицы, показывающие, как собрать 2906 вариантов узлов.
Это было в 60-е годы, а в 1978 году американский математик Билл Катлер написал программу для компьютера и методом полного перебора определил, что существует 119 979 вариантов головоломки из 6 элементов, отличающихся друг от друга комбинациями выступов и впадин в брусках, а также размещением брусков, при условии, что внутри узла нет пустот.
Удивительно большое число для такой маленькой игрушки! Поэтому для решения задачи и понадобилась ЭВМ.
Как ЭВМ решает головоломки?
Конечно, не так, как человек, но и не каким-то волшебным способом. Компьютер решает головоломки (и другие задачи) по программе, программы пишут программисты. Пишут, как им удобно, но так, чтобы было понятно и ЭВМ. Как же ЭВМ манипулирует деревянными брусками?
Будем исходить из того, что мы имеем набор из 369 брусков, отличающихся друг от друга конфигурациями выступов (этот набор первым определил Ван де Боер). В ЭВМ надо ввести описания этих брусков. Минимальный вырез (или выступ) в бруске — это кубик с ребром, равным 0,5 толщины бруска. Назовем его единичным кубиком. В целом бруске содержатся 24 таких кубика (рисунок 1). В ЭВМ для каждого бруска заводится «малый» массив из 6х2х2=24 чисел. Брусок с вырезами задается последовательностью 0 и 1 в «малом» массиве: 0 соответствует вырезанному кубику, 1 — целому. Каждый из «малых» массивов имеет свои номер (от 1 до 369). Любому из них можно присвоить еще номер от 1 до 6, отвечающий положению бруска внутри головоломки.
Перейдем теперь к головоломке. Представим, что она помещается внутрь куба размером 8х8х8. В ЭВМ этому кубу соответствует «большой» массив, состоящий из 8х8х8=512 ячеек-чисел. Поместить определенный брусок внутрь куба — это значит заполнить соответствующие ячейки «большого» массива числами, равными номеру данного бруска.
Сравнивая 6 «малых» массивов и основной, ЭВМ (т. е. программа) как бы складывает вместе 6 брусков. По результатам сложения чисел она определяет, сколько и каких «пустых», «заполненных» и «переполненных» ячеек образовалось в основном массиве. «Пустые» ячейки соответствуют пустому пространству внутри головоломки, «заполненные» — соответствуют выступам в брусках, а «переполненные» — попытке соединить вместе два единичных кубика, что, естественно, запрещено. Такое сравнение производится многократно, не только с разными брусками, но и с учетом их разворотов, мест, которые они занимают в «кресте», и т. п.
В результате отбирают те варианты, в которых нет пустых и переполненных ячеек. Для решения этой задачи достаточно было бы «большого» массива размером 6х6х6 ячеек. Оказывается, однако, что существуют комбинации брусков, полностью заполняющие внутренний объем головоломки, но при этом разобрать их невозможно. Поэтому программа должна уметь проверять узел на возможность разборки. Для этого Катлер и взял массив 8х8х8, хотя его размеры, возможно, недостаточны для проверки всех случаев.
Он заполняется информацией о конкретном варианте головоломки. Внутри массива программа пытается «двигать» бруски, т. е. перемещает в «большом» массиве части бруска размером 2х2х6 ячеек. Перемещение происходит на 1 ячейку в каждом из 6 направлении, параллельных осям головоломки. Результаты тех из 6 попыток, в которых не образуется «переполненных» ячеек, запоминаются как исходные положения для следующих шестерок попыток. В результате строится дерево всевозможных движений до тех пор, пока какой-нибудь брусок целиком не выйдет из основного массива или же после всех попыток останутся «переполненные» ячейки, что соответствует варианту, который невозможно разобрать.
Вот так были получены на ЭВМ 119 979 вариантов «Чертова узла», в том числе не 108, как полагали древние, а 6402 варианта, имеющих 1 целый, без вырезов брусок.
Суперузел
Обратим внимание, что Катлер отказался от исследования общей задачи — когда узел содержит и внутренние пустоты. В этом случае количество узлов из 6 брусков сильно возрастает и полный перебор, необходимый для поиска допустимых решений, становится нереальным даже для современного компьютера. Но как мы увидим сейчас, самые интересные и трудные головоломки содержатся именно в общем случае — разборку головоломки тогда можно сделать далеко не тривиальной.
Благодаря наличию пустот, появляется возможность последовательно передвинуть несколько брусков прежде, чем удастся полностью отделить какой-либо брусок. Движущийся брусок отцепляет некоторые бруски, разрешает движение следующего бруска и одновременно зацепляет другие бруски.
Чем больше нужно проделать манипуляций при разборке, тем интереснее и труднее вариант головоломки. Пазы в брусках расположены так хитро, что поиск решения напоминает блуждание по темному лабиринту, в котором все время наталкиваешься то на стены, то на тупики. Такого типа узел несомненно заслуживает и нового имени; мы будем называть его «суперузел». Мерой сложности суперузла назовем количество движений отдельных брусков, которые необходимо сделать до того, как первый элемент будет отделен от головоломки.
Мы не знаем, кто придумал первый суперузел. Наиболее знамениты (и наиболее трудны в решении) два суперузла: «колючка Билла» сложности 5, придуманная У. Катлером, и «суперузел Дюбуа» сложности 7. До сих пор считалось, что степень сложности 7 едва ли можно превзойти. Однако первому из авторов этой статьи удалось усовершенствовать «узел Дюбуа» и увеличить сложность до 9, а затем, используя некоторые новые идеи, получить суперузлы со сложностью 10, 11 и 12. Но число 13 остается пока непреодолимым. Может быть, число 12 является самой большой сложностью суперузла?
Решение суперузлов
Приводить чертежи таких трудных головоломок, как суперузлы, и не раскрывать их секретов было бы слишком жестоко по отношению даже к знатокам головоломок. Мы дадим решение суперузлов в компактной, алгебраической форме.
Перед разборкой берем головоломку и ориентируем так, чтобы номера деталей соответствовали рисунку 1. Последовательность разборки записывается в виде сочетания цифр и букв. Цифры означают номера брусков, буквы — направления движения в соответствии с показанной на рисунках 3 и 4 системой координат. Черта над буквой означает движение в отрицательном направлении оси координат. Один шаг — это перемещение бруска на 1/2 его ширины. Когда брусок передвигается сразу на два шага, его перемещение записывается в скобках с показателем степени 2. Если передвигают сразу несколько деталей, которые зацеплены между собой, то их номера заключают н скобки, например (1, 3, 6) х. Отделение бруска от головоломки отмечается вертикальной стрелкой.
Приведем теперь примеры лучших суперузлов.
Головоломка У. Катлера («колючка Билла»)
Она состоит из деталей 1, 2, 3, 4, 5, 6, показанных на рисунке 3. Там же приводится алгоритм ее решения. Любопытно, что в журнале «Scientific American» (1985, № 10) приведен другой вариант этой головоломки и сообщается, что «колючка Билла» имеет единственное решение. Различие между вариантами — всего в одном бруске: деталях 2 и 2 В на рисунке 3.
Рис. 3 «Колючка Билла», разработанна с помощью ЭВМ.
Из-за того, что деталь 2 В содержит меньше вырезов, чем деталь 2, вставить ее в «колючку Билла» по указанному на рисунке 3 алгоритму не удается. Остается предположить, что головоломка из «Scientific American» собирается каким-то другим способом.
Если это так и мы ее соберем, то после этого сможем заменить деталь 2 В на деталь 2, так как последняя занимает меньший объем, чем 2 В. В результате мы получим второе решение головоломки. Но «колючка Билла» имеет единственное решение, и из нашего противоречия можно сделать только один вывод: во втором варианте допущена ошибка в рисунке.
Аналогичная ошибка сделана еще в одной публикации (Дж. Слокум, Дж. Ботерманс «Puzzles old and new», 1986), но уже в другом бруске (деталь 6 С на рисунке 3). Каково же было тем читателям, которые пытались и, возможно, пытаются до сих пор решить эти головоломки?
Головоломка Филиппа Дюбуа (рис. 4)
Она решается за 7 ходов по следующему алгоритму: (6z)^2, 3x. 1z, 4х, 2х, 2у, 2z?. Ha рисунке показано расположение деталей на б таге разборки. Начиная с этого положения, используя обратный порядок алгоритма и изменяя направления движения на противоположные, можно собрать головоломку.
Рис. 4 Суперузел Ф. Дюбая сложность 7
Три суперузла Д. Вакарелова.
Рис. 5 Суперузел Д.Вакарелова сложности 9
Первая из его головоломок (рис. 5) — это усовершенствованный вариант головоломки Дюбуа, он имеет сложность 9. Этот суперузел больше других похож на лабиринт, так как при его разборке возникают ложные ходы, заводящие в тупики. Пример такого тупика — ходы Зх, 1z в начале разборки. А правильное решение такое:
(6z)^2, Зх,1z, 4х, 2х, 2у, 5x, 5y, 3z?.
Рис. 6 Суперузел Д. Вакарелова сложности 11
Вторая головоломка Д. Вакарелова (рис. 6) решается по формуле:
4z,1z, Зх, 2х, 2z, Зх, 1z, 6z, Зх, 1х,3z?
и имеет сложность 11. Она замечательна тем, что брусок 3 на третьем ходу делает шаг Зх, а на шестом ходу возвращается обратно (Зх); и брусок 1 на втором шаге двигается по 1z, а на 7 ходу делает обратный ход.
Рис. 7 Суперузел Д. Вакарелова сложности 12
Третья головоломка (рис. 7) — одна из самых сложных. Ее решение:
4z, 1z, Зх, 2х, 2z, Зх, 6z, 1z, (1,3,6)х, 5y?
до седьмого хода повторяет предыдущую головоломку, затем, на 9 ходу в ней встречается совершенно новая ситуация: неожиданно все бруски перестают двигаться! И тут необходимо догадаться подвинуть сразу 3 бруска (1, 3, 6), и если это движение считать за 3 хода, то сложность головоломки будет равна 12.
Статья взята из журнала «Квант«.
Какащъ у нас другое лолололол