「ルービックキューブは25手以内で揃う！」記事へのコメント

Rokickiの証明の概略

[mad-p (1491)]

元記事からリンクされている論文 [arxiv.org]を読みました。今回の証明概略はこんな感じ:

• ルービックキューブ群Gとその部分群H=<U,D,R2,L2,F2,B2>を考え、Hとcoset空間G＼Hの性質を調べるのはこれまでと同じアプローチ。Hの要素は20G個あり、直交するようにcosetが2.2G個ある。20G×2.2G=約43Eでキューブの取り得る全状態数になる。
• 従来の解法(Reidの方法) [wikipedia.org]は、Hが最大18手で到達可能、coset空間が最大12手で到達可能なので、18+12手以内でキューブの全状態が到達可能とするもの。
• Rokickiの方法は、すべてのcosetにつき、coset内の全要素がある手数(例えば25手)以下で解けると証明することによって、全キューブ状態が25手以下で解けると示すもの。cosetは2.2G個あるが、対象性を考えると139M個だけ考えればよい。
• cosetを頂点とするケーリーグラフを作成。あるcosetが20手以内で解けるなら、グラフ上で隣にあるcosetは21手以内で解けることを利用すれば、全数を解かなくてもよい。
• あるcosetの必要手数上限を得るために、1要素を1ビットに対応させた20Gビットのビットマップを使って、breadth-firstサーチを実行(集合の各要素を解くのでなく全体を一気に解くのでset solverと称している)。上限付近は具体的なキューブをKociembaの解法で解いてみることによって、時間のかかるBFサーチを省力化。

Rokickiは139Mのcosetのうち約4000をグラフの構造から戦略的に選び、それぞれ19ないし20手以内で解けることを確認しました。これによって全coset(の全要素)が最大25手で到達可能なことを示したそうです。coset内の探索は「少なくとも○○手以内では解ける」というところでやめてしまうことで時間短縮しています。

以前に話題になったKunkleの方法は [srad.jp]、碁盤の目状の街で東西に何ブロック、南北に何ブロック、合計○○ブロックで到達可能とした上で、対角一番遠い地点までのななめの近道がないかさがす方法に例えることができます。Rokickiの方法は、首都圏の私鉄・地下鉄のようなネットワークにおいて、主要な乗り換え駅に待ち時間○○分以内の支店を配置することによって、どの駅からでも△△分以内にどこかの店舗でサービスを受けられる、という感じの戦略です。

この方法は、cosetの最大手数が短縮されることによってケーリーグラフ上のクリティカルパスが変わっていくので、それに応じて別のcosetを選んで解くことを繰り返せば、全体の上限をさらに短縮することができます(支店を追加して最大の待ち時間を短縮できる)。現在24手という上限をめざして計算を続行中だそうです。