Das tägliche Brett ist sieben Kacheln breit und sieben Kacheln hoch. Es wirkt klein. Dann zählen Sie, auf wie viele Arten es gedreht werden kann, und die Zahl wirkt überhaupt nicht mehr klein.
Auf Englisch verfasst und redigiert. Diese deutsche Fassung wurde maschinell übersetzt; wo es auf Genauigkeit ankommt, ist das englische Original maßgeblich. Das englische Original lesen →
Jede Kachel in Conduit hat vier mögliche Orientierungen, gedreht um null, eine, zwei oder drei Viertelumdrehungen gegenüber der Lage, in der sie liegt. 1 Geben Sie jedem der neunundvierzig Felder im täglichen Raster eine unabhängige Wahl zwischen diesen vier, und die Anzahl der unterscheidbaren Brettzustände beträgt 449. Ausgeschrieben sind das 316.912.650.057.057.350.374.175.801.344, über dreihundert Quadrilliarden Konfigurationen, von denen das Spiel Sie bittet, eine zu finden, die vollständig erhellt und leckfrei ist.
Das Mischen, das Ihnen ein Rätsel vorlegt, wählt für jede Kachel eine zufällige Anzahl von Viertelumdrehungen zwischen null und drei. 1 Das Brett, auf das Sie treffen, wird also gleichverteilt aus diesem enormen Raum gezogen, abzüglich einer einzigen sorgfältigen Ausnahme, mit der das Spiel vermeidet, Ihnen ein bereits gelöstes Raster auszuteilen. 1 Brute Force ist vom Tisch: Die spieleigenen Tests halten fest, dass das Durchprobieren aller vier Drehungen jeder Kachel exponentiell ist, und sie lassen die erschöpfende Suche nur auf Miniaturbrettern mit höchstens neun Feldern laufen. 2
Diese Schlagzeilenzahl zählt zu viel, weil es manchen Kacheln gleichgültig ist, wie Sie sie drehen. Ein Kreuz, mit Anschlüssen an allen vier Seiten, sieht in allen vier Orientierungen identisch aus; es zu drehen ändert nichts. Ein gerades Stück hat nur zwei unterscheidbare Erscheinungsbilder, waagerecht und senkrecht, weil eine halbe Umdrehung es auf sich selbst abbildet. Nur die asymmetrischen Formen, das Winkelstück, das T-Stück und das Endstück mit einem einzigen Anschluss, haben wirklich vier unterscheidbare Orientierungen. 3
| Form | Anschlüsse | Unterscheidbare Drehungen | Symmetrie |
|---|---|---|---|
| Endstück (Knoten/Lampe) | 1 | 4 | keine |
| Gerades Stück | 2 | 2 | halbe Umdrehung |
| Winkelstück | 2 | 4 | keine |
| T-Stück | 3 | 4 | keine |
| Kreuz | 4 | 1 | vollständig |
Die Formen sind in den Designnotizen des Spiels benannt; die Zahlen der unterscheidbaren Orientierungen ergeben sich daraus, dass die Vier-Bit-Anschlussmaske unter den aufgeführten Drehungen unverändert bleibt. 3 Der effektive Suchraum ist um genau das Produkt dieser Symmetrien pro Kachel kleiner als 449, auf jedem Brett mit einem gesunden Mix aus Winkel- und T-Stücken aber immer noch astronomisch groß.
Drehen Sie die Frage um. Vergessen Sie die Orientierungen, die Sie ausprobieren könnten; fragen Sie, wie viele gelöste Bretter überhaupt möglich sind. Ein fertiges Conduit-Raster ist ein Leitungsgeflecht, das zusammenhängend ist, in dem der Strom jede Kachel erreicht und das keine verschwendete Schleife enthält, denn der Generator baut einen Spannbaum: zusammenhängend, kreisfrei, ein Pfad von der Quelle zu jedem Knoten. 3 Jede solche Verkabelung ist, genau genommen, ein Spannbaum des Gittergraphen, dessen Knoten die Felder sind und dessen Kanten die gemeinsamen Grenzen, die eine Leitung überbrücken kann.
Und Spannbäume lassen sich exakt zählen. Kirchhoffs Matrix-Gerüst-Satz, ein Ergebnis aus dem Jahr 1847, besagt, dass die Anzahl der Spannbäume eines beliebigen Graphen gleich jedem Kofaktor seiner Laplace-Matrix ist, einer Determinante, die sich in Polynomialzeit berechnen lässt. 4 Bei Gittern explodiert die Anzahl mit der Größe: Ein bescheidenes 4×4-Gitter hat bereits 100.352 Spannbäume, und von dort klettert die Zahl unerbittlich weiter. Jeder einzelne davon ist eine legitime, vollständig erhellte Conduit-Lösung. Das Rätsel ist nicht deshalb schwer, weil Antworten rar wären, sondern weil sie sich in einer weit größeren Menge von Beinahe-Antworten verstecken.
Die gelösten Zustände sind zählbar und zahlreich; die gemischten Zustände sind zählbar und weitaus zahlreicher. Lösen ist die Suche nach einer Nadel, von der Sie wissen, dass es sie gibt, weil das Spiel sie absichtlich dort versteckt hat.
Sie könnten hoffen, dass sich das Rätsel zerlegen lässt: Fixieren Sie die Kachel oben links, dann die daneben, und marschieren Sie ordentlich bis in die gegenüberliegende Ecke. Manchmal gibt ein Abschnitt des Bretts dem tatsächlich nach. Eine Kachel in einer Ecke hat nur zwei Kanten, die Nachbarn berühren, ihre Anschlüsse sind also stark eingeschränkt; eine Endkachel am Rand kann nur nach innen zeigen. Diese erzwungenen Züge bieten Halt.
Aber die beiden Siegbedingungen verketten sich nicht so bereitwillig. Leckfrei ist eine lokale Eigenschaft, die Sie Kante für Kante prüfen können. Unter Strom ist keine: Ob eine Kachel erhellt ist, hängt von einer ununterbrochenen Kette von Verbindungen ab, die den ganzen Weg zurück zur Quelle führt, womöglich über das gesamte Brett. 3 Eine Änderung, die Sie in einer Ecke vornehmen, kann eine entfernte Region in Dunkelheit stürzen, indem sie den einzigen Pfad kappt, der sie versorgt hat. Diese Kopplung, bei der das Schicksal jeder Kachel potenziell an eine Route durch das ganze Raster gebunden ist, bewahrt ein Drehrätsel davor, in einfache Buchhaltung zu zerfallen, und sie ist der Grund, warum Löser für die breitere Net/Pipes-Familie (Rohrdreh-Rätsel) auf Constraint-Propagation und Suche setzen statt auf einen simplen Durchlauf von links nach rechts. 5
Bei aller Weite des Zustandsraums ist die Größe, nach der Conduit Sie bewertet, winzig und menschlich: wie oft Sie getippt haben. Die Punkte betragen 1000 − 4 × Züge − 2 × Sekunden, nach unten bei null begrenzt. 3 Für jedes Brett gibt es eine theoretische Mindestzahl an Drehungen, die Summe der wenigsten Viertelumdrehungen über alle Kacheln, die nötig sind, um eine gelöste Orientierung zu erreichen, und jede darüber hinaus verschwendete Drehung kostet Sie vier Punkte, jede untätige Sekunde zwei.
Das eigentliche Spiel liegt also zwischen zwei gewaltigen Tatsachen und einer kleinen. Der Heuhaufen ist 449 Orientierungen breit; die Nadeln sind die vielen Spannbäume des Rasters; und Ihre Aufgabe ist es, mit so wenigen Ausführungen des einzigen erlaubten Zuges wie möglich vom einen zum anderen zu gelangen. Die Kombinatorik garantiert, dass eine Antwort darin steckt. Die Wertung fordert Sie leise heraus, sie zu finden, ohne umherzuirren. 4