木製列車セット「ブリオ」でのアルゴリズム探索：2 歳の子供が教えた制約解決と SAT ソルバー

はじめに：息子との遊びから生まれた問題

• 背景：息子は 2 歳になり、アポロニウス的な「支配への欲求」や機械化されたものへの興味に加え、特に木製列車セット**「ブリオ（Brio）」**を愛しています。
• 親子の関係性：息子は「チュートチュート（蒸気機関車のおおきなきいてん！）」と叫びながら遊びますが、「私には絶対に列車に触れることを禁じられている」というルールがあります。そのため、私は興味深い配線レイアウトの構築を楽しんでいます。
• 問題の提起：
  • 部品は明確に組み合わさる形状になっており、背後の設計構造とは何か。
  • 与えられた部品の集合に対して、どのような最も複雑なレイアウトを構築できるか。
  • 私は数学的なバックグラウンドはありませんが、これは面白いアルゴリズム問題だと直観しました。
• この記事の内容：息子が発見してくれた「制約解決（Constraint Solving）における専門性」に基づき、彼に聞いた話を編集して紹介します。可視化はブラウザ上で見た方がより効果的です。

---

ブリオシステムと 2D 平面への抽象化

• ブリオについて：子供向けの木製列車玩具ですが、特に興味のある大人によって深掘りされています。
  • 各部品には文字コード（例：A, E）と寸法が割り当てられています。
    • 「A」：144mm の中径ストレートなど。
    • 「E」：内側 182mm、外側 222mm の円弧（45 度曲線）。
  • 組み合わせの可能性：8 つの「E」を組み合わせると、直径約 40cm の円を作れます。多くの部品は裏返すことで左右折れを変えられます。
• モデルの簡略化：
  • ランプや橋は無視し、システムを2 次元として扱います。
  • 理由：橋は不安定で子供が倒壊させてしまうためです。

---

アルゴリズム進化史：図 1 から図 6 へ

ステート 0：円を作ろうとする試み

息子は「円！」と大歓声、私は『トーマスと友達たち』の読書の甲斐を感じます。しかし、最もシンプルな閉ループでは物足りません。**与えられた部品全てで、開放された接続子をペアにする（すべて閉じる）**のが目標です。

ステート 1：バックトラック探索（Backtracking Search）

幼児が配線を作るアプローチを模倣します。「部品を敷き詰めて、合わなければ元に戻す」というプロセスです。

• 手法：再帰的バックトラック。開放された接続子をリスト化し、一つずつ部品を試して再帰的に進み、行き詰まったら最後の接続子まで戻ります。
• Python 風のパセウドコード：

  def search(open_connectors, unused_pieces, layout):
      # 接続子がなければ終了。未使用の部品があれば失敗、なければ成功
      if not open_connectors:
          return layout if not unused_pieces else None
  
      # 最初の接続子を取得し、すべての可能な配置を試す
      connector = open_connectors[0]
      for piece in unused_pieces:
          for port in piece.ports:
              placement = mate(piece, port, connector) 
              if collides(placement):
                  continue
              
              # 再帰呼び出し（成功したら返す）
              found = search(update(open_connectors, placement),
                            unused_pieces - piece,
                            layout + placement)
              if found is not None:
                  return found
      return None
  

• 課題：ソルバーは直感的な最適解（例：すべての曲線を同じ向きに配置）を理解していません。**「states explored（探索された状態数）」**が急増し、無駄な分岐が発生します。

ステート 2：配線を大きくする（長方形の発見）

円を半分に分けて反対側にストレートセクションを追加し、レイアウトを拡大します。息子はこれを「楕円形」と勘違いしますが、実際には「長方形（oblong）」です。

• 状態数の爆発：
  • 部品数 +2（2 つのストレート A）だけで、状態探索数は約8 倍に増加します（1,930 ステート）。
  • アルゴリズム実行時間は指数的に増大します（$O(b^n)$）。
• 貪欲法の限界：
  • 「合う最初の部品を採用し進み、振り返らない」アプローチは失敗しやすいです。
  • ストレート部品は僅かな位置のみにしか機能せず、誤った配置は早期の行き詰まり（dead end）を招きます。

ステート 3：交差点による分岐ポイントの追加

交差点部品**「H3」**を導入し、二つの円が重なって列車を通過または線路変更できるようにします。

• グラフ理論との関連：
  • 部品は点（頂点）で、接続子は辺となります。
  • 通常の部品は 2 つの接続子しか持たないため、単一のサイクル（閉ループ）でした。
  • H3 は 4 つの接続子を持ち、配置すると3 つの接続子を開放し、探索が分岐します。
• 衝突検出（Collision Detection）：
  • 部品を重ねて敷き詰めるのを防ぐための重要な制約です。

ステート 4：分岐ループとネットワーク化

「L」分岐と「M」分岐を追加し、内部ループや複雑なネットワーク構造を作ります。

• オイラー回路の限界：
  • 息子は**「次数（Degree）3」**を指摘します。交差点（度数 4）では∞字形を追うことが可能ですが、分岐（度数 3）を含むと、一度のラップですべての経路をカバーできないことが数学的に証明されます。
  • これは**「θ グラフ（Theta Graph）」**と呼ばれる形状に対応します。

ステート 5：制約充足問題（CSP）への転換

多数の交差点と分岐を使った複雑なレイアウトを試みるも、部品同士が離れすぎて接続できなくなります。息子はこれを**「制約充足問題（Constraint Satisfaction Problem）」**だと指摘しました。

• CSP の定義：
  • 変数：開放された接続子
  • ドメイン：そこにある部品＋回転／反転の組み合わせ
  • 制約：全ての接続子がペアになること、軌道が交差しないことなど。
• フォワードチェック（Forward Checking）の試みと限界：
  • 配置後、衝突する可能性のあるオプションを除外しますが、ブリオの場合は部品がどこにでも合うため効果に限界がありました。
  • **対立指向のバックジャンプ（Conflict-directed Backjumping）**を導入し、失敗の原因となったより前の配置まで直接戻りました。
• グローバルチェック（Global Constraint）の導入：
  • 単なる局部チェックではなく、全体レイアウトの状態を監視します。
    1. 開放された接続子をすべてペアにするのに十分な部品が残っているか。
    2. 残された部品が物理的に到達可能か。
  • これにより、探索状態数は約1/8に削減されました。

ステート 6：SAT ソルバーによる解決

バックジャンプしても同じ間違いを繰り返すため、失敗を永続的に記憶させる必要があります。息子はこれをタイル配置問題（ポリオミノ）と結び付け、**「SAT ソルバー（Boolean Satisfiability Problem）」**を使おうと提案します。

• SAT 問題への変換：
  • 変数：

    x[placement] = true

    （特定の部品が特定的位置にあるかどうか）。
  • 条項（Clauses）：「少なくとも一つの真」を満足させるルール。
    • 各ポートは正確に 1 つのペアと結合すること。
    • 交差点や分岐の重複を防ぐこと。
• 「ズル」なアプローチ：
  • ブリオはグリッド固定ではないため、全位置をリスト化するのは不可能です。
  • 解決策：バックトラックで探索可能な位置を記録し、これを SAT の入力として与えます。「いいえ」という答えは「その位置を使えば閉路が存在しない」ことを意味します。
• 連結性の保証（Counterexample-guided Refinement）：
  • 単一条項で全体を連結することは難しいため、局部ルールで分岐し、非連結な場合は反例（Counterexample）として新しい条項を追加して再解決というループを行います。これは整数計画ソルバーの巡回セールスマン問題解決法と類似しています。

---

結論：学んだことと教訓

最終的に SAT ソルバーに従って部品を配置しましたが、実は息子が私に多くのことを教えてくれました。

アルゴリズム比較と特性

手法	特徴・長所	短所・限界
バックトラック探索	簡潔でメモリ使用量少。即時回答可能。	最悪ケースで指数的時間増大。再帰的なので過去の失敗を記憶しない（同じ間違いを繰り返す）。
CSP ソルバー (伝播＋バックジャンプ)	全局制約やフォワードチェックで探索空間を削減できる。	自動的に効率化されるわけではない。有効な制約の発見が必要である。
SAT ソルバー	永続的なメモリ（条項学習）。一つの失敗が他の場所での再発を防ぐ。部品選択も可能にする。	メモリと速度のコストが高い。スコープが与えられた入力空間に限定される。

重要な教訓

1. 問いの定義が重要：「この集合で閉じるか」と「最も複雑なレイアウトを作るか」は異なる問いです。後者には前者のために作られたツール（CSP）は不適切でした。
2. 制約解決の自動改善は幻想：バックトラックや CSP は必ずしも自動的に検索を最適化するわけではありません。大幅に検索空間を削減する有用な制約を見つけることが鍵です。
3. SAT の真価：条項学習により、一つの実験から得られた知識（失敗）が永続的に適用され、より高い次元での部品選択や最適化が可能になります。

息子は「実際のプランナーたちは時刻表作成やルートの最適化にも SAT を使用しています」と教えてくれました。遊びの中から深層学習的なアルゴリズムの理解へと進化する面白さです。