日々の盤面は横7タイル、縦7タイルです。小さく見えます。ところが、それを回す方法が何通りあるかを数えてみると、その数はまったく小さく見えなくなります。
英語で執筆・編集されました。この日本語版は機械翻訳によって作成されたものです。正確さが重要な箇所については、英語の原文が正式なものです。 英語の原文を読む →
Conduitのタイルはどれも、元の位置から0、1、2、または3クォーター回転させた4つの向きを取り得ます。1 デイリーグリッドの49マスそれぞれに、この4つの向きから独立に1つを選ばせると、盤面の異なる状態の数は449になります。書き出せば316,912,650,057,057,350,374,175,801,344、つまり30穣(3のあとに0が29個続く数)を超える配置があり、ゲームはその中から、完全に点灯していて漏れのないものを1つ見つけるよう求めてくるのです。
パズルを配るシャッフルは、タイルごとに0から3までのクォーター回転数をランダムに選びます。1 ですから、あなたが出会う盤面はその巨大な空間から一様に引かれたものであり、そこから差し引かれているのは、すでに解けたグリッドを配らないようにゲームが行う慎重な除外の1点だけです。1 総当たりは論外です。ゲーム自身のテストには、すべてのタイルの4つの回転を試すのは指数的だと記されており、網羅的探索が実行されるのは9マス以下のおもちゃのような盤面に限られます。2
この見出しの数は数えすぎです。回し方を気にしないタイルがあるからです。四方すべてにコネクタを持つ十字型は、4つの向きのどれでも同じに見え、回しても何も変わりません。直線型には水平と垂直の2つの見た目しかありません。半回転すると自分自身に重なるからです。非対称な形、すなわちL字型、T字型、コネクタが1本だけの端末型だけが、本当に4つの異なる向きを持ちます。3
| 形 | コネクタ | 異なる向き | 対称性 |
|---|---|---|---|
| 端末型(ノード/電球) | 1 | 4 | なし |
| 直線型 | 2 | 2 | 半回転 |
| L字型 | 2 | 4 | なし |
| T字型 | 3 | 4 | なし |
| 十字型 | 4 | 1 | 完全 |
形の名前はゲームの設計ノートで定義されており、異なる向きの数は、列挙された回転のもとで4ビットのコネクタマスクが変化しないことから導かれます。3 実効的な探索空間は、これらタイルごとの対称性の積の分だけ449より小さくなりますが、L字型とT字型がほどよく混ざった盤面であれば、それでも天文学的に大きいままです。
問いを裏返してみましょう。試すかもしれない向きのことは忘れて、そもそも解けた盤面が何通りあり得るかを問うのです。完成したConduitのグリッドは、つながっていて、電力がすべてのタイルに届き、無駄なループがないパイプの集合です。ジェネレータが作るのが全域木、つまり、つながっていて、閉路がなく、電源から各ノードへの経路が1本ずつある構造だからです。3 そのような配線の一つひとつは、まさにグリッドグラフの全域木です。頂点はマスであり、辺はパイプが橋渡しできる共有された境界です。
そして全域木は正確に数えられます。1847年の成果であるキルヒホッフの行列木定理は、任意のグラフの全域木の数が、そのラプラシアン行列の任意の余因子に等しいと述べています。これは多項式時間で計算できる行列式です。4 グリッドではその数はサイズとともに爆発します。ささやかな4×4の格子でさえ100,352本の全域木を持ち、そこから先は猛烈な勢いで増えていきます。そのどれもが、正当な、完全に点灯したConduitの解です。パズルが難しいのは答えが少ないからではなく、答えが、はるかに大きな「惜しい答え」の群衆の中に隠れているからです。
解けた状態は数えることができ、しかも数多くあります。シャッフルされた状態も数えることができ、そしてはるかに多くあります。解くとは、そこにあると分かっている針を探すことです。ゲームがわざとそこに隠したのですから。
パズルが分解できればと期待するかもしれません。左上を確定し、次にその隣のタイルを確定し、整然と遠い角まで行進していく、というふうに。盤面の一部がそれに応じてくれることも確かにあります。角のタイルは隣と接する辺が2つしかないので、そのコネクタは強く制約されます。境界上の端末型タイルは内側を向くしかありません。こうした強制手が足がかりになります。
しかし、2つの勝利条件はそれほど従順に連鎖してはくれません。漏れがないことは局所的な性質で、辺ごとに確かめられます。通電していることはそうではありません。あるタイルが点灯しているかどうかは、電源まで途切れずに続く接合の鎖、場合によっては盤面全体を横切る鎖にかかっています。3 ある角で行った変更が、その領域に電力を送っていた唯一の経路を断ち切ることで、遠く離れた領域を闇に沈めることがあります。この結合、すなわちすべてのタイルの運命がグリッド全体を通る経路に結びつき得るということこそが、回転パズルが簡単な帳簿付けに崩れ落ちるのを防いでいるものであり、より広いNet/Pipes系(パイプつなぎパズルの一族)のソルバーが、単純な左から右への走査ではなく制約伝播と探索に頼る理由でもあります。5
状態空間がどれほど広大であっても、Conduitがあなたを採点する量は小さく人間的なものです。何回タップしたか、です。スコアは1000 − 4 × 手数 − 2 × 秒数で、下限は0です。3 どの盤面にも理論上の最小回転数があります。解けた向きに到達するのに必要な最少クォーター回転数を、すべてのタイルにわたって合計したものです。それを超えて無駄に回すたびに4点、何もしない1秒ごとに2点が失われます。
ですから本当のゲームは、2つの巨大な事実と1つの小さな事実の間にあります。干し草の山は449通りの向きの幅があり、針はグリッドの数多くの全域木で、あなたの仕事は、唯一の合法手をできるだけ少なく使って一方から他方へたどり着くことです。組合せ論は、答えがその中にあることを保証します。採点は、さまよわずにそれを見つけてみろと静かに挑んでいるのです。4