Pagbibilang ng mga Paraan Kung Paano Maaaring Magliwanag ang Isang Grid

Apat na itinaas sa apatnapu't siyam

Ang bawat tile sa Conduit ay may apat na posibleng oryentasyon, na pinaikot nang zero, isa, dalawa o tatlong quarter-turn mula sa kinalalagyan nito. ¹ Bigyan ang bawat isa sa apatnapu't siyam na cell sa pang-araw-araw na grid ng malayang pagpili sa apat na iyon, at ang bilang ng magkakaibang estado ng board ay 4⁴⁹. Kung isusulat nang buo, iyon ay 316,912,650,057,057,350,374,175,801,344, mahigit tatlong daang octillion na configuration, at hinihiling sa iyo ng laro na hanapin mula sa mga iyon ang isa na ganap na naiilawan at walang tagas.

Ang scramble na nag-aabot sa iyo ng puzzle ay pumipili, para sa bawat tile, ng random na bilang ng quarter-turn mula zero hanggang tatlo. ¹ Kaya ang board na masasalubong mo ay hinuhugot nang pantay-pantay mula sa napakalawak na espasyong iyon, bawas ang isang maingat na eksepsiyon na ginagawa ng laro upang hindi ka maabutan ng grid na nalutas na. ¹ Wala sa usapan ang brute force: sinasabi ng sariling mga test ng laro na ang pagsubok sa lahat ng apat na pag-ikot ng bawat tile ay exponential, at pinapatakbo lamang nila ang exhaustive search sa maliliit na board na siyam na cell o mas kaunti. ²

Tahimik na pinaliliit ng simetriya ang bilang

Sobra ang bilang na iyon sa headline, dahil may mga tile na walang pakialam kung paano mo sila paikutin. Ang krus, na may connector sa lahat ng apat na gilid, ay magkakamukha sa lahat ng apat na oryentasyon; walang nababago sa pag-ikot nito. Ang tuwid na linya ay may dalawang magkaibang anyo lamang, pahalang at patayo, dahil ibinabalik ito ng kalahating ikot sa sarili nito. Tanging ang mga hugis na hindi simetriko, ang siko, ang tee, at ang dulo na may iisang connector, ang tunay na may apat na magkakaibang oryentasyon. ³

Pinangalanan ang mga hugis sa mga design note ng laro; ang bilang ng magkakaibang oryentasyon ay sumusunod mula sa four-bit connector mask na hindi nagbabago sa ilalim ng mga nakalistang pag-ikot. ³ Ang epektibong search space ay mas maliit kaysa 4⁴⁹ nang eksaktong katumbas ng produkto ng mga simetriyang ito sa bawat tile, ngunit sa anumang board na may sapat na halo ng mga siko at tee, napakalaki pa rin nito nang astronomikal.

Ilang nalutas na wiring ba talaga ang umiiral?

Baligtarin ang tanong. Kalimutan ang mga oryentasyong maaari mong subukan; itanong kung ilang nalutas na board ang posible sa simula pa lang. Ang natapos na Conduit grid ay isang set ng tubo na magkakakonekta, naaabot ng kuryente ang bawat tile, at walang sayang na loop, dahil spanning tree ang binubuo ng generator: konektado, walang cycle, iisang landas mula sa pinagmulan patungo sa bawat node. ³ Ang bawat ganitong wiring ay, sa eksaktong kahulugan, isang spanning tree ng grid graph, kung saan ang mga vertex ay ang mga cell at ang mga edge ay ang mga magkasalong hangganan na maaaring tulayin ng tubo.

At maaaring bilangin nang eksakto ang mga spanning tree. Ayon sa matrix-tree theorem ni Kirchhoff, isang resulta mula 1847, ang bilang ng spanning tree ng anumang graph ay katumbas ng alinmang cofactor ng Laplacian matrix nito, isang determinant na maaaring kalkulahin sa polynomial time. ⁴ Para sa mga grid, sumasabog ang bilang habang lumalaki: ang isang simpleng 4×4 na lattice ay mayroon nang 100,352 spanning tree, at mabilis na tumataas ang bilang mula roon. Ang bawat isa sa mga iyon ay isang lehitimo at ganap na naiilawang solusyon ng Conduit. Mahirap ang puzzle hindi dahil kakaunti ang sagot, kundi dahil nakatago ang mga ito sa mas malaking pulutong ng mga halos-sagot.

Mga lokal na patakaran, mga pangkabuuang bunga

Maaari mong asahan na mahahati-hati ang puzzle: ayusin ang kaliwang-itaas, pagkatapos ang tile sa tabi nito, at maayos na magmartsa hanggang sa malayong sulok. Kung minsan, may bahagi nga ng board na sumusuko sa ganoon. Ang tile sa sulok ay may dalawang gilid lamang na dumidikit sa mga kapitbahay, kaya lubhang limitado ang mga connector nito; ang dulong tile sa hangganan ay maaari lamang tumuro paloob. Ang mga sapilitang galaw na ito ay nagbibigay ng mga tuntungan.

Ngunit hindi ganoon kadaling magkakabit ang dalawang kondisyon ng panalo. Ang walang tagas ay isang lokal na katangian, maaari mo itong tiyakin gilid por gilid. Ang may kuryente ay hindi: kung naiilawan ang isang tile ay nakasalalay sa walang patid na kadena ng mga koneksyon na umaabot pabalik hanggang sa pinagmulan, posibleng sa kabuuan ng board. ³ Ang pagbabagong gagawin mo sa isang sulok ay maaaring maglubog sa isang malayong rehiyon sa kadiliman sa pamamagitan ng pagputol sa nag-iisang landas na nagpapakain dito. Ang ugnayang iyon, ang kapalaran ng bawat tile na posibleng nakatali sa isang ruta sa buong grid, ang pumipigil sa isang rotation puzzle na maging simpleng pagtatala lamang, at ito ang dahilan kung bakit ang mga solver para sa mas malawak na pamilya ng Net/Pipes (mga puzzle ng pag-ikot ng tubo) ay umaasa sa constraint propagation at search sa halip na sa simpleng pagsala mula kaliwa pakanan. ⁵

Hindi ang mga estado, kundi ang mga ikot

Sa kabila ng lawak ng state space, ang dami na pinagbabatayan ng Conduit sa pagmamarka sa iyo ay maliit at makatao: ilang beses kang tumapik. Ang iskor ay 1000 − 4 × galaw − 2 × segundo, na hindi bababa sa zero. ³ May teoretikal na pinakamababang bilang ng pag-ikot para sa anumang board, ang kabuuan, sa lahat ng tile, ng pinakakaunting quarter-turn na kailangan upang marating ang nalutas na oryentasyon, at ang bawat sayang na ikot na lampas dito ay nagkakahalaga sa iyo ng apat na puntos, ang bawat segundong walang ginagawa ay dalawa.

Kaya ang tunay na laro ay nakalagay sa pagitan ng dalawang napakalaking katotohanan at isang maliit. Ang bunton ng dayami ay 4⁴⁹ na oryentasyon ang lapad; ang mga karayom ay ang maraming spanning tree ng grid; at ang trabaho mo ay maglakbay mula sa isa patungo sa isa pa gamit ang pinakakaunting bilang ng nag-iisang legal na galaw na kaya mo. Ginagarantiya ng combinatorics na may sagot doon. Tahimik kang hinahamon ng pagmamarka na hanapin ito nang hindi naliligaw. ⁴