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

raspberry-pi-cube-solver

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

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

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

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

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

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

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

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

Java

Cube Explorer

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

min2phase

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

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++ に変換されたソースコードが公開されています。

Cube Solver

[ソルバ] 先日、Raspberry Pi のブログで公開されていた機械式ソルバのプログラムです。 詳細はよくわからないのですが、おそらく Raspberry Pi 上でソルバが動いているものだと思われます。 Kociemba’s Algorithm を C と Python で実装しています。

chample

[ソルバ/スクランブルジェネレータ] 私もオリジナルはJavaで書かれた Kociemba’s Algorithm を C で実装し直しています。

Javascript (node.js)

jsss

[ソルバ/スクランブルジェネレータ] Javascript Solver/Scrambler Suite です。 Webページでも手軽にソルバ/スクランブラを利用することができます。 高速に動作します。

Mark 2

[スクランブルジェネレータ] WCA公式プロジェクトです (でした)。歴史的背景はよくわからないですが、 公式スクランブラが TNoodle に移行したときの候補の1つだった? 現在は開発されていないようすです (last commit が 2012年6月のため)。

twophase.js

Kociemba’s Algorithm (God’s Number is 20 のやつ) を javascript で実装するとディスクリプションには書いてありますが、まだ中身がありません。今後追加されるかは不明です。

Python

Cube Solver

[ソルバ] C言語の節で書いた Cube Solver (Raspberry Pi のやつ) は Python でも実装されています。

とりあえず、以上です。

この記事をシェアする:Tweet about this on TwitterShare on FacebookShare on Google+Share on TumblrEmail this to someone

コメントを残す

名前を入力しなくてもコメント投稿可能です (匿名ユーザとして表示されます)。