ルービックキューブの最短手数の上限は20手

有名パズルに対する解析の話．
ルービックキューブはどんな盤面から初めても20手以内に解けるということが証明されたっぽいですね．普通にやると35年かかるものをグーグルのサーバーで計算して時間内にやったのだとか．
http://www.cube20.org/

Every position of Rubik's Cube™ can be solved in twenty moves or less.

With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves

ルービックキューブというと解くのに結構手数がかかるようなイメージがあったのですが，どんな手数に対してもわずか20手あれば解けるというのは驚きです．
(52手で必ず解けるアルゴリズムは初期の頃からあったそうですが．)

戦略など

Wikipediaとかに記されているように，ルービックキューブにはかなり莫大な状態数(4.3*10^19くらい)があることがわかります．
当然全部調べるなんてことはできないんで，どうやったらそんなことできるんだろうなー と気になるのですが，どうやら4.3*10^19通りあるパターンを2.2*10^9くらいの種類にグループ分け(それぞれのグループは同じ数のパターンをもつ)して考えたそう．（で，そのグループの代表元についてだけ調べあげた… ということでいいんだろうか）
どのようなグループ分けがなされたのかは記されていなかったので分かりませんが，coset(剰余類)という単語がたくさん出てきていたので，おそらくなんらかの変換写像で剰余類分解したんじゃないかなーと勝手に思っています(あやふや)．
対称なパターンを除外して考えるのは高速化のためにとても重要なようで，回転や鏡像による同型はあるパターンに対して自身も含めて48通り(回転が24通り，鏡像が2通り)もあるため，単純に考えるとこれを除くだけで50倍近く速度が変わることになります．
また，最長手数の lower_bound が20手であることは割と昔から知られていたようなので，解を求めるのには最短手ではなく，20手以内で解ける解を見つけるようにして高速化をしたのだとか．
さまざまな高速化を行って，1つの盤面に対しては20秒程度で解けるようなプログラムが書かれていたらしいです．さすがというかなんというか．
んで，これで全体で(普通にやると)20*(2.2*10^9/48)秒 = 35年 程度で解ける状態になったので，それをGoogleのサーバーのアイドル時間を使って解いた，と．へー．

ところでこういう研究ってどういう人たちがやってるんだろうか．

追記

ここまで書いていろいろ調べたらEngadgetに分かりやすい記事がありました．