Het dagelijkse bord is zeven tegels breed en zeven tegels hoog. Het oogt klein. Dan tel je op hoeveel manieren het gedraaid kan worden, en opeens oogt het getal helemaal niet klein meer.
In het Engels geschreven en geredigeerd. Deze Nederlandse versie is met machinevertaling gemaakt; waar precisie ertoe doet, is het Engelse origineel leidend. Lees het origineel in het Engels →
Elke tegel in Conduit heeft vier mogelijke standen: nul, één, twee of drie kwartslagen gedraaid ten opzichte van hoe hij ligt. 1 Geef elk van de negenenveertig cellen op het dagelijkse rooster een onafhankelijke keuze uit die vier, en het aantal verschillende bordtoestanden is 449. Voluit geschreven is dat 316.912.650.057.057.350.374.175.801.344, meer dan driehonderd quadriljard configuraties, waarvan het spel je vraagt er één te vinden die volledig verlicht en lekvrij is.
De husseling die je een puzzel voorschotelt, kiest voor elke tegel een willekeurig aantal kwartslagen van nul tot en met drie. 1 Het bord dat je te zien krijgt, is dus uniform getrokken uit die enorme ruimte, op één zorgvuldige uitsluiting na, die het spel toepast om je geen rooster voor te leggen dat al is opgelost. 1 Brute kracht is uitgesloten: de eigen tests van het spel merken op dat het uitproberen van alle vier de rotaties van elke tegel exponentieel is, en ze draaien de uitputtende zoektocht alleen op speelgoedborden van negen cellen of minder. 2
Dat pronkgetal telt te veel, want sommige tegels trekken zich niets aan van hoe je ze draait. Een kruis, met aansluitingen aan alle vier de zijden, ziet er in alle vier de standen identiek uit; draaien verandert niets. Een recht stuk heeft maar twee verschillende aanzichten, horizontaal en verticaal, omdat een halve slag het op zichzelf afbeeldt. Alleen de asymmetrische vormen, de bocht, het T-stuk en het eindstuk met één aansluiting, hebben werkelijk vier verschillende standen. 3
| Vorm | Aansluitingen | Verschillende draaien | Symmetrie |
|---|---|---|---|
| Eindstuk (knoop/lamp) | 1 | 4 | geen |
| Recht stuk | 2 | 2 | halve slag |
| Bocht | 2 | 4 | geen |
| T-stuk | 3 | 4 | geen |
| Kruis | 4 | 1 | volledig |
De vormen worden benoemd in de ontwerpnotities van het spel; de aantallen verschillende standen volgen uit het feit dat het aansluitmasker van vier bits onder de genoemde rotaties onveranderd blijft. 3 De effectieve zoekruimte is precies het product van deze symmetrieën per tegel kleiner dan 449, maar op elk bord met een gezonde mix van bochten en T-stukken nog altijd astronomisch groot.
Draai de vraag om. Vergeet de standen die je zou kunnen proberen; vraag hoeveel opgeloste borden er überhaupt mogelijk zijn. Een voltooid Conduit-rooster is een stelsel leidingen dat samenhangend is, waarin de stroom elke tegel bereikt en dat geen overbodige lus bevat, omdat de generator een opspannende boom bouwt: samenhangend, cykelvrij, één pad van de bron naar elke knoop. 3 Elke zo'n bedrading is, precies, een opspannende boom van de roostergraaf, waarin de knopen de cellen zijn en de kanten de gedeelde grenzen die een leiding kan overbruggen.
En opspannende bomen kunnen exact geteld worden. De matrix-boomstelling van Kirchhoff, een resultaat uit 1847, zegt dat het aantal opspannende bomen van een willekeurige graaf gelijk is aan elke cofactor van zijn Laplace-matrix, een determinant die je in polynomiale tijd kunt berekenen. 4 Voor roosters explodeert het aantal met de grootte: een bescheiden 4×4-rooster heeft al 100.352 opspannende bomen, en van daaraf klimt het getal woest verder. Elk daarvan is een legitieme, volledig verlichte Conduit-oplossing. De puzzel is niet moeilijk omdat antwoorden schaars zijn, maar omdat ze verborgen zitten in een veel grotere menigte van bijna-antwoorden.
De opgeloste toestanden zijn telbaar en talrijk; de gehusselde toestanden zijn telbaar en onmetelijk talrijker. Oplossen is zoeken naar een naald waarvan je weet dat ze bestaat, omdat het spel haar daar met opzet heeft verstopt.
Je zou hopen dat de puzzel uiteenvalt: leg linksboven vast, dan de tegel ernaast, en marcheer netjes door naar de verste hoek. Soms geeft een stuk van het bord daar inderdaad aan toe. Een tegel in een hoek heeft maar twee zijden die aan buren grenzen, dus zijn aansluitingen zijn sterk ingeperkt; een eindstuk aan de rand kan alleen naar binnen wijzen. Deze gedwongen zetten bieden houvast.
Maar de twee winvoorwaarden schakelen niet zo gewillig aan elkaar. Lekvrij is een lokale eigenschap; je kunt haar zijde voor zijde controleren. Onder stroom is dat niet: of een tegel verlicht is, hangt af van een ononderbroken keten van verbindingen die helemaal terugloopt naar de bron, mogelijk dwars over het hele bord. 3 Een verandering die je in de ene hoek aanbrengt, kan een ver gebied in duisternis dompelen door het enige pad te verbreken dat het voedde. Die koppeling, het lot van elke tegel mogelijk gebonden aan een route door het hele rooster, is wat voorkomt dat een draaipuzzel ineenzakt tot simpel boekhouden, en het is de reden waarom oplossers voor de bredere Net/Pipes-familie (de puzzelfamilie waartoe Conduit behoort) leunen op constraintpropagatie en zoeken in plaats van op een simpele veeg van links naar rechts. 5
Hoe onmetelijk de toestandsruimte ook is, de grootheid waarop Conduit je beoordeelt is klein en menselijk: hoe vaak je hebt getikt. De score is 1000 − 4 × zetten − 2 × seconden, met een ondergrens van nul. 3 Voor elk gegeven bord bestaat er een theoretisch minimumaantal rotaties, de som, over alle tegels, van het kleinste aantal kwartslagen dat nodig is om een opgeloste stand te bereiken, en elke verspilde draai daarbovenop kost je vier punten, elke seconde stilstand twee.
Het echte spel zit dus tussen twee enorme feiten en één klein feit in. De hooiberg is 449 standen breed; de naalden zijn de vele opspannende bomen van het rooster; en jouw taak is om van het ene naar het andere te reizen met zo weinig mogelijk van de enige toegestane zet. De combinatoriek garandeert dat er een antwoord in zit. De puntentelling daagt je stilletjes uit het te vinden zonder te dwalen. 4