DiBS: 拡散モデルによる分岐選択
数独解法における学習ベースソルバーの正しさの保証の欠如と、記号的ソルバーのロングテール探索の問題に対処するため、研究者らは拡散モデルを用いた分岐選択手法DiBSを提案した。DiBSは記号的ソルバーの完全性を維持しつつ、拡散モデルで候補値をランク付けし、探索コストを大幅に削減する。Royle 17ヒント数独ベンチマークでの実験では、ノード数、バックトラック数、ロングテールパーセンタイルが改善され、困難な問題に対する学習済みグローバルガイダンスの有効性が示された。
数独は、厳格な離散的制約の下で大域的な構造的推論を必要とする代表的な制約充足問題である。既存の解法アプローチは主に、従来のヒューリスティック手法と深層学習ソルバーの2つに焦点が当てられてきた。しかし、これらのアプローチには相補的な限界がある。学習ベースのソルバーはハードな正しさの保証が欠けており、完全な記号的ソルバーは依然としてロングテール探索に陥りやすい。このような問題に対処するため、研究者らはDiBS（Diffusion-Informed Branch Selection）と呼ばれる新たな拡散モデル誘導手法を提案した。
DiBSの核心は、記号的ソルバーの完全性を維持しつつ、拡散モデルを分岐順序付けのガイドとして活用することである。具体的には、現在の部分割当てと軽量な一貫性シグナルに基づいて候補値をランク付けし、探索を効率的な方向へ導く。さらに、研究チームはこの手法が機能する理由とその有効性を理論的に証明している。
挑戦的なRoyle 17ヒント数独ベンチマークでの実験では、DiBSは強いヒューリスティックベースラインと比較して探索コストを大幅に削減し、特にノード数、バックトラック数、ロングテールパーセンタイルで顕著な改善が見られた。これらの結果は、分岐順序の誤りが最も高いコストを生む困難なインスタンスにおいて、学習された大域的ガイダンスが極めて有効であることを確認している。
DiBSの全コードはGitHubで公開されており、今後の研究の基盤を提供している。本研究は、数独解法に新たな視点をもたらすとともに、制約充足問題における記号推論とニューラルネットワークの融合に向けた重要な一歩となる。