CayleyR：サイクル交差によるTopSpinパズルの解法

研究者らは、順列パズルを解くためのRパッケージcayleyRを発表しました。このパッケージの核心は、ケイリーグラフにおけるサイクル交差を検出することで解経路を見つける点にあります。順列パズルは、対称群Snのケイリーグラフとしてモデル化できます。頂点は順列状態、辺は許容操作を表します。cayleyRのアルゴリズムは反復的双方向探索を実行します。初期状態と目標状態の両方からランダムな操作系列を生成し、ケイリーグラフ上でサイクルを形成します。二つのサイクルが交差すれば、それが解経路となります。直接交差が見つからない場合は、距離に基づくブリッジ選択でギャップを狭め、このプロセスを繰り返します。

cayleyRは主にTopSpin(n,k)パズルを対象としています。TopSpinは、円形のレールに数字の書かれたタイルが並び、循環シフトと接頭辞反転操作でシャッフルされる古典的なパズルです。その状態空間は、循環シフトと接頭辞反転によって生成されるケイリーグラフです。このパッケージは数学的枠組みとアルゴリズムの詳細な説明に加え、C++によるハッシュインデックス状態ストアとオプションのVulkan GPU加速による効率的な実装を提供します。

cayleyRはCRANで公開されており、誰でもインストールして利用できます。この研究は、特に大規模状態空間を扱う際の組み合わせ探索や人工知能における経路計画問題に新たなツールを提供します。著者のYuri Baramykov氏は2026年7月14日に論文を提出し、全文は17ページ、2つの図を含みます。研究者やパズル愛好家にとって、cayleyRは複雑な順列パズルに新たな視点をもたらし、グラフ理論と高性能計算の融合の可能性を示しています。