Natychmiastowe szaleństwo

Łamigłówka Instant Insanity w konfiguracji „rozwiązanej”. Od góry do dołu, kolory z tyłu kostek to biały, zielony, niebieski i czerwony (lewa strona) oraz niebieski, czerwony, zielony i biały (prawa strona)

Sieci kostek Instant Insanity – styl linii służy do identyfikacji kostek w rozwiązaniu

Instant Insanity to nazwa nadana przez Parker Brothers ich wersji układanki z 1967 roku, która istnieje od starożytności i która była sprzedawana przez wielu twórców zabawek i puzzli pod różnymi nazwami, w tym: Devil's Dice ( Pressman ); DamBlocks (Schaper); Logi-Qubes (Schaeffer); Kostki Logi (ThinkinGames); Daffy Dots (Reiss); Te bloki (Austin); PsykoNosis (Pomysły od A do Z) i wiele innych.

Układanka składa się z czterech kostek ze ścianami pokolorowanymi czterema kolorami (powszechnie czerwonym, niebieskim, zielonym i białym). Celem układanki jest ułożenie tych kostek w kolumnie tak, aby każda strona stosu (przód, tył, lewa i prawa) przedstawiała każdy z czterech kolorów. Rozkład kolorów na każdej kostce jest wyjątkowy.

Ten problem ma teorię grafów rozwiązanie, w którym graf z czterema wierzchołkami oznaczonymi jako B, G, R, W (dla koloru niebieskiego, zielonego, czerwonego i białego) może być użyty do przedstawienia każdego sześcianu; istnieje krawędź między dwoma wierzchołkami, jeśli dwa kolory znajdują się po przeciwnych stronach sześcianu, oraz pętla w wierzchołku, jeśli przeciwległe boki mają ten sam kolor. Metoda prób i błędów to powolny sposób rozwiązania tego problemu, ponieważ istnieje 331 776 możliwych układów czterech sześcianów (6 ścian, 4 obroty = 24 pozycje każdego sześcianu, razy cztery sześciany, w sumie 331 776). A rozwiązanie jest symetryczne na 8 sposobów (jeśli masz rozwiązanie i obrócisz wszystkie cztery sześciany do przodu, masz inne prawidłowe rozwiązanie. Możesz wykonać ten ruch pomnożony przez obrót każdego sześcianu o 180 stopni wokół jego pionowej osi , co daje w sumie 8 symetrii), więc szanse wynoszą 331 776 podzielone przez 8, co równa się 41 472 szansom losowego wrzucenia kostek do roztworu. Układanka jest badana przez DE Knuth w artykule na temat szacowania czasu trwania wyczerpujących procedur przeszukiwania ze śledzeniem wstecznym.

Każdą pozycję układanki można rozwiązać w ośmiu ruchach lub mniej.

Pierwsza znana opatentowana wersja układanki została stworzona przez Fredericka A. Schossowa w 1900 roku i sprzedawana jako układanka Katzenjammer . Układanka została odtworzona przez Franza Owena Armbrustera, znanego również jako Frank Armbruster, i niezależnie opublikowana przez Parker Brothers i Pressman w 1967 roku. Tylko Parker Brothers sprzedało ponad 12 milionów puzzli. Układanka jest podobna lub identyczna z wieloma innymi układankami (np. The Great Tantalizer , około 1940 r. i najpopularniejsza nazwa przed Instant Insanity ).

Jedna wersja układanki jest obecnie sprzedawana przez Winning Moves Games USA.

Rozwiązanie

Wykres przeciwległych ścian sześcianów, style linii odpowiadające sześcianom na powyższym obrazie ich sieci

Biorąc pod uwagę już pokolorowane kostki i cztery różne kolory (czerwony, zielony, niebieski, biały), spróbujemy wygenerować wykres, który da jasny obraz wszystkich pozycji kolorów we wszystkich kostkach. Wynikowy graf będzie zawierał cztery wierzchołki, po jednym dla każdego koloru, a każdą krawędź ponumerujemy od jednego do czterech (jedna liczba dla każdego sześcianu). Jeśli krawędź łączy dwa wierzchołki (Czerwony i Zielony), a liczba krawędzi wynosi trzy, oznacza to, że trzeci sześcian ma przeciwległe ściany Czerwone i Zielone.

Aby znaleźć rozwiązanie tego problemu, potrzebujemy ułożenia czterech ścian każdego z sześcianów. Aby przedstawić informacje o dwóch przeciwległych ścianach wszystkich czterech sześcianów, potrzebujemy skierowanego podgrafu zamiast nieskierowanego, ponieważ dwa kierunki mogą reprezentować tylko dwie przeciwległe ściany, ale nie to, czy ściana powinna znajdować się z przodu, czy z tyłu.

Więc jeśli mamy dwa skierowane podgrafy, możemy właściwie przedstawić wszystkie cztery ściany (które mają znaczenie) wszystkich czterech sześcianów.

• Pierwszy graf skierowany będzie reprezentował przednią i tylną ścianę.
• Drugi skierowany wykres będzie reprezentował lewą i prawą ścianę.

Nie możemy losowo wybrać dwóch podgrafów - jakie są więc kryteria wyboru?

Musimy wybrać grafy takie, że:

1. dwa podgrafy nie mają wspólnych krawędzi, ponieważ jeśli istnieje krawędź, która jest wspólna, oznacza to, że co najmniej jeden sześcian ma parę przeciwległych ścian dokładnie tego samego koloru, to znaczy, jeśli sześcian ma czerwony i niebieski jako przód i tylnej, to samo dotyczy lewej i prawej strony.
2. podgraf zawiera tylko jedną krawędź z każdego sześcianu, ponieważ podgraf musi uwzględniać wszystkie sześciany, a jedna krawędź może całkowicie reprezentować parę przeciwległych ścian.
3. podgraf może zawierać tylko wierzchołki stopnia drugiego, ponieważ stopień dwa oznacza, że ​​kolor może występować tylko na ścianach dwóch sześcianów. Łatwym sposobem na zrozumienie jest to, że istnieje osiem twarzy, które należy równo podzielić na cztery kolory. Czyli po dwa na kolor.

Po zrozumieniu tych ograniczeń, jeśli spróbujemy wyprowadzić dwa wykresy podrzędne, możemy otrzymać jeden możliwy zestaw, jak pokazano na rysunku 3. Każdy styl linii krawędzi reprezentuje sześcian.

Odwzorowanie krawędzi dwóch skierowanych podgrafów na lewą (L) i prawą (R) oraz przednią (F) i tylną (B) ścianę rozwiązuje zagadkę

Górny podwykres pozwala wyprowadzić kolory lewej i prawej ściany odpowiedniego sześcianu. Np:

1. Ciągła strzałka od czerwonego do zielonego mówi, że pierwsza kostka będzie miała czerwoną po lewej stronie i zieloną po prawej.
2. Przerywana strzałka od niebieskiego do czerwonego oznacza, że ​​drugi sześcian będzie miał niebieski po lewej stronie i czerwony po prawej.
3. Kropkowana strzałka od Białego do Niebieskiego mówi, że trzeci sześcian będzie miał Biały po lewej stronie i Niebieski po prawej.
4. Strzałka przerywana od zielonego do białego mówi, że czwarty sześcian będzie miał zielony po lewej stronie i biały po prawej.

Dolny podwykres pozwala wyprowadzić kolory przedniej i tylnej ściany odpowiedniego sześcianu. Np:

1. Ciągła strzałka od Białego do Niebieskiego mówi, że pierwsza kostka będzie miała Białe z przodu i Niebieskie z tyłu.
2. Przerywana strzałka od Zielonego do Białego mówi, że drugi sześcian będzie miał Zielony z przodu i Biały z tyłu.
3. Kropkowana strzałka od niebieskiego do czerwonego mówi, że trzeci sześcian będzie miał niebieski z przodu i czerwony z tyłu.
4. Strzałka przerywana od czerwonego do zielonego mówi, że czwarta kostka będzie miała czerwoną z przodu i zieloną z tyłu.

Trzeci obraz przedstawia pochodny stos sześcianu, który jest rozwiązaniem problemu.

To ważne by zauważyć że:

1. Możesz dowolnie oznaczyć kostki, ponieważ jedno takie rozwiązanie wyrenderuje 23 więcej, zamieniając pozycje kostek, ale nie zmieniając ich konfiguracji.
2. Dwa skierowane podgrafy mogą reprezentować zamiennie od przodu do tyłu i od lewej do prawej, tj. jeden z nich może przedstawiać od przodu do tyłu lub od lewej do prawej. Dzieje się tak, ponieważ jedno takie rozwiązanie renderuje również 3 więcej po prostu obracając. Dodając efekt w 1., generujemy 95 kolejnych rozwiązań, dostarczając tylko jedno. Patrząc z perspektywy, takie cztery kostki mogą wygenerować 24 ³ × 3 = 41472 konfiguracji.
3. Nie jest ważne, aby zwracać uwagę na górę i dół stosu kostek.

Uogólnienia

Biorąc pod uwagę n sześcianów, ze ścianami każdego sześcianu pokolorowanymi jednym z n kolorów, ustalenie, czy możliwe jest ułożenie kostek w taki sposób, aby każdy kolor pojawił się dokładnie raz na każdej z 4 ścian stosu, jest NP- zupełne .

Gra polegająca na układaniu kostek to dwuosobowa wersja tej układanki. Mając uporządkowaną listę kostek, gracze na zmianę dodają następną kostkę na wierzch rosnącego stosu kostek. Przegrany jest pierwszym graczem, który doda kostkę, która powoduje, że jeden z czterech boków stosu ma kolor powtórzony więcej niż jeden raz. Robertson i Munro udowodnili, że ta gra jest PSPACE-zupełna , co ilustruje obserwację, że NP-zupełne łamigłówki zwykle prowadzą do gier PSPACE-zupełnych.

•   Slocum; Botermans (1987), Stare i nowe zagadki , Seattle: University of Washington Press, s. 38, ISBN 0-295-96579-7