Jak złożyć chińską kostkę z 6 części. Drewniane węzły puzzli wykonane z prętów

Data: 2013-11-07

Świat jest zaprojektowany w taki sposób, że rzeczy w nim mogą żyć dłużej niż ludzie, mieć różne nazwy w różnych czasach i w różnych krajach, możemy nawet grać w gry The Simpsons. Zabawka, którą widzisz na zdjęciu, znana jest w naszym kraju jako „łamigłówka Admirała Makarowa”. W innych krajach ma inne nazwy, z których najczęstsze to „krzyż diabła” i „węzeł diabła”.

Węzeł ten jest połączony z 6 kwadratowych prętów. Pręty posiadają rowki, dzięki którym istnieje możliwość skrzyżowania prętów w środku węzła. Jeden z prętów nie ma rowków, jest wkładany do zespołu jako ostatni, a przy demontażu jest usuwany jako pierwszy.

Autor tej zagadki jest nieznany. Pojawił się wiele wieków temu w Chinach. W Leningradzkim Muzeum Antropologii i Etnografii im. Piotra Wielkiego, zwanego „Kunstkamerą”, znajduje się starożytna skrzynia z drzewa sandałowego z Indii, w której 8 rogach przecięcia prętów ramy tworzą 8 puzzli. W średniowieczu marynarze i kupcy, wojownicy i dyplomaci bawili się takimi łamigłówkami i jednocześnie nosili je po całym świecie. Admirał Makarow, który przed swoją ostatnią podróżą i śmiercią w Port Arthur dwukrotnie odwiedził Chiny, przywiózł zabawkę do Petersburga, gdzie stała się modna na świeckich salonach. Zagadka przenikała w głąb Rosji także innymi drogami. Wiadomo, że do wsi Olsufiewo w obwodzie briańskim przywiózł tobołek diabła żołnierz powracający z wojny rosyjsko-tureckiej.

Obecnie puzzle można kupić w sklepie, ale przyjemniej jest je wykonać samodzielnie. Najbardziej odpowiedni rozmiar prętów do domowej konstrukcji: 6x2x2 cm.

Różnorodność cholernych węzłów

Przed początkiem naszego stulecia, w ciągu kilkuset lat istnienia zabawki, w Chinach, Mongolii i Indiach wynaleziono ponad sto wariantów tej układanki, różniących się konfiguracją wycięć w prętach. Ale dwie opcje pozostają najpopularniejsze. Zadanie pokazane na rysunku 1 jest dość łatwe do rozwiązania; wystarczy to zrobić. To jest wzór zastosowany w starożytnym indyjskim pudełku. Z prętów przedstawionych na rysunku 2 ułożono układankę zwaną „diabelskim węzłem”. Jak można się domyślić, swoją nazwę zawdzięcza trudności w rozwiązaniu.

Ryż. 1 Najprostsza wersja łamigłówki „diabelski węzeł”.

W Europie, gdzie od końca ubiegłego wieku powszechnie znany stał się „diabelski węzeł”, entuzjaści zaczęli wymyślać i wykonywać zestawy prętów o różnych konfiguracjach wycięć. Jeden z najbardziej udanych zestawów pozwala na zdobycie 159 puzzli i składa się z 20 sztabek 18 rodzajów. Chociaż wszystkie węzły są zewnętrznie nie do odróżnienia, wewnątrz są ułożone zupełnie inaczej.

Ryż. 2 „Zagadka admirała Makarowa”

Nad łamigłówką „Diabelski węzeł” pracował także bułgarski artysta, profesor Petr Czuchowski, autor wielu dziwacznych i pięknych drewnianych sęków z różnej liczby prętów. Opracował zestaw konfiguracji prętów i zbadał wszystkie możliwe kombinacje 6 prętów w jednym prostym podzbiorze.

Najbardziej wytrwały w takich poszukiwaniach był holenderski profesor matematyki Van de Boer, który własnoręcznie wykonał zestaw kilkuset taktów i sporządził tabele pokazujące, jak złożyć 2906 wariantów węzłów.

Było to w latach 60., kiedy w 1978 roku amerykański matematyk Bill Cutler napisał program komputerowy i metodą wyczerpujących poszukiwań ustalił, że istnieje 119 979 wariantów 6-elementowej układanki, różniących się od siebie kombinacją występów i wgłębień w pręty, a także pręty rozmieszczające, pod warunkiem, że wewnątrz zespołu nie ma pustych przestrzeni.

Zaskakująco duża liczba jak na tak małą zabawkę! Dlatego do rozwiązania problemu potrzebny był komputer.

Jak komputer rozwiązuje zagadki?

Oczywiście nie jak osoba, ale też nie w jakiś magiczny sposób. Komputer rozwiązuje zagadki (i inne problemy) zgodnie z programem; programy są pisane przez programistów. Piszą, jak im się podoba, ale w sposób zrozumiały dla komputera. Jak komputer manipuluje drewnianymi klockami?

Załóżmy, że mamy zbiór 369 prętów, różniących się między sobą konfiguracjami występów (zestaw ten został po raz pierwszy określony przez Van de Boera). Opisy tych słupków należy wprowadzić do komputera. Minimalne wycięcie (lub występ) w bloku to sześcian o krawędzi równej 0,5 grubości bloku. Nazwijmy to sześcianem jednostkowym. Cały blok zawiera 24 takie kostki (rysunek 1). W komputerze dla każdego bloku tworzona jest „mała” tablica złożona z 6x2x2=24 liczb. Blok z wycięciami jest określony przez ciąg 0 i 1 w „małej” tablicy: 0 odpowiada wyciętej kostce, 1 całej. Każda z „małych” tablic ma swój własny numer (od 1 do 369). Każdemu z nich można przypisać liczbę od 1 do 6, odpowiadającą położeniu bloczka wewnątrz układanki.

Przejdźmy teraz do zagadki. Wyobraźmy sobie, że mieści się on w sześcianie o wymiarach 8x8x8. W komputerze kostka ta odpowiada „dużej” tablicy składającej się z 8x8x8 = 512 komórek liczbowych. Umieszczenie określonego bloku wewnątrz sześcianu polega na wypełnieniu odpowiednich komórek „dużej” tablicy liczbami równymi numerowi danego bloku.

Porównując 6 „małych” tablic z tablicą główną, komputer (czyli program) zdaje się dodawać do siebie 6 kresek. Na podstawie wyników dodawania liczb określa, ile i jakie komórki „puste”, „wypełnione” i „przepełnione” powstały w tablicy głównej. Komórki „puste” odpowiadają pustej przestrzeni wewnątrz układanki, komórki „wypełnione” odpowiadają występom w słupkach, a komórki „zatłoczone” odpowiadają próbie połączenia dwóch pojedynczych kostek, co oczywiście jest zabronione. Takiego porównania dokonuje się wielokrotnie, nie tylko z różnymi taktami, ale także biorąc pod uwagę ich zakręty, miejsca, jakie zajmują w „krzyżu” itp.

W rezultacie wybierane są te opcje, które nie mają pustych lub przepełnionych komórek. Aby rozwiązać ten problem, wystarczyłaby „duża” tablica komórek 6x6x6. Okazuje się jednak, że istnieją kombinacje prętów, które całkowicie wypełniają wewnętrzną objętość układanki, ale nie da się ich rozebrać. Dlatego program musi mieć możliwość sprawdzenia złożenia pod kątem możliwości demontażu. W tym celu Cutler wziął tablicę 8x8x8, choć jej wymiary mogą nie wystarczyć do przetestowania wszystkich przypadków.

Jest ona wypełniona informacjami na temat konkretnej wersji układanki. Wewnątrz tablicy program próbuje „przesunąć” słupki, czyli przesuwa części słupka o wymiarach 2x2x6 komórek w „dużej” tablicy. Ruch odbywa się o 1 komórkę w każdym z 6 kierunków, równolegle do osi układanki. Wyniki tych 6 prób, w których nie powstały „przepełnione” komórki, są zapamiętywane jako pozycje wyjściowe dla kolejnych sześciu prób. W rezultacie budowane jest drzewo wszystkich możliwych ruchów, aż jeden blok całkowicie opuści główny układ lub po wszystkich próbach pozostaną „przepełnione” komórki, co odpowiada opcji, której nie można zdemontować.

W ten sposób uzyskano na komputerze 119 979 wariantów „diabelskiego węzła”, w tym nie 108, jak sądzili starożytni, ale 6402 warianty, posiadające 1 cały blok bez nacięć.

Superwęzeł

Zauważmy, że Cutler odmówił zbadania problemu ogólnego – gdy węzeł zawiera również wewnętrzne puste przestrzenie. W tym przypadku liczba węzłów z 6 taktów znacznie wzrasta, a wyczerpujące poszukiwania wymagane do znalezienia wykonalnych rozwiązań stają się nierealne nawet dla nowoczesnego komputera. Ale jak zobaczymy teraz, najciekawsze i najtrudniejsze łamigłówki zawarte są właśnie w ogólnym przypadku - demontaż łamigłówki może wtedy nie być trywialny.

Dzięki obecności pustych przestrzeni możliwe staje się przesuwanie kilku prętów sekwencyjnie, zanim będzie można całkowicie oddzielić jeden. Poruszający się klocek odczepia niektóre pręty, umożliwia ruch następnego klocka i jednocześnie zaczepia inne pręty.

Im więcej manipulacji trzeba wykonać podczas demontażu, tym ciekawsza i trudniejsza jest wersja układanki. Rowki w prętach są tak sprytnie rozmieszczone, że znalezienie rozwiązania przypomina wędrówkę po ciemnym labiryncie, w którym nieustannie natrafia się na ściany lub ślepe zaułki. Ten rodzaj węzła niewątpliwie zasługuje na nową nazwę; nazwiemy go „superwęzłem”. Miarą złożoności superwęzła jest liczba ruchów poszczególnych prętów, jakie należy wykonać, zanim pierwszy element zostanie oddzielony od układanki.

Nie wiemy, kto wpadł na pomysł pierwszego superwęzła. Najbardziej znane (i najtrudniejsze do rozwiązania) to dwa superwęzły: „Cierń Billa” o trudności 5, wymyślony przez W. Cutlera oraz „superwęzeł Dubois” o trudności 7. Do tej pory uważano, że stopień trudności Trudno było przebić 7. Jednak pierwszemu autorowi tego artykułu udało się ulepszyć „węzeł Dubois” i zwiększyć złożoność do 9, a następnie, korzystając z nowych pomysłów, uzyskać superwęzły o złożoności 10, 11 i 12. Ale liczba 13 pozostaje nie do pokonania. Może liczba 12 jest największą trudnością superwęzła?

Rozwiązanie superwęzła

Dostarczanie rysunków tak trudnych zagadek jak superwęzły i nie zdradzanie ich tajemnic byłoby zbyt okrutne nawet dla ekspertów od łamigłówek. Rozwiązanie superwęzłów podamy w zwartej, algebraicznej formie.

Przed demontażem bierzemy puzzle i układamy je tak, aby numery części odpowiadały rysunkowi 1. Kolejność demontażu zapisuje się jako kombinację cyfr i liter. Cyfry oznaczają numery prętów, litery wskazują kierunek ruchu zgodnie z układem współrzędnych pokazanym na rysunkach 3 i 4. Linia nad literą oznacza ruch w kierunku ujemnym osi współrzędnych. Jednym z kroków jest przesunięcie bloku o 1/2 jego szerokości. Gdy klocek porusza się o dwa kroki na raz, jego ruch zapisuje się w nawiasach z wykładnikiem 2. Jeżeli jednocześnie porusza się kilka sczepionych ze sobą części, to ich numery podaje się w nawiasach, np. (1, 3, 6) x . Oddzielenie klocka od układanki jest oznaczone pionową strzałką.

Podajmy teraz przykłady najlepszych superwęzłów.

Zagadka W. Cutlera („Cierń Billa”)

Składa się z części 1, 2, 3, 4, 5, 6, pokazanych na rysunku 3. Podano tam również algorytm jego rozwiązania. Co ciekawe, czasopismo „Scientific American” (1985, nr 10) podaje inną wersję tej zagadki i donosi, że „Cierń Billa” ma unikalne rozwiązanie. Różnica między opcjami dotyczy tylko jednego bloku: części 2 i 2 B na rysunku 3.

Ryż. 3 „Bill's Thorn”, opracowany przy użyciu komputera.

Ze względu na to, że część 2 B zawiera mniej nacięć niż część 2, nie ma możliwości włożenia jej w „cierń Billa” przy pomocy algorytmu pokazanego na rysunku 3. Pozostaje założyć, że zagadka z „Scientific American” jest składana w inny sposób.

Jeśli tak się stanie i złożymy to, to następnie możemy zastąpić część 2 B częścią 2, ponieważ ta ostatnia zajmuje mniej objętości niż 2 B. W rezultacie otrzymamy drugie rozwiązanie zagadki. Ale „Cierń Billa” ma unikalne rozwiązanie i z naszej sprzeczności można wyciągnąć tylko jeden wniosek: w drugiej wersji wystąpił błąd w rysunku.

Podobny błąd popełniono w innej publikacji (J. Slocum, J. Botermans „Puzzle stare i nowe”, 1986), ale w innym bloku (szczegół 6 C na ryc. 3). Jak to było z czytelnikami, którzy próbowali i być może nadal próbują rozwiązać te zagadki?