この記事はなに？
私は現在4x4x4ルービックキューブ(ルービックリベンジ)を解くロボットを作り、世界記録を目指しています。ロボットを作る上で一番のハードルであったのが4x4x4キューブを現実的な時間に、なるべく少ない手数で解くアルゴリズムを実装することです。
調べてみると4x4x4については文献や先人が少ないことがわかると思います。そんな貴重な資料の一つになれば嬉しいと思い、この記事を書いています。
GitHubはこちら
この記事の内容は完全ではありません。一部効率の悪いところを含んでいるかもしれません。今後改良したら随時追記していきます。
↓競技用4x4x4ルービックキューブとプログラム制作のために番号を振られた競技用4x4x4ルービックキューブ
全貌
この記事集は全部で3つの記事から構成されています。
この記事で話すこと
この記事では4x4x4ルービックキューブを(探索アルゴリズムを使って)解くプログラムを書くために必要な知識の紹介、およびプログラムの流れを軽くお話しします。
参考になる資料
参考となる資料を私が参考になったと感じる順番に紹介します。
- https://arxiv.org/abs/1601.05744
- https://github.com/cs0x7f/TPR-4x4x4-Solver
- http://cubezzz.dyndns.org/drupal/?q=node/view/525
- http://cubezzz.dyndns.org/drupal/?q=node/view/73
最初の資料は4x4x4キューブについて私が唯一見つけられた論文です。2つ目は実際に論文と似た手法でJavaを使って実装したレポジトリです。こちらも唯一の実装例として見つかりました。3つ目は2つ目のレポジトリの持ち主による投稿です。4つ目は謎ですが一応見つかった投稿です。
この記事を読むのに必要な知識
この記事を読むのに必要な知識とその入手方法を書いておきます。
回転記号
ルービックキューブの回転を客観的に正確に表す記号です。参考資料としてこちらをおすすめします。3x3x3についての回転記号の説明ですが、4x4x4も全く同じ記号を使います。
面の名前
回転記号で出てきたR, L, U, D, F, Bは、面の名前としても使われます。例えばF面と言えば正面の面を表します。
パーツの名前
4x4x4ルービックキューブの外側に出ているパーツには3種類あります。画像の通りです。
コーナーには3つ、エッジには2つ、センターには1つのステッカーがついています。
パーツの位置の表し方
パーツの位置について、またしても回転記号で出てきたR, L, U, D, F, Bを使います。エッジとコーナーで表し方が違うので別々に紹介します。
エッジ
エッジは当たり前ですが必ず2つの面にまたがっています。そこで、エッジをR, L, U, D, F, Bのうちからまたがっている面2つを取ってきて並べて表します。例えばUFエッジと言えば、U面とF面にまたがったエッジです。
コーナー
コーナーは必ず3つの面にまたがっています。そこでR, L, U, D, F, Bのうちからまたがっている面3つを取ってきて並べて表します。例えばUFRコーナーと言えば、U面、F面、R面にまたがったコーナーです。
パリティ
4x4x4ルービックキューブには特有の「パリティ」と呼ばれる状態があります。パリティには2種類ありますが、こちらの説明がわかりやすいです。なお、こちらのサイトではPLLパリティの説明が少しわかりにくいですが、要するにエッジのみの2点交換(3x3x3ルービックキューブで2点交換はありえません)の状態です。図にOLLパリティとPLLパリティの例を載せておきます。左がOLLパリティ、右がPLLパリティです。見えていない面は全部揃っています。
CP, CO, EP, EO
それぞれ
- Corner Permutation (コーナーパーツの位置)
- Corner Orientation (コーナーパーツの向き)
- Edge Permutation (エッジパーツの位置)
- Edge Orientation (エッジパーツの向き)
のことです。4x4x4キューブを構成する各パーツは、エッジとコーナーは位置と向き、センターは位置のみで一意に状態が表せます。
ベースとなるアルゴリズム
4x4x4ルービックキューブを探索で解くのはそう簡単ではありません。なにせ探索すべき木(このへんの用語や基礎知識はこちらの記事にわかりやすくまとめました)が大きすぎます。そこで、あるアルゴリズムがよく使われます。紹介した資料、および私による実装はすべてTsai's Algorithmというアルゴリズムがベースになっています。流れを説明しましょう。
なお、「使う回転」で例えばX回転を使うと書いてあったら実際に使う回転はX, X'の2種類です。そしてX2回転を使うと書いてあれば実際に使うのはX2のみです。
わからない言葉や表現があると思います。次の記事で各フェーズの詳しい解説をするときに説明しますのでここではふーんと言って流してください。
| フェーズ番号 | やること | 使う回転 |
|---|---|---|
| 0 | R面とL面のセンターパーツをすべてR面かL面に持ってくる | R, R2, Rw, Rw2, L, L2, U, U2, Uw, Uw2, D, D2, F, F2, Fw, Fw2, B, B2 |
| 1 | 1. F面とB面のセンターパーツをすべてF面かB面に持ってくる 2. ハイエッジとローエッジを分離する 3. R面とL面のセンターの状態を今後処理可能な12の状態のうちの一つにする 4. OLLパリティを解消する | R, R2, Rw, Rw2, L, L2, U, U2, Uw2, D, D2, F, F2, Fw2, B, B2 |
| 2 | 1. 側面(F, R, B, L面)センターに「列」を作る 2. 側面に位置するエッジのペアリングを行う |
R2, Rw2, L2, U, U2, Uw2, D, D2, F, F2, Fw2, B, B2 |
| 3 | 1. センターを6面完成させる 2. 残りのエッジをペアリングする 3. PLLパリティを解消する | R2, Rw2, L2, U, U2, Uw2, D, D2, F2, Fw2, B2 |
| 4 | 1. U面とD面にあるべきステッカーをU面またはD面に持ってくる 2. EOを解消する | R, L, U, U2, D, D2, F, B |
| 5 | 完成させる | R2, L2, U, U2, D, D2, F2, B2 |
まとめ
この記事では4x4x4ルービックキューブを解くプログラムを書くにあたって必要な知識の軽い解説とどのように4x4x4ルービックキューブを解くのかという概要を説明しました。