Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

コンピュータが単なる超高速な計算機のように数字を処理するだけでなく、リズムに合わせて踊る世界を想像してみてください。これは、**振動型ニューラルネットワーク（ONN）と呼ばれる、「物理ベース」のコンピューティングの世界です。標準的な電子スイッチの代わりに、これらのネットワークはオシレータ（発振器）**と呼ばれる、微細に振動するユニットを使用します。それは、メトロノームが詰まった部屋や、合唱団のようなものです。このシステムでは、情報は単純な「オン」か「オフ」のビットとしてではなく、**位相（フェーズ）**として知られる「振動のタイミング」として保存されます。2つのオシレータが完璧に同期して振動していれば「同相」であり、反対のタイミングで振動していれば「逆相」となります。

これらのネットワークの目標は、すべてのオシレータが安定したパターンに落ち着く、完璧な調和、すなわち「最低エネルギー状態」を見つけ出すことです。このアプローチは、組合せ最適化問題——特定のルールに抵触することなく、多くのピースを配置しなければならないパズル——を解くのに特に適しています。例えば、隣接する国同士が同じ色にならないように地図を塗るグラフ彩色問題があります。もし、一連のオシレータが、隣り合うものが同じタイミングで振動しないようなパターンに自然と落ち着くようにできれば、力任せの数学ではなく、物理法則を用いて複雑なパズルを解いたことになります。これは、従来のコンピュータがこれらの種の問題に対して膨大な電力を消費し、時間を要してしまう一方で、この「踊るオシレータ」がより高速でエネルギー効率の高い思考法を提供できる可能性があるため、非常に重要です。

---

大いなる数独ダンス・オフ

次に、**数独（Sudoku）**についてお話ししましょう。ルールはご存知の通り、グリッド内の空欄を、行、列、および小さなボックスの中に数字の重複がないように、1から9（または小さなバージョンの場合は1から4）の数字で埋めていくというものです。これは古典的な論理パズルですが、コンピュータにとっては試行錯誤の連続となる非常に厄介な問題です。

この論文の著者であるアイントホーフェン工科大学のフィリップ・サボ氏とアイダ・トドリ＝サニアル氏は、この「踊るオシレータ」ネットワークを使って数独に取り組むことにしました。彼らは数独のグリッドをグラフ彩色問題として扱いました。数独のグリッド内の各空欄を「ダンサー」だと想像してください。ルールは単純です。同じ行、列、またはボックスにいるダンサーは、同じ「色」（この場合は、1や2、3といった特定の数字を表すもの）を身につけてはなりません。

オシレータの世界では、「色を身につける」ということは、特定の律動（リズム）で振動することを意味します。9x9の数独の場合、オシレータが選択できるリズム（位相）は9つあります。ネットワークの仕事は、すべてのダンサーが、隣人たちが同じダンスステップを踏まないようなリズムを選択するように導くことです。

旧来のダンスステップの問題点

著者らは、他の科学者たちが以前どのようにこれに挑んできたかを調査しました。ある手法は、ダンスの振り付けを決めるために、事前にすべての筋肉の動きを計算しようとするような、非常に計算コストの高い複雑な数学的公式を用いるものでした。別の手法はよりシンプルなアプローチを用いましたが、致命的な欠陥がありました。それは、ダンサーが「ズル」をしてしまうことを許容してしまう点です。

例えば、同じ行にいる2人のダンサーが、二人とも「数字の1」のダンスを踊ることに決めたシナリオを考えてみてください。旧来のより単純なモデルでは、ネットワークは「おや、彼らは二人とも『数字の1』のリズムを踊っている。これは有効なリズムだから、問題ないぞ！」と考えてしまうかもしれません。しかし、数独において、それは災難です。ルールでは、同じ行に2つの「1」があってはならないと決まっています。旧来のモデルには、もし彼らが間違った数字で同期してしまった場合に、その状態からダンサーを追い出す方法がなかったのです。

新しい「キック」項

これを解決するために、著者らはオシレータを踊らせるためのよりシンプルで新しい方法を考案し、特別な「キック（蹴り）」のメカニズムを追加しました。

1. よりシンプルなリズム: 複雑で高価な数学的公式の代わりに、よりクリーンで直接的な方程式を使用しました。これにより、コンピュータのシミュレーションがはるかに高速かつ安価に実行できるようになりました。
2. 「キック」（秘伝のソース）: これが最も重要な部分です。彼らは、方程式にレフェリーのように機能する特別な項を追加しました。もし同じ行、列、またはボックスにいる2人のダンサーが、誤って全く同じ周波数で振動し始めた場合（つまり、同じ数字を選んでしまった場合）、このレフェリーが鋭い「キック」を与えます。これにより、彼らをその安定した快適な状態から叩き出し、別のリズムを試すよう強制するのです。

この「キック」があることで、ネットワークはパズルが実際に正しく解かれたときにのみ、落ち着くことができます。それは、教室を回っている教師のようなものです。もし2人の生徒が間違った答えをささやき合っていたら、教師は彼らの肩を叩いて、立ち止まって考え直させるのです。

結果：完璧なパフォーマンス

チームは、この新しい「キック・アッス（最高にイカした）」オシレータ・ソルバーを、4x4の小さなグリッドから標準的な9x9のグリッドまで、数千もの数独パズルに対してテストしました。彼らは、ホップフィールド・ニューラルネットワーク（HNN）に基づくものや、標準的な振動型ニューラルネットワークといった、他の2つの有名なソルバーと比較しました。

結果は以下の通りです：

• 4x4のパズルについて: 彼らの新しいソルバーは、実質的に完璧でした。空白の数がどれほど多くても、ほぼ100%のパズルを正しく解きました。他のソルバーは苦戦し、空白が増える（難易度が上がる）につれて精度が急激に低下しました。
• 9x9のパズルについて: 結果は依然として印象的でしたが、完全ではありませんでした。空白が少ない場合（約25%以下）は、彼らのソルバーは非の打ち所がありませんでした。パズルがより難しくなっても（空白が37.5%まで増加）、80%以上のパズルを解くことができました。しかし、パズルが非常に難しくなると（空白が50%を超えると）、ソルバーはつまずき始め、約50%の正解率となりました。一方、他のソルバーはもっと早く失敗し、空白が40〜50%を超えると、正しく解けるパズルがほとんどなくなりました。

研究者たちはまた、「秩序パラメータ（order parameter）」についても調査しました。これは、オシレータが最終的な正しいリズムにどれだけうまく落ち着けたかを示すスコアのようなものです。彼らは、ソルバーがパズルを正解したときは、常にオシレータが非常によく組織化されていた（高い秩序パラメータ）ことを発見しました。逆に、不正解だったときは、オシレータは混沌としており、安定したパターンに合意できていませんでした。

次なるステップは？

著者らは、自分たちの「キック」項こそが成功の理由であると確信していますが、まだやるべきことはあると認めています。彼らのモデルには、動作させるために手動で調整しなければならないいくつかの「調整可能なパラメータ（knobs）」があり、それを見つけるのに多大な時間がかかりました。また、最も難しい9x9のパズルについては、オシレータが落ち着くまでに、より長い「ダンス」の時間が必要だったか、あるいは「キック」が十分に強力ではなかった可能性にも気づいています。

彼らは、将来のバージョンのソルバーにおいて、より複雑な「非線形」オシレータ（より複雑な動きをするダンサー）を使用したり、ルール違反者をより上手く捕まえるために「キック」関数を微調整したりすることを提案しています。しかし、現時点でも、これらの踊るネットワークの物理学にシンプルで巧妙なルールを加えることで、以前よりもはるかに良く数独を解けることを、彼らは証明したのです。これは小さな一歩ですが、壊れたシステムを修正するために必要なのは、時には正しい方向へのちょっとした「ひと押し」であるということを示しています。