プログラミング言語によるルービックキューブ (3x3x3) ソルバ実装まとめ

2015-10-07 ルービックキューブ Tech ルービックキューブコメントを受け付けていません。

本記事では、ルービックキューブ 3x3x3 のソルバ (解法プログラム) の実装をまとめます。同時にスクランブルジェネレータ (スクランブル生成プログラム) も紹介します。

Contents

1 ソルバとスクランブルジェネレータの関係
2 3x3x3ソルバ/スクランブルジェネレータ紹介

ソルバとスクランブルジェネレータの関係

紹介の前に、ソルバとスクランブルジェネレータの関係を簡単に述べておきます。
パズルのスクランブルジェネレータはソルバに強く依存しています。というのも、ソルバが存在すればランダムステートなパズルの状態から完成状態に至る手順Sを求めることが可能となり、Sの逆手順S’が完成状態からそのランダムステートへのスクランブルシーケンスとなるためです。逆手順を求めるのは一般に容易 (自明) であるため、ソルバが確立されればスクランブルジェネレータも同時に完成できる、と言うことができます。
よってルービックキューブパズルのソルバとスクランブルジェネレータには強い関係があります。

今回紹介する全てのソルバのアルゴリズムは、現在3x3x3ルービックキューブの最も効率的な解求アルゴリズムである “Kociemba’s Two-phase Algorithm” にもとづいています。コンピュータとルービックキューブ解求アルゴリズムについては以前記事を書いたのでよろしければそちらをご覧ください。

ルービックキューブをアルゴリズムで解くということ

terabo.net

ルービックキューブを解くアルゴリズムについて書きます．この記事では具体的なアルゴリズムの話はありません．（情報工学的アプローチでの見方です．ルービックキューブを解くアルゴリズムは「群論」とも深く関わりがありますが，私は情報工学系の人間なので...

https://www.terabo.net/blog/solving-cube-by-algorithms/

それでは、ルービックキューブ (3x3x3) ソルバ / スクランブルジェネレータをプログラミング言語ごとに紹介していきます。

3x3x3ソルバ/スクランブルジェネレータ紹介

言語ごとに紹介します。自分が知っている限りすべて列挙しています。新しいのを発見したら随時追加します。
ソルバとスクランブルジェネレータの分類も一応付けていますが、前述のように相互変換が自明なのでそんなに意味はないです。

Java

Cube Explorer

[ソルバ/スクランブルジェネレータ] 現在コンピュータでのソルバアルゴリズムのスタンダードとなった “Kociemba’s Two-phase Algorithm” の Kociemba氏によるJavaでの実装です。

Solve Rubik’s Cube with Cube Explorer : kociemba.org/cube.htm

min2phase

[ソルバ/スクランブルジェネレータ] Chen Shuang氏 (WCA ID: 2008CHEN27) によって実装されたJavaによる “Kociemba’s Two-phase Algorithm” の実装です。オリジナルと比較してパフォーマンスが改善されているようすです (多分)。 WCA公式スクランブルプログラム TNoodle での内部でこのプログラムが使用されています。

cubing/min2phase : github.com/cubing/min2phase

C / C++

cube20

[ソルバ] God’s Number is 20 というルービックキューブ (3x3x3) God’s number (= 「いかなる状態でも、最多でもN手で各面が揃った状態に戻せる」このときのN) が20手であることを示したプロジェクトで使用されたプログラムです。ソルバはCWEB言語 (拡張子.w) 実装されています。CやC++に変換するためにコンパイルする必要があります。
Lucas Garron (WCA ID: 2006GARR01) 氏による f2lfast というプロジェクトのソルバはこのプログラム (C++版) を使用しています。また、dwalton76/cube20 では C++ に変換されたソースコードが公開されています。