Menghitung Berapa Banyak Cara Sebuah Grid Bisa Menyala

Empat pangkat empat puluh sembilan

Setiap ubin dalam Conduit memiliki empat orientasi yang mungkin, diputar nol, satu, dua, atau tiga seperempat putaran dari posisi semulanya. ¹ Beri setiap sel dari empat puluh sembilan sel pada grid harian pilihan bebas di antara keempatnya, dan jumlah keadaan papan yang berbeda adalah 4⁴⁹. Jika dituliskan, itu adalah 316.912.650.057.057.350.374.175.801.344, lebih dari tiga ratus oktiliun konfigurasi, dan dari sekian banyak itu permainan meminta Anda menemukan satu yang menyala seluruhnya dan bebas kebocoran.

Pengacakan yang menyodorkan teka-teki kepada Anda memilih, untuk setiap ubin, sejumlah acak seperempat putaran dari nol hingga tiga. ¹ Jadi papan yang Anda hadapi diambil secara seragam dari ruang yang sangat besar itu, dikurangi satu pengecualian cermat yang dibuat permainan agar Anda tidak diberi grid yang sudah terpecahkan. ¹ Cara paksa (brute force) tidak bisa diandalkan: pengujian permainan itu sendiri mencatat bahwa mencoba keempat rotasi dari setiap ubin bersifat eksponensial, dan pencarian menyeluruh hanya pernah dijalankan pada papan mainan berukuran sembilan sel atau kurang. ²

Simetri diam-diam memperkecil hitungannya

Angka utama itu menghitung berlebih, karena sebagian ubin tidak peduli bagaimana Anda memutarnya. Ubin silang, dengan konektor di keempat sisinya, tampak identik dalam keempat orientasi; memutarnya tidak mengubah apa pun. Ubin lurus hanya punya dua rupa yang berbeda, mendatar dan tegak, karena setengah putaran memetakannya ke dirinya sendiri. Hanya bentuk-bentuk yang tidak simetris, yaitu ubin siku, ubin T, dan ubin ujung berkonektor tunggal, yang benar-benar memiliki empat orientasi berbeda. ³

Bentuk-bentuk itu diberi nama dalam catatan desain permainan; jumlah orientasi berbeda mengikuti dari mask konektor empat-bit yang tidak berubah di bawah rotasi-rotasi yang tercantum. ³ Ruang pencarian efektif lebih kecil daripada 4⁴⁹ tepat sebesar hasil kali simetri per ubin ini, tetapi pada papan mana pun dengan campuran ubin siku dan ubin T yang cukup banyak, ruang itu masih sangat besar secara astronomis.

Berapa banyak rangkaian terpecahkan yang sebenarnya ada?

Balikkan pertanyaannya. Lupakan orientasi-orientasi yang mungkin Anda coba; tanyakan berapa banyak papan terpecahkan yang mungkin ada sejak awal. Grid Conduit yang selesai adalah sekumpulan pipa yang tersambung, daya mencapai setiap ubin, dan tidak memiliki lingkaran sia-sia, karena pohon rentang (spanning tree) adalah apa yang dibangun oleh generator: tersambung, tanpa siklus, satu jalur dari sumber ke setiap node. ³ Setiap rangkaian semacam itu, tepatnya, adalah pohon rentang dari graf grid, dengan simpul-simpulnya adalah sel dan sisi-sisinya adalah batas bersama yang dapat dijembatani oleh pipa.

Dan pohon rentang dapat dihitung secara eksak. Teorema matriks-pohon Kirchhoff, sebuah hasil dari tahun 1847, menyatakan bahwa jumlah pohon rentang dari graf mana pun sama dengan kofaktor mana pun dari matriks Laplacian-nya, sebuah determinan yang dapat Anda hitung dalam waktu polinomial. ⁴ Untuk grid, jumlahnya meledak seiring ukuran: kisi 4×4 yang sederhana saja sudah memiliki 100.352 pohon rentang, dan angkanya naik dengan ganas dari sana. Setiap satu di antaranya adalah solusi Conduit yang sah dan menyala seluruhnya. Teka-teki ini sulit bukan karena jawabannya langka, melainkan karena jawaban-jawaban itu tersembunyi di antara kerumunan hampir-jawaban yang jauh lebih besar.

Aturan lokal, akibat global

Anda mungkin berharap teka-teki ini bisa diurai: bereskan ubin kiri atas, lalu ubin di sebelahnya, dan melangkah rapi hingga ke sudut terjauh. Kadang-kadang sebagian papan memang tunduk pada cara itu. Ubin di sudut hanya memiliki dua sisi yang menyentuh tetangganya, sehingga konektornya sangat terbatas; ubin ujung di tepi papan hanya bisa menghadap ke dalam. Langkah-langkah yang terpaksa ini memberikan pijakan.

Namun kedua syarat kemenangan itu tidak berantai semudah itu. Bebas kebocoran adalah sifat lokal, Anda dapat memeriksanya sisi demi sisi. Teraliri daya tidak begitu: apakah sebuah ubin menyala bergantung pada rantai sambungan yang tak terputus sepanjang jalan kembali ke sumber, mungkin melintasi seluruh papan. ³ Perubahan yang Anda buat di satu sudut dapat menjerumuskan wilayah yang jauh ke dalam kegelapan dengan memutus satu-satunya jalur yang mengalirinya. Keterkaitan itu, nasib setiap ubin yang berpotensi terikat pada rute melintasi seluruh grid, adalah yang mencegah teka-teki rotasi runtuh menjadi pembukuan yang mudah, dan itulah sebabnya pemecah untuk keluarga teka-teki Net/Pipes yang lebih luas mengandalkan propagasi kendala dan pencarian alih-alih sapuan sederhana dari kiri ke kanan. ⁵

Bukan keadaannya, melainkan putarannya

Betapa pun luasnya ruang keadaan, besaran yang dinilai Conduit dari Anda kecil dan manusiawi: berapa kali Anda mengetuk. Skornya adalah 1000 − 4 × langkah − 2 × detik, dengan batas bawah nol. ³ Ada jumlah rotasi minimum teoretis untuk papan mana pun, yaitu jumlah, atas semua ubin, seperempat putaran tersedikit yang diperlukan untuk mencapai orientasi terpecahkan, dan setiap putaran sia-sia melebihi itu merugikan Anda empat poin, setiap detik menganggur dua poin.

Jadi permainan yang sebenarnya berada di antara dua fakta raksasa dan satu fakta kecil. Tumpukan jeraminya selebar 4⁴⁹ orientasi; jarum-jarumnya adalah banyaknya pohon rentang dari grid; dan tugas Anda adalah bepergian dari yang satu ke yang lain dengan sesedikit mungkin satu-satunya langkah yang diperbolehkan. Kombinatorika menjamin ada jawaban di dalamnya. Penilaian diam-diam menantang Anda menemukannya tanpa berkeliaran. ⁴