この記事はなに？

私は現在4x4x4ルービックキューブ(ルービックリベンジ)を解くロボットを作り、世界記録を目指しています。ロボットを作る上で一番のハードルであったのが4x4x4キューブを現実的な時間に、なるべく少ない手数で解くアルゴリズムを実装することです。
調べてみると4x4x4については文献や先人が少ないことがわかると思います。そんな貴重な資料の一つになれば嬉しいと思い、この記事を書いています。
GitHubはこちら
この記事の内容は完全ではありません。一部効率の悪いところを含んでいるかもしれません。今後改良したら随時追記していきます。

↓競技用4x4x4ルービックキューブとプログラム制作のために番号を振られた競技用4x4x4ルービックキューブ

全貌

この記事集は全部で3つの記事から構成されています。

概要
アルゴリズム(本記事)
実装

この記事で話すこと

この記事では前回の記事でお話ししたTsai's Algorithmを詳しく解説します。

実際のスクランブル

この記事ではわかりやすくするため、実際のスクランブルを使用して解説します。使用するスクランブルは(白面をU面に、緑面をF面として)、

R2 B2 F2 D2 R2 B2 D F2 D' F2 D B' F' D' F2 R U F2 L D' Rw2 Fw2 U R' U' D2 Fw2 F2 L Uw2 D' L U2 Fw' R Uw2 U2 B L Uw' D' Rw Uw2 B Rw R

です。4x4x4ルービックキューブを持ってらっしゃる方はぜひ回しながらお読みください。キューブの状態は写真の通りです。これからキューブが並んだ画像が現れたときにはこの写真の向きの画像だと思ってください。

フェーズ0

フェーズ0では以下のことをします。
R面とL面のセンターパーツをすべてR面かL面に持ってくる
例として、先程のスクランブルでは以下の手順を回します。
Rw L' Uw R' Rw D Fw
回した後の状態は写真の通りです。

R面とL面のセンター4つの部分に赤かオレンジのみしかないことがわかると思います。これが今回目指すことです。
完成状態ではR面とL面にはそれぞれ赤とオレンジのパーツが集まります(もちろん向きによりますが、ここでは便宜上白がU面、緑がF面とした場合のことを考えます)
このフェーズでは使う回転に制限をかけず、自由に適当に回します。使う回転は以下です(全種類の回転です)。
R, R2, Rw, Rw2, L, L2, U, U2, Uw, Uw2, D, D2, F, F2, Fw, Fw2, B, B2

フェーズ1

フェーズ1では以下のことをします。
1. F面とB面のセンターパーツをすべてF面かB面に持ってくる
2. ハイエッジとローエッジを分離する
3. R面とL面のセンターの状態を今後処理可能な12の状態のうちの一つにする
4. OLLパリティを解消する
多いですね。とりえず例のスクランブルで回してみましょう。手順は以下です。フェーズ0が終わったあとにこの手順を回します。
L2 D2 F Rw F2 R2 B2 Rw

ぱっと見てまずF面とB面、U面とD面についてもフェーズ0と同じようにそれぞれのセンターが集まっていると思います。これが1つ目の達成目標です。
2つ目、ハイエッジとローエッジについては、少し理解が難しいかもしれません。天下り的ですが、もし写真のようになっていると、内層90度回し(Uw, Rw, Fw)を使わないとこの2つのエッジをペアリング(くっつけること。写真右の状態)できません。今後の操作では内層回転に関しては180度回転のみを使うよう制限するので、そうなっても解けるような状態にします。
さて、写真では同じ色のペアを持つエッジが同じ面かつ列にありますね。これがいけない状態です。この状態を回避したいのです。
3つ目は、今後R, Lの回転は使わない(つまりR面かL面を回すときには180度回しになる)ことによる制約です。R, Lの2種類の回転を使わない場合、端的に言ってしまえばセンターが写真のように市松模様になっていたり1つだけ対面の色が混じっていたりしては揃えられません。この状態を回避します。
4つ目は、4x4x4特有の現象であるOLLパリティの回避です。OLLパリティを解消するためには内層90度回しが必須です。よってこの時点でOLLパリティを回避します。具体的にはEO(Edge Orientation=エッジの向き)の反転している数を数え、奇数だったらOLLパリティあり、偶数ならなし、と判断します。
フェーズ1で使う回転は以下の通りです。
R, R2, Rw, Rw2, L, L2, U, U2, Uw2, D, D2, F, F2, Fw2, B, B2

フェーズ2

フェーズ2では以下のことをします。
1. 側面(F, R, B, L面)センターに「列」を作る
2. 側面に位置するエッジのペアリングを行う
例のスクランブルでは以下の手順を回します。
D L2 Uw2 Rw2 D F' Uw2 B

1つ目の目標は、今後F, F'回転を使わないことによる制約です。側面センターの模様を、揃っているもしくは縦に同じ色が並んでいる状態にします。
2つ目の目標は単に側面に位置するエッジ(FR, BR, BL, FLのエッジ)をペアリングします。写真を見るとこの位置のエッジが揃っていることがわかると思います。
フェーズ2で使う回転は以下の通りです。
R2, Rw2, L2, U, U2, Uw2, D, D2, F, F2, Fw2, B, B2

フェーズ3

フェーズ3では以下のことをします。
1. センターを6面完成させる
2. 残りのエッジをペアリングする
3. PLLパリティを解消する
例のスクランブルでは以下の手順を回します。
L2 U L2 U Rw2 D Fw2 L2 U B2 Rw2

ぱっと見てパズルが"3x3化"されていることがわかると思います。ここまでをスピードキューブの用語では「リダクション」と言います。
1つ目、センターが完成しています。
2つ目、エッジペアリングがすべて済んでいます。
3つ目はぱっと見ただけではわからないです。エッジの2点交換であるPLLパリティの状態は内層を回さないと解消できません。今後外層回しのみでパズルを揃えていくため、PLLパリティを解消します。
フェーズ3で使う回転は以下の通りです。
R2, Rw2, L2, U, U2, Uw2, D, D2, F2, Fw2, B2

フェーズ4

フェーズ4では以下のことをします。
1. U面とD面にあるべきステッカーをU面またはD面に持ってくる
2. EOを解消する
例のスクランブルでは以下の手順を回します。
D L' F' D R' L' U2 F' D R B

ぱっと見てU面とD面に白(最終的にU面にくる色)と黄(最終的にD面にくる色)しかないことがわかると思います。これが1つ目の達成目標です。
2つ目はEOの解消です。今後、最後のフェーズであるフェーズ5ではR, L, F, Bの回転を使用しません(これらの面を回すときは必ず180度回転を用います)。エッジの反転(EO)は必ず2つの直交する面の90度回転が使えないと解消できません。そこで今のうちにEOを解消します。
フェーズ4で使う回転は以下の通りです。
R, L, U, U2, D, D2, F, B

フェーズ5

最後のフェーズです。フェーズ5では最終的にパズルを完成させます。
例のスクランブルでは以下の手順を回します。
U R2 U L2 U2 L2 B2 U F2 U2 L2 B2 U'

パズルが揃っているのがわかると思います。
フェーズ5で使う回転は以下の通りです。
R2, L2, U, U2, D, D2, F2, B2

まとめ

この記事ではTsai's Algorithmをベースに4x4x4ルービックキューブを計算機が解くためのアルゴリズムを紹介しました。次回の記事では実際にこれを実装する大まかな指針や実装上でのTIPSを紹介します。