←前 2007年02月中旬 ↑index 2007年06月中旬 次→
■
CoopermanとKunkleが3x3x3ルービックキューブを解くのに必要な手数の上限が26手以下であることを示した。論文はこちら。「1手」の定義はface-turn metric(FTM)と明記されている。ブログやslashdotの記事で「研究者の間で共通の1手の定義があるのか?」なんて書かれているが、ちゃんとあるわけだし、複数ある「1手の定義」のうち、今回はこれを使いますと宣言している。みんな調べないで文句ばっかり言い杉。
CoopermanとKunkleの方法はThistlethwaiteによる4段階法、Kociembaによる2段階法と同様のアプローチで、G1=<L2,R2,F2,B2,U2,D2>とした場合に相当する(論文の中ではG1でなくQと表記)。つまり、180度回しだけで到達できる範囲(=G1)を考え、そこまでの最大手数とそこから完成までの最大手数を考えることになる。G1の要素が1.5万通りくらいあって、最大でも13手以内で完成(この計算では180度回しに限定せずFTMの全部の回し方を使ってよい)。任意の状態からG1に持っていくのに約1.3兆通りの可能性があって、最大でも16手以内でG1のうちどれかにすることができる。合計すると多くても13+16=29手以内で解けるとわかる。
CoopermanとKunkleは29手という上限をもっと縮めるため、上限近くの特定の場合について、KociembaのCube Explorerを使って最適解を総当たりで調べることにした。上の方法で26手以内と証明できないキューブ状態を生成し、Cube Explorerにかけた(論文には明記されていないが、約7.2万通りと思われる)。その結果、実際に26手より多くの手数を必要とする状態は出てこなかったとのことだ。