Codzienna plansza ma siedem płytek szerokości i siedem wysokości. Wygląda na małą. Potem liczysz, na ile sposobów można ją poobracać, i liczba przestaje wyglądać na małą.
Napisane i zredagowane po angielsku. Ta polska wersja powstała w wyniku tłumaczenia maszynowego; tam, gdzie liczy się precyzja, rozstrzygający jest angielski oryginał. Przeczytaj oryginał po angielsku →
Każda płytka w Conduit ma cztery możliwe orientacje: obróconą o zero, jeden, dwa lub trzy ćwierćobroty względem położenia wyjściowego. 1 Daj każdej z czterdziestu dziewięciu komórek codziennej siatki niezależny wybór spośród tych czterech, a liczba różnych stanów planszy wyniesie 449. Zapisana w całości, to 316 912 650 057 057 350 374 175 801 344, ponad trzysta kwadryliardów konfiguracji, wśród których gra prosi cię o znalezienie jednej: w pełni oświetlonej i szczelnej.
Tasowanie, które wręcza ci łamigłówkę, wybiera dla każdej płytki losową liczbę ćwierćobrotów od zera do trzech. 1 Plansza, którą zastajesz, jest więc losowana jednostajnie z tej ogromnej przestrzeni, z jednym ostrożnym wyjątkiem, jaki gra robi, by nie podsunąć ci siatki już rozwiązanej. 1 Siłowe przeszukiwanie odpada: własne testy gry odnotowują, że wypróbowanie wszystkich czterech obrotów każdej płytki ma złożoność wykładniczą, i uruchamiają wyczerpujące przeszukiwanie wyłącznie na zabawkowych planszach o dziewięciu komórkach lub mniejszych. 2
Ta nagłówkowa liczba zawyża wynik, bo niektórym płytkom jest obojętne, jak je obrócisz. Krzyż, ze złączami na wszystkich czterech bokach, wygląda identycznie w każdej z czterech orientacji; obracanie go niczego nie zmienia. Prosta ma tylko dwa różne wyglądy, poziomy i pionowy, bo półobrót przenosi ją na nią samą. Tylko kształty niesymetryczne, kolanko, trójnik i końcówka z jednym złączem, naprawdę mają cztery różne orientacje. 3
| Kształt | Złącza | Różne obroty | Symetria |
|---|---|---|---|
| Końcówka (węzeł/żarówka) | 1 | 4 | brak |
| Prosta | 2 | 2 | półobrót |
| Kolanko | 2 | 4 | brak |
| Trójnik | 3 | 4 | brak |
| Krzyż | 4 | 1 | pełna |
Kształty noszą nazwy nadane w notatkach projektowych gry; liczby różnych orientacji wynikają z tego, że czterobitowa maska złączy pozostaje niezmieniona przy wymienionych obrotach. 3 Efektywna przestrzeń przeszukiwania jest mniejsza od 449 dokładnie o iloczyn tych symetrii poszczególnych płytek, ale na każdej planszy ze zdrową mieszanką kolanek i trójników wciąż jest astronomicznie wielka.
Odwróć pytanie. Zapomnij o orientacjach, które można by wypróbować; zapytaj, ile w ogóle jest możliwych plansz rozwiązanych. Ukończona siatka Conduit to zestaw rur, który jest spójny, zasilanie dociera do każdej płytki i nie ma w nim żadnej zbędnej pętli, bo generator buduje właśnie drzewo rozpinające: spójne, acykliczne, z jedną ścieżką od źródła do każdego węzła. 3 Każde takie okablowanie jest, ściśle rzecz biorąc, drzewem rozpinającym grafu siatki, w którym wierzchołkami są komórki, a krawędziami wspólne granice, przez które rura może przejść.
A drzewa rozpinające da się policzyć dokładnie. Twierdzenie Kirchhoffa o macierzy i drzewach, wynik z 1847 roku, mówi, że liczba drzew rozpinających dowolnego grafu równa się dowolnemu dopełnieniu algebraicznemu jego macierzy Laplace'a, wyznacznikowi, który można obliczyć w czasie wielomianowym. 4 Dla siatek liczba ta eksploduje wraz z rozmiarem: skromna krata 4×4 ma już 100 352 drzewa rozpinające, a dalej liczba rośnie zawrotnie. Każde z nich to prawomocne, w pełni oświetlone rozwiązanie Conduit. Łamigłówka jest trudna nie dlatego, że odpowiedzi jest mało, lecz dlatego, że kryją się w znacznie liczniejszym tłumie prawie-odpowiedzi.
Stany rozwiązane są policzalne i liczne; stany potasowane są policzalne i nieporównanie liczniejsze. Rozwiązywanie to poszukiwanie igły, o której wiesz, że istnieje, bo gra schowała ją tam celowo.
Można by mieć nadzieję, że łamigłówka rozkłada się na części: ustaw lewy górny róg, potem płytkę obok i maszeruj równo do przeciwległego narożnika. Czasem jakiś fragment planszy rzeczywiście się temu poddaje. Płytka w narożniku ma tylko dwie krawędzie stykające się z sąsiadami, więc jej złącza są mocno ograniczone; końcówka na brzegu może wskazywać tylko do środka. Te wymuszone ruchy dają punkty zaczepienia.
Ale dwa warunki wygranej nie układają się w łańcuch tak usłużnie. Szczelność to własność lokalna, można ją sprawdzić krawędź po krawędzi. Zasilanie już nie: to, czy płytka świeci, zależy od nieprzerwanego łańcucha połączeń biegnącego aż do źródła, być może przez całą planszę. 3 Zmiana, którą robisz w jednym rogu, może pogrążyć odległy obszar w ciemności, przerywając jedyną ścieżkę, która go zasilała. To sprzężenie, los każdej płytki potencjalnie związany z trasą przez całą siatkę, sprawia, że łamigłówka obrotowa nie sprowadza się do prostej buchalterii, i dlatego programy rozwiązujące szerszą rodzinę łamigłówek Net/Pipes (sieci rur) opierają się na propagacji ograniczeń i przeszukiwaniu, a nie na zwykłym przejściu od lewej do prawej. 5
Mimo całego ogromu przestrzeni stanów wielkość, z której Conduit cię ocenia, jest malutka i ludzka: ile razy stukasz. Wynik to 1000 − 4 × ruchy − 2 × sekundy, obcięty od dołu do zera. 3 Dla każdej planszy istnieje teoretyczne minimum liczby obrotów, suma po wszystkich płytkach najmniejszej liczby ćwierćobrotów potrzebnych do osiągnięcia rozwiązanej orientacji, i każde zbędne obrócenie ponad nie kosztuje cię cztery punkty, a każda bezczynna sekunda dwa.
Prawdziwa gra toczy się więc między dwoma ogromnymi faktami a jednym małym. Stóg siana ma 449 orientacji szerokości; igłami są liczne drzewa rozpinające siatki; a twoim zadaniem jest przejść od jednego do drugich, wykonując jak najmniej jedynego dozwolonego ruchu. Kombinatoryka gwarantuje, że odpowiedź tam jest. Punktacja po cichu rzuca ci wyzwanie: znajdź ją, nie błądząc. 4