Щоденна дошка має сім плиток завширшки і сім заввишки. Вона здається маленькою. Потім ви підраховуєте, скількома способами її можна повернути, і число вже зовсім не здається маленьким.
Написано й відредаговано англійською. Цю українську версію створено машинним перекладом; там, де важлива точність, авторитетним є англійський оригінал. Читати оригінал англійською →
Кожна плитка в Conduit має чотири можливі орієнтації: повернута на нуль, один, два або три чверть-оберти від свого положення. 1 Дайте кожній із сорока дев’яти клітинок щоденної сітки незалежний вибір серед цих чотирьох, і кількість різних станів дошки становитиме 449. Записане повністю, це 316 912 650 057 057 350 374 175 801 344, понад триста октильйонів конфігурацій, серед яких гра просить вас знайти одну, повністю освітлену й без витоків.
Перемішування, яке вручає вам головоломку, обирає для кожної плитки випадкову кількість чверть-обертів від нуля до трьох. 1 Отже, дошка, яку ви бачите, вибрана рівномірно з цього величезного простору, за одним обережним винятком, який гра робить, щоб не роздати вам уже розв’язану сітку. 1 Грубий перебір відпадає: власні тести гри зазначають, що перебір усіх чотирьох поворотів кожної плитки експоненційний, і вичерпний пошук вони запускають лише на іграшкових дошках із дев’яти клітинок або менше. 2
Це заголовне число завищене, бо деяким плиткам байдуже, як ви їх повертаєте. Хрестовина, зі з’єднувачами з усіх чотирьох боків, виглядає однаково в усіх чотирьох орієнтаціях; її обертання нічого не змінює. Пряма має лише два різні вигляди, горизонтальний і вертикальний, бо півоберт переводить її саму в себе. Лише асиметричні форми, коліно, трійник і заглушка з одним з’єднувачем, справді мають усі чотири різні орієнтації. 3
| Форма | З’єднувачі | Різні повороти | Симетрія |
|---|---|---|---|
| Заглушка (вузол/лампочка) | 1 | 4 | немає |
| Пряма | 2 | 2 | півоберт |
| Коліно | 2 | 4 | немає |
| Трійник | 3 | 4 | немає |
| Хрестовина | 4 | 1 | повна |
Назви форм узято з дизайнерських нотаток гри; кількості різних орієнтацій випливають із того, що чотирибітова маска з’єднувачів не змінюється за перелічених поворотів. 3 Ефективний простір пошуку менший за 449 рівно на добуток цих симетрій окремих плиток, але на будь-якій дошці зі здоровою сумішшю колін і трійників він усе ще астрономічно великий.
Переверніть запитання. Забудьте про орієнтації, які ви могли б спробувати; запитайте, скільки розв’язаних дощок узагалі можливо. Завершена сітка Conduit — це набір труб, який з’єднаний, у якому живлення доходить до кожної плитки і немає жодної зайвої петлі, бо генератор будує саме кістякове дерево: зв’язне, ациклічне, з одним шляхом від джерела до кожного вузла. 3 Кожна така схема — це, точно кажучи, кістякове дерево графа сітки, де вершини — клітинки, а ребра — спільні межі, які може перекрити труба.
А кістякові дерева можна порахувати точно. Теорема Кірхгофа про матриці й дерева, результат 1847 року, стверджує, що кількість кістякових дерев будь-якого графа дорівнює будь-якому алгебраїчному доповненню його матриці Лапласа, визначнику, який можна обчислити за поліноміальний час. 4 Для сіток кількість вибухає зі зростанням розміру: скромна ґратка 4×4 вже має 100 352 кістякові дерева, і далі число зростає шалено. Кожне з них — законний, повністю освітлений розв’язок Conduit. Головоломка складна не тому, що відповідей мало, а тому, що вони сховані в набагато більшому натовпі майже-відповідей.
Розв’язані стани зліченні й численні; перемішані стани зліченні й незрівнянно численніші. Розв’язування — це пошук голки, про яку ви знаєте, що вона існує, бо гра сховала її там навмисно.
Можна сподіватися, що головоломка розкладається на частини: зафіксувати верхній лівий кут, потім плитку поруч, і акуратно промарширувати до дальнього кута. Іноді частина дошки справді піддається такому підходу. Плитка в куті має лише два ребра, що торкаються сусідів, тож її з’єднувачі сильно обмежені; заглушка на межі може бути спрямована лише всередину. Ці вимушені ходи дають опору.
Але дві умови перемоги не зчіплюються так люб’язно. Без витоків — це локальна властивість, її можна перевірити ребро за ребром. Під живленням — ні: чи світиться плитка, залежить від безперервного ланцюга з’єднань, що тягнеться аж до джерела, можливо через усю дошку. 3 Зміна, яку ви робите в одному куті, може занурити далеку ділянку в темряву, розірвавши єдиний шлях, що її живив. Саме цей зв’язок, коли доля кожної плитки потенційно прив’язана до маршруту через усю сітку, не дає головоломці з обертанням перетворитися на просту бухгалтерію, і саме тому розв’язувачі для ширшої родини головоломок Net/Pipes («мережа/труби») спираються на поширення обмежень і пошук, а не на простий прохід зліва направо. 5
Попри всю неосяжність простору станів, величина, за якою Conduit вас оцінює, крихітна й людська: скільки разів ви натиснули. Рахунок дорівнює 1000 − 4 × ходи − 2 × секунди, з нижньою межею нуль. 3 Для будь-якої дошки існує теоретичний мінімум кількості поворотів, сума по всіх плитках найменшої кількості чверть-обертів, потрібних, щоб дійти до розв’язаної орієнтації, і кожен зайвий оберт понад нього коштує вам чотири очки, кожна секунда бездіяльності — два.
Отже, справжня гра розташована між двома величезними фактами й одним маленьким. Стіг сіна завширшки 449 орієнтацій; голки — численні кістякові дерева сітки; а ваше завдання — дістатися від одного до іншого за якомога меншу кількість єдиного дозволеного ходу. Комбінаторика гарантує, що відповідь там є. Підрахунок очок тихо кидає вам виклик знайти її, не блукаючи. 4