Rubik's Cubeの解法研究のためにソフトウェアを開発する

Youtubeで視聴者にルービックキューブを送ってもらって、 2x2x2からはじめて3x3x3を左右のセクシームーブだけでよちよち解けるようになったが最後、 ソルブする悦びを知ってしまい、 次の段階に行くために 競技用のキューブGAN356M Liteというのを買ったのがだいたい二週間前くらい。

それから簡易CFOPを学びはじめ、 ルービックキューブをひたすら回すために諏訪湖に行き、湖を見ながらひたすらキューブを回したところ、 思い出しながらのよちよちだが簡易CFOPで解けるようになってきた。 簡易CFOP法

簡易CFOPというのはOLLとPLLを4Lookで揃える簡易解法のことだが、 さらに速くソルブすることを考えた場合、OLLはともかく PLL21種を全部覚えることは不可避に見える。 しかしこれを本当に丸暗記するのは厳しいし、無意味に思う。 それに、意味づけ出来た方が血肉をなり、長期的に覚えていられるだろう。

PLLというのは本質的に一体何をしているのだろうか?

簡易CFOPでおれは、TパームとYパームというのを使っている。

  • Tパーム: (Tr-U' Sn-F')(F Ja-U' Tr-F')
  • Yパーム: (F Ja-U' Tr-F')(Tr-U' Sn-F')

見るとわかるが、 これらは実は手順を入れ替えただけであり、 しかも各シーケンスは下二層を保存する。つまり、OLLなのだ。

こう考えると一つの仮説にたどり着く。

他のPLLも実は、こういう感じでいくつかのOLLの組み合わせによって 実行出来ないだろうか? しかも各シーケンスは典型的なシーケンスであるセクシームーブやスレッジハンマーなどで 構成されている方が、覚えやすさとエルゴノミクスの観点から優れる。

では、どうやって調べればよいだろうか?

  1. まず、典型的なシーケンスの組み合わせによるOLLを網羅的に調べる。これを基本OLLと呼ぼう
  2. そしてそれらのOLLの組み合わせによってPLLが実現出来ないか調べる

PLLは21種しかない。つまり、仮に基本OLLが7種あり、その2つの組み合わせで実現出来るならば、 7C2=21になる。もしかしたら、これが数学的に証明出来るんじゃないか?という直感がある。 もし、これが正しいならば、たった7種類のOLLを覚えるだけですべてのPLLが1Lookで解けることになる。 エレガントだ。

しかし、この探索アプリケーションを実装するためには、そもそもルービックキューブを実装した ライブラリが必要となる。しかし、探してみたところおれがほしいものはなかった。 そこで、ルービックキューブアプリケーションを実装するための基盤ライブラリを作ることにした。

Rubik Master

おれの考察によると、ルービックキューブは少なくとも54x54の置換行列によって表すことが出来る。 揃った状態を単位行列として、ある状態からそれに至る操作は、現在の状態の逆行列となる。 これは、転置することによって得られる。

操作は、高速でなければいけないが、行列は各行各列に1が1つしかないため、 掛け算の計算量はO(54)であり、しかもギャザーなので並列処理出来る。 また、メモリは54バイトで済む。

テストはどうだろうか?ランダムに操作列を生成して、要素ごとに逆順でかけた時に単位行列になることは事実だ。 また、同じ操作を4回したら単位行列になったり、セクシームーブを6回繰り返したら単位行列になることも事実だ。 代数ライブラリを参照実装として比較することでもテスト出来る。 これらの性質を利用して、QuickCheckやproptestを使って網羅的にテスト出来そうだ。

ここまで考察したあと、一気に2日で初版を作りあげた。 しかしまだやらないといけないことはある。

1つは、回転記号列をパースするパーサ実装であり、 もう1つは、WebGLによるルービックキューブのコンポーネントである。これはYew Componentとして実装したい。 もしやってみたい人がいたら、Issueに書いておいたからやってみてほしい。

ルービックキューブは非常に良い趣味だ。