Ежедневное поле — семь плиток в ширину и семь в высоту. Выглядит оно небольшим. А потом вы подсчитываете, сколькими способами его можно повернуть, и число перестаёт казаться небольшим вовсе.
Написано и отредактировано на английском языке. Эта русская версия создана машинным переводом; там, где важна точность, авторитетным остаётся английский оригинал. Читать оригинал на английском →
Каждая плитка в 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