Перетворення головоломки адмірала Макарова (д
Цей вузол зв'язується з 6 брусків квадратного перетину. У брусках є пази, завдяки яким і можливо схрещування брусків в центрі вузла. Один з брусків не має пазів, він закладається в вузол останнім, а при розбиранні виймається першим.
Купити одну з таких головоломок можна, наприклад, на my-shop.ru
Різноманіття чортових вузлів
До початку нашого століття, за кілька сот років існування іграшки в Китаї, Монголії та Індії було придумано більше ста варіантів головоломки, що відрізняються між собою конфігурацією вирізів в брусках. Але найпопулярнішими залишаються два варіанти. Показаний на малюнку 1 вирішується досить легко, просто його і виготовити. Саме ця конструкція використана в давньої індійської скриньці. З брусків малюнка 2 складається головоломка, яка називається «Чортів вузол». Як ви здогадуєтеся, свою назву вона отримала за складність вирішення.
Мал. 1 Найпростіший варіант головоломки «чортів вузол»
В Європі, де, починаючи з кінця минулого століття, «Чортів вузол» отримав широку популярність, ентузіасти стали придумувати і робити набори брусків з різними конфігураціями вирізів. Один з найбільш вдалих комплектів дозволяє отримувати 159 головоломок і складається з 20 брусків 18 видів. Хоча всі вузли зовні невиразні, вони абсолютно по різному влаштовані всередині.
Мал. 2 «Головломка адмірала Макарова»
Наполегливіше всіх в таких пошуках був голландський професор математики Ван де Боєр, який своїми руками зробив набір з декількох сотень брусків і склав таблиці, що показують, як зібрати 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 брусків сильно зростає і повний перебір, необхідний для пошуку допустимих рішень, стає нереальним навіть для сучасного комп'ютера. Але як ми побачимо зараз, найцікавіші і важкі головоломки містяться саме в загальному випадку - розбирання головоломки тоді можна зробити далеко не тривіальним.
Завдяки наявності порожнеч, з'являється можливість послідовно пересунути кілька брусків перш, ніж вдасться повністю відокремити будь-якої брусок. Рухомий брусок відчіплює деякі бруски, дозволяє рух наступного бруска і одночасно зачіпає інші бруски.
Чим більше потрібно виконати маніпуляцій при розбиранні, тим цікавіше і важче варіант головоломки. Пази в брусках розташовані так хитро, що пошук рішення нагадує блукання по темному лабіринту, в якому весь час натрапляєш то на стіни, то на тупики. Такого типу вузол безсумнівно заслуговує і нового імені; ми будемо називати його «суперузел». Мірою складності супервузлом назвемо кількість рухів окремих брусків, які необхідно зробити до того, як перший елемент буде відділений від головоломки.
рішення супервузлів
Наводити креслення таких важких головоломок, як супервузли, і не розкривати їх секретів було б занадто жорстоко по відношенню навіть до знавців головоломок. Ми дамо рішення супервузлів в компактній, алгебраїчної формі.
Перед розбиранням беремо головоломку і орієнтуємо так, щоб номери деталей відповідали малюнку 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» збирається якимось іншим способом.
Головоломка Філіпа Дюбуа (рис. 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) - одна з найскладніших. Її рішення:
4 z. 1 z. Зх, 2х, 2 z. З х. 6 z. 1z, (1,3,6) х. 5y?
до сьомого ходу повторює попередню головоломку, потім, на 9 ходу в ній зустрічається зовсім нова ситуація: несподівано все бруски перестають рухатися! І тут необхідно здогадатися посунути відразу 3 бруска (1, 3, 6), і якщо цей рух вважати за 3 ходу, то складність головоломки дорівнюватиме 12.