Історія створення - нешарнірние головоломки

Хрест адмірала Макарова

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

Цей вузол зв'язується з 6 брусків квадратного перетину. У брусках є пази, завдяки яким і можливо схрещування брусків в центрі вузла. Один з брусків не має пазів, він закладається в вузол останнім, а при розбиранні виймається першим.

Різноманіття чортових вузлів

До початку нашого століття, за кілька сот років існування іграшки в Китаї, Монголії та Індії було придумано більше ста варіантів головоломки, що відрізняються між собою конфігурацією вирізів в брусках. Але найпопулярнішими залишаються два варіанти. Показаний на першого малюнка вирішується досить легко, просто його і виготовити. Саме ця конструкція використана в давньої індійської скриньці. З брусків другого малюнка складається головоломка, яка називається «Чортів вузол». Як ви здогадуєтеся, свою назву вона отримала за складність вирішення.

В Європі, де, починаючи з кінця минулого століття, «Чортів вузол» отримав широку популярність, ентузіасти стали придумувати і робити набори брусків з різними конфігураціями вирізів. Один з найбільш вдалих комплектів дозволяє отримувати 159 головоломок і складається з 20 брусків 18 видів. Хоча всі вузли зовні невиразні, вони абсолютно по різному влаштовані всередині.

Наполегливіше всіх в таких пошуках був голландський професор математики Ван де Боєр, який своїми руками зробив набір з декількох сотень брусків і склав таблиці, що показують, як зібрати 2906 варіантів вузлів.

Це було в 60-ті роки, а в 1978 році американський математик Білл Катлер написав програму для комп'ютера і методом повного перебору визначив, що існує 119 979 варіантів головоломки з 6 елементів, що відрізняються один від одного комбінаціями виступів і западин в брусках, а також розміщенням брусків, за умови, що всередині вузла немає пустот. Дивно велика кількість для такої маленької іграшки! Тому для вирішення завдання і знадобилася ЕОМ.

Як ЕОМ вирішує головоломки?

Звичайно, не так, як людина, але і не якимось чарівним способом. Комп'ютер вирішує головоломки (і інші завдання) за програмою, програми пишуть програмісти. Пишуть, як їм зручно, але так, щоб було зрозуміло і ЕОМ. Як же ЕОМ маніпулює дерев'яними брусками?

Будемо виходити з того, що ми маємо набір з 369 брусків, що відрізняються один від одного конфігураціями виступів (цей набір першим визначив Ван де Боєр). У ЕОМ треба ввести опису цих брусків. Мінімальний виріз (або виступ) в бруску - це кубик з ребром, рівним 0,5 товщини бруска. Назвемо його одиничним кубиком. В цілому бруску містяться 24 таких кубика. У ЕОМ для кожного бруска заводиться «малий» масив з 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 є найбільшою складністю супервузлом?