1. Різноманіття чортових вузлів
2. Як ЕОМ вирішує головоломки?
3. Суперузел
4. рішення супервузлів
5. Головоломка У. Катлера ( «колючка Білла»)
6. Головоломка Філіпа Дюбуа (рис. 4)
7. Три супервузлом Д. Вакарелова.

Світ влаштований так, що речі в ньому можуть жити довше, ніж люди, мати різні імена в різний час і в різних країнах. Іграшка, яку ви бачите на малюнку, відома в нашій країні як «головоломка адмірала Макарова». В інших країнах вона має інші імена, з яких найбільш часто зустрічаються - «диявольський хрест» і «чортів вузол».

Цей вузол зв'язується з 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 ходів за наступним алгоритмом: (6 z) ^ 2, 3 x. 1 z, 4х, 2х, 2у, 2z ?. Ha малюнку показано розташування деталей на б таге розбирання. Починаючи з цього положення, використовуючи зворотний порядок алгоритму і змінюючи напрямку руху на протилежні, можна зібрати головоломку.

Рис. 4 Суперузел Ф. Дюбая складність 7

Три супервузлом Д. Вакарелова.

Рис. 5 Суперузел Д.Вакарелова складності 9

Перша з його головоломок (рис. 5) - це вдосконалений варіант головоломки Дюбуа, він має складність 9. Цей суперузел найбільше схожий на лабіринт, так як при його розбиранні виникають помилкові ходи, заводять в безвихідь. Приклад такого глухого кута - ходи З х, 1 z на початку розбирання. А правильне рішення таке:

(6 z) ^ 2, З х, 1z, 4х, 2х, 2у, 5x, 5y, 3z ?.

Рис. 6 Суперузел Д. Вакарелова складності 11

Друга головоломка Д. Вакарелова (рис. 6) вирішується за формулою:

4 z, 1 z, Зх, 2х, 2 z, З х, 1z, 6z, З х, 1 х, 3z?

і має складність 11. Вона чудова тим, що брусок 3 на третьому ходу робить крок Зх, а на шостому ходу повертається назад (З х); і брусок 1 на другому кроці рухається по 1 z, а на 7 ходу робить зворотний хід.

Рис. 7 Суперузел Д. Вакарелова складності 12

Третя головоломка (рис. 7) - одна з найскладніших. Її рішення:
4z, 1 z, Зх, 2х, 2 z, З х, 6 z, 1z, (1,3,6) х, 5y?
до сьомого ходу повторює попередню головоломку, потім, на 9 ходу в ній зустрічається зовсім нова ситуація: несподівано все бруски перестають рухатися! І тут необхідно здогадатися посунути відразу 3 бруска (1, 3, 6), і якщо цей рух вважати за 3 ходу, то складність головоломки дорівнюватиме 12.

Стаття взята з журналу « Квант «.