격자에 불이 들어오는 방법의 수를 세다

4의 49제곱

Conduit의 모든 타일은 제자리에서 0, 1, 2, 3번의 4분의 1 회전만큼 돌려진 네 가지 방향을 가질 수 있습니다. ¹ 매일의 격자에 있는 마흔아홉 개의 칸 각각에 이 네 가지 가운데 독립적인 선택을 주면, 서로 다른 보드 상태의 수는 4⁴⁹가 됩니다. 풀어서 쓰면 316,912,650,057,057,350,374,175,801,344, 즉 3백 옥틸리언(10의 27제곱)이 넘는 배치이며, 게임은 그 가운데 완전히 불이 들어오고 새는 곳이 없는 하나를 찾으라고 요구합니다.

퍼즐을 건네주는 뒤섞기 과정은 각 타일마다 0에서 3 사이의 무작위 4분의 1 회전 횟수를 고릅니다. ¹ 따라서 여러분이 마주하는 보드는 그 거대한 공간에서 균등하게 뽑힌 것이며, 이미 풀린 격자를 건네지 않기 위해 게임이 신중하게 두는 단 하나의 예외만 제외됩니다. ¹ 무차별 대입은 논외입니다. 게임 자체의 테스트에는 모든 타일의 네 가지 회전을 전부 시도하는 것이 지수적이라고 적혀 있으며, 완전 탐색은 아홉 칸 이하의 장난감 보드에서만 실행됩니다. ²

대칭이 조용히 수를 줄인다

앞서 말한 대표 숫자는 실제보다 많이 셉니다. 어떤 타일은 어떻게 돌리든 상관하지 않기 때문입니다. 네 면 모두에 커넥터가 달린 십자 조각은 네 방향 모두에서 똑같이 보이며, 돌려도 아무것도 바뀌지 않습니다. 직선 조각은 반 바퀴를 돌리면 자기 자신으로 겹치기 때문에 가로와 세로, 두 가지 모습만 가집니다. 비대칭 모양, 즉 ㄱ자 모양의 꺾임 조각, T자 조각, 커넥터가 하나뿐인 끝 조각만이 진정으로 네 가지 서로 다른 방향을 가집니다. ³

모양의 이름은 게임의 설계 노트에 붙여져 있으며, 서로 다른 방향의 개수는 4비트 커넥터 마스크가 나열된 회전 아래에서 변하지 않는다는 사실로부터 따라옵니다. ³ 실질적인 탐색 공간은 이 타일별 대칭들의 곱만큼 정확히 4⁴⁹보다 작지만, 꺾임 조각과 T자 조각이 적당히 섞인 보드라면 여전히 천문학적으로 큽니다.

풀린 배선은 도대체 몇 개나 존재하는가?

질문을 뒤집어 봅시다. 여러분이 시도할지도 모를 방향들은 잊고, 애초에 풀린 보드가 몇 개나 가능한지 물어봅시다. 완성된 Conduit 격자는 서로 연결되어 있고, 전력이 모든 타일에 닿으며, 낭비되는 고리가 없는 파이프의 집합입니다. 생성기가 만드는 것이 바로 신장 트리이기 때문입니다. 연결되어 있고, 순환이 없으며, 전원에서 각 노드까지 경로가 하나뿐입니다. ³ 그런 배선 하나하나는 정확히 격자 그래프의 신장 트리이며, 여기서 꼭짓점은 칸이고 변은 파이프가 이어 줄 수 있는 공유된 경계선입니다.

그리고 신장 트리는 정확히 셀 수 있습니다. 1847년의 결과인 키르히호프의 행렬-트리 정리에 따르면, 어떤 그래프든 신장 트리의 수는 그 라플라시안 행렬의 임의의 여인수와 같으며, 이는 다항 시간에 계산할 수 있는 행렬식입니다. ⁴ 격자의 경우 그 수는 크기에 따라 폭발적으로 늘어납니다. 소박한 4×4 격자만 해도 이미 100,352개의 신장 트리를 가지며, 그 뒤로는 수가 맹렬하게 치솟습니다. 그 하나하나가 모두 정당하고 완전히 불이 들어온 Conduit의 해답입니다. 이 퍼즐이 어려운 것은 답이 드물어서가 아니라, 답이 훨씬 더 큰 근사-답의 무리 속에 숨어 있기 때문입니다.

국소적인 규칙, 전역적인 결과

퍼즐이 분해되기를 바랄 수도 있습니다. 왼쪽 위를 고정하고, 그 옆의 타일을 고정하고, 반대편 모서리까지 차근차근 행진하는 식으로 말입니다. 때로는 보드의 일부 구간이 실제로 그렇게 풀리기도 합니다. 모서리에 있는 타일은 이웃과 맞닿는 변이 둘뿐이라 커넥터가 크게 제약되고, 가장자리에 있는 끝 조각은 안쪽을 향할 수밖에 없습니다. 이런 강제된 수들이 발판이 되어 줍니다.

그러나 두 가지 승리 조건은 그렇게 순순히 이어지지 않습니다. 새는 곳 없음은 국소적인 성질이라 변 하나하나를 따라 확인할 수 있습니다. 전원 공급됨은 그렇지 않습니다. 어떤 타일에 불이 들어오는지는 전원까지 끊기지 않고 이어지는 연결의 사슬에 달려 있으며, 그 사슬은 보드 전체를 가로지를 수도 있습니다. ³ 한쪽 모서리에서 여러분이 바꾼 것 하나가, 멀리 떨어진 영역을 먹여 살리던 단 하나의 경로를 끊어 그곳을 어둠에 빠뜨릴 수 있습니다. 모든 타일의 운명이 격자 전체를 지나는 경로에 잠재적으로 묶여 있다는 이 결합이야말로 회전 퍼즐이 손쉬운 장부 정리로 주저앉지 않게 하는 요인이며, 더 넓은 Net/Pipes(파이프 잇기) 계열의 풀이 프로그램들이 단순한 왼쪽에서 오른쪽으로의 훑기 대신 제약 전파와 탐색에 기대는 이유이기도 합니다. ⁵

상태가 아니라 회전 횟수

상태 공간이 아무리 광대해도, Conduit이 여러분을 채점하는 양은 작고 인간적입니다. 몇 번 탭했는가입니다. 점수는 1000 − 4 × 이동 횟수 − 2 × 초이며, 최저 0점으로 고정됩니다. ³ 어떤 보드든 이론적으로 최소한의 회전 횟수가 있습니다. 모든 타일에 걸쳐, 풀린 방향에 도달하는 데 필요한 가장 적은 4분의 1 회전 수를 합한 값입니다. 그것을 넘어 낭비하는 회전 하나마다 4점, 허비하는 1초마다 2점을 잃습니다.

그러니 진짜 게임은 두 개의 거대한 사실과 하나의 작은 사실 사이에 놓여 있습니다. 건초 더미는 4⁴⁹가지 방향만큼 넓고, 바늘은 격자의 수많은 신장 트리이며, 여러분의 일은 유일하게 허용된 수인 회전을 가능한 한 적게 써서 한쪽에서 다른 쪽으로 옮겨 가는 것입니다. 조합론은 그 안에 답이 있음을 보장합니다. 채점은 헤매지 않고 그것을 찾아내 보라고 조용히 도발합니다. ⁴