ExcelVBAでルービックキューブを揃える【プログラム編】
プログラム手法としては、総当たりで探索する方法と、解法の手筋を再現する方法に分類されると思います。
今回のプログラムは、前者の方法に属しますが、ルービックキューブを総当たりで揃えるというのは、現実的には不可能と言えるでしょう。
というのもルービックキューブの組み合わせは約4325京通りあると言われており、これらを総当たりするには膨大な時間がかかってしまい実用性はありません。
いろいろトライしてみたのですが筆者のスキルでは到底およびませんでしたので、今回はPythonで作られたルービックキューブを解くプログラムを参考にしてVBAで作ってみました。
（というか焼き直しなのですが、、、汗）
という事で、今回のプログラムは、以下の 「@7y2n（Kentaro Nishiさん)」のページを参考にしています。
ルービックキューブを解くプログラムを書いてみよう(前編:キューブを操る実装)
ルービックキューブを解くプログラムを書いてみよう(中編:IDA*探索)
ルービックキューブを解くプログラムを書いてみよう(後編:状態のindex化, Two-Phase-Algorithm)
今回の内容は、プログラミングに興味がある方と、単純に使って遊びたいという方がいらっしゃると思いますので、2つの記事に分けています。
こちらの記事は、「プログラミング編」で、プログラミングの内容について述べています。
出来上がったツールの使い方については「使い方編」をご覧ください。
プログラムのダウンロード
解答後のファイルは約18MBと大きめのファイルとなります。立ち上げにも少々時間がかかります。
ルービックキューブを揃えるプログラミング
プログラミングの詳細につきましては、前述の参考ページをご覧いただくとして、こちらでは概要を解説したいと思います。
本プログラムの構想は、排除できる組合せを出来るだけ排除（枝刈り）し、尚且つインデックス化やTwo-Phase-Algorithmと呼ばれる手法を用いて、現実的な時間で解答できるように工夫されています。
インデックス化とは、一手ごと計算を行うのではなく、結果を数値化して扱う方法になります。
簡単に言うと二次配列として結果をあらかじめ用意しておいて取り出します。（九九の計算みたいなものです。）
また、Two-Phase-Algorithmは、中間的な完成状態を定義して、その状態から扱う手数を少なくして完成を目指すという方法になります。つまり２段階で完成を目指します。
今回のプログラムの特徴として、あらかじめ計算結果を遷移表（換算表）として用意しておく事になるのですが、これが非常に大きい表になります。ブック内には10個程のシートを抱えており、大きいものでは数千行ものデータがあり、そのため、Excelファイルを読み込むのに少々時間がかかります。Excelファイル自体、約18Mバイトもあります。
（尚、10個の遷移表シートは書き変え防止のため非表示にしています。）
ただ、この事で処理が遅いと言われるVBAでも、数秒程度で解答を示す事が出来るようになっています。
（一応、無限ループとならないよう3分程度でメッセージが出て中断できるようにしてあります。）
尚、今回のプログラムでは、最短の手筋を見つけるものではなく、最初に探索でヒットしたものを表示するようになっています。
参考にした記事では、より最短の手筋に近づけるような手法が紹介されていますが、そこまでは追い込んでいません。
PythonからVBAへ移行
解法のためのプログラムは焼き直しなのでPythonからVBAへの移行が大変なだけでした。
標準モジュールのModule2に書かれたプログラムは遷移表（換算表）を作るためのプログラムなのですが、遷移表の結果をシートに展開しましたので、遷移表を作るプログラムは実行する必要はありません。ただ、この事でファイルサイズが大きくなっています。
一応、参考のためにプログラムは残しています。
オリジナル部分
参考にしたPythonのプログラムはCUIで実行する仕様となっています。
私としては、手元にあるルービックキューブを適当にスクランブルした状態でも、展開図に色を当てはめれば解答を得られるようにしたかったので、インターフェースを用意しています。
インターフェースは展開図の色指定を、ユーザーフォームからできるようになっています。
スクランブルされた実際のルービックキューブから展開図に、配色通りに色を並べれば、その状態から解法を得られるようになっています。
使い方については、「使い方編」をご覧ください。
キューブの定義やプログラム上の記譜法について
プログラミングに入る前に、ルービックキューブの状態をプログラム上で把握するために、回し方や各キューブの位置などを記号化する必要があります。
まずは、ルービックキューブの正面を決めます。ここでは緑の面を正面に持つ事にしています。
向きに優劣は無いのですがどれかに決めなければいけませんので、ここでは以下のような展開図を固定とします。中の数値は後程説明しますので、配色に注目してください。
ちなみにこの展開図の配色は国際基準となっています。日本基準ですと、黄色と青が入れ替わる形になります。
変更は「設定」シートで行えます。もしお手持ちのルービックキューブが日本基準の配色であれば変更する必要があります。やり方は「使い方編」で解説しています。
操作について
回し方（操作）については、以下のページを踏襲しています。ただ使わない回し方もありますので、一応説明します。
キューブの操作記法については、3x3x3 回転記号 （tribox） を参考にしてみてください。
上記の展開図で、「↓L 」となっているのは、緑の面を正面に持って、
左（Left）の縦の列を下向きに回転させるのを正方向としている事を示しています。
この動作を90度行うのを ” L “ と表記します。
更に90度回転させて正面の緑面の左側の楯列が裏側になった状態を” 2L “と表記します。
更に90度回転させると、矢印とは反対方向に90度回転させたのと同じになりますが、これを” L’ “と表記します。 アポストロフィは反対方向という意味で使います。
つまり左縦方向の回転は、” L ” ” L2 ” ” L’ ” の3種類のみになります。
正面右縦方向に関しては「↑R 」となっており、先程とは矢印が逆になります。
つまり正方向は上向きに回転させたときが ” R ” となり、
下向き（逆方向）に回転させたときは ” R’ “となります。
正方向の向きが反対になるので注意してください。
なお、キューブの中央を回す、“M” “S” “E” に関しては本プログラムでは使用しません。
これは、中央のキューブの位置が変わってしまっては都合が悪い事と、
両側を同じ方向に回せば同じような回転を再現できるためです。
本プログラムでは、“U’ L B2 F2 R”などと表記されますが、全て緑の面を正面にした時の操作になります。持ち換えは行いません。
各キューブ面の記法について
※キューブ面の表記方法については、プログラムの検証などで使用するものなので自動解答として使用したい場合は理解しなくても大丈夫です。
少々複雑なので、単にプログラムを使用したい場合は読み飛ばして構いません。
キューブには、中央キューブ、辺キューブ、角キューブの3種類があります。
中央キューブに関しては、その場で回転しているだけで位置は変わりません。
中央キューブの番号がその面を示す番号になります。
角キューブは、3つの面の向きが入れ替わることがあります。
記法は “2,0” “2,1” “2,2” となります。
最初の 「2」 は、角キューブに割り振られた、0～7までの値.。
後半の 「0」,「1」,「2」 は側面に振り分けられた3種類の値になります。
辺キューブに関しては、2つの面の向きが入れ替わることがあります。
記法は “6,0” “6,1”などと書きます。最初の 「6」 は辺キューブに割り振られた値で0～11までの値。
後半の 「0」 ,「1」 は側面に振り分けられた2種類の値になります。
振り分けられた値ですので、”6,0″は白。”6,1″は緑。と変化する事はありません。
各キューブの配置を示す記法
各キューブの配置を示す記法は、cp,co,ep.eo で記述しています。
cp は Corner permutation の略だそうです。コーナーキューブ（角キューブ）の場所を示しています。
co は Corner orientation の略で、コーナーキューブ（角キューブ）の向き(ひねり)の情報を示しています。
ep は Edge permutation の略で、cpと同じく エッジキューブ（辺キューブ）の場所を示しています。
eo は Edge orientation の略で、エッジキューブ（辺キューブ）の向きの情報を示しています。
汚くて申し訳ありませんが、角キューブは以下のように3つの面で構成された8個になります。
角(コーナー)キューブ cp,co
角キューブは cp,co で構成されています。
以下は、キューブが揃った状態での記法です。
cp 0 1 2 3 4 5 6 7
co 0 0 0 0 0 0 0 0
ep 0 1 2 3 4 5 6 7 8 9 10 11
eo 0 0 0 0 0 0 0 0 0 0 0 0 ここから、” L “ を1回回転させると以下のようになります。
cp:4 1 2 0 7 5 6 3
co:2 0 0 1 1 0 0 2
ep:11 1 2 7 4 5 6 0 8 9 10 3
eo:0 0 0 0 0 0 0 0 0 0 0 0 coは角キューブの向き（ひねり）を表しますが、3面なので回転なし、時計回り、反時計回りでそれぞれ 0,1,2 が割り当てられます。
時計回りか、反時計回りかは上面・下面を基準にしています。
角キューブの向きに関しては、以下のナンバリング図と見比べるとわかりやすいです。
赤数字で指定された場所がcp配列の順番になります。
キューブが回転する事で、この数値上に他の角キューブが移動してきます。
例えば、上記の例では、cp の 0番目に、「4」のキューブが来ています。
そしてナンバリング図の「0」は、[4,1] が来ています。後半が「1」の時は、反時計回りと見るので、co は「2」となります。
このようにナンバリング図のある位置ので照合して、
後半が「0」の時は正位置で co = 0 。
「1」の時は向きが反時計回りで、co = 2 。
「2」の時は向きが時計回りで、co = 1 。
となります。
辺(エッジ)キューブ ep,eo
辺キューブは、 ep,eo で構成されています。
辺キューブは2面で構成されているため正方向と逆方向があります。
ep と eo に関しては以下のナンバリング図を基準にします。
黒数字で書かれた番号が辺キューブの順番になります。
以下のような展開図で ep, eo を見ていきましょう。
cp:0 1 3 7 4 5 2 6
co:0 0 1 2 0 0 2 1
ep:0 1 6 10 4 5 3 7 8 9 2 11
eo:0 0 0 1 0 0 1 0 0 0 0 0 辺キューブ4番目のナンバリング図「3」のところに ep 「10」 が来ています。
値を見ると[10,1] となっていますので、向きを示す eo は 「1」となります。
同じ緑の面なのに向きが反転していると捉えるのでおかしな感じがしますが、
ナンバリング図「10」を見ると、緑面でない下面（黄色)に「10」が振られていますので、逆向きと見なす事になります。
実際のプログラムでは、cp,co,ep,eo の値が揃った状態を見て完成したと捉える事になります。
わかりずらい考え方なのですが、これが解法のための大事な仕組みとなっています。
ただ、プログラミングに興味のない方は意識する必要はありません。
この事が理解できないと自動解答が使えないという事ではありませんのでご安心ください。
” L, R, U, D, F, B ” などの回転操作を理解してもらえれば大丈夫です。
Two-Phase-Algorithm
「Two-Phase-Algorithm」は二段階で完成させるアルゴリズムになります。
まず、第一段階である程度の完成を目指します。「ある程度」とは第二段階で完成させるためのお膳立てになります。
第二段階では、手数を限定させて完成できるようにします。
こうする事で、探索回数を減らす事ができ、完成までの時間を短縮できるようになります。
第一段階
第一段階では、以下の条件がクリアされていれば完成になります。
・ co が全て 0
・ eo が全て 0
・上面・下面に挟まれた中間層の辺キューブメンバーが中間層内に揃っている
回転に関しては、“L,R,U,D,F,B,L’,R’,U’,D’,F’,B’,L2,R2,U2,D2,F2,B2”と全ての操作を総当たりして探索します。
探索に関しては上記の条件がクリアした状態で終了しますので、最短の手数という事ではありません。
第二段階
第二段階では、完成を目指しますが、操作は以下のように限定されたものを使用します。
“U, U2, U’, D, D2, D’, L2, R2, F2, B2”
操作の種類が減ることで、探索時間を短縮することができます。
こちらも条件がクリアされた段階で終了しますので、最短の手数という事ではありません。
プログラムが出力する解答について
プログラムは殆どの場合、数秒で解法を出力します。
解法は2段階なので2行となります。
B' U' L' D2 R' D2 F' R' B
B2 R2 例えば、上記のような解法が出力された時、１行目の最後の B と、２行目の最初の B2 は、
B + 2B なので、Bを3回まわしたことになり、B を逆方向に1回まわした B’と同じになります。
このような時は、以下のように書き変えて「検証」ボタンを押せば結果は同じになります。
B' U' L' D2 R' D2 F' R' B'
R2このような事が起こってしまう原因は2回の工程に分けて解法を見つけている事に起因します。
少ないスクランブルで多めの解答
上記と同じような理由ですが、例えば揃った状態から、” R ” のみスクランブルした状態で解答を得ようとすると、” R R2 ” という答えが返ってきます。これは ” R’ ” と同じなのですが、1回スクランブルしたにもかかわらず、解答の操作は 2回となってしまいます。
同じように ” L R ” と2回スクランブルした場合は、” R L R2 L2 ” という答えになります。
ただ、回数は多くなりますが揃った状態となります。
VBAプログラミング
本プログラムは、フォームが2つ、標準モジュールが4つ、クラスモジュールが2つで構成されています。
フォーム
ユーザーフォームは、2つで
UserForm1は、「InputColor」ボタンで表示されるユーザーフォーム。
UserForm2は、「検証」ボタンで表示されるユーザーフォーム
をそれぞれ配置しています。
標準モジュール
Module1は、「InputColor」ボタン関係のコードと、「Reset」ボタン関係のコードを掲載しています。
Module2は、遷移表を作るためのコードを掲載しています。
Module3は、「Random」ボタン、「Search」ボタン関係のコードを掲載しています。
Module4は、「検証」ボタン関係のコードを掲載しています。
クラスモジュール
CRubicCubeクラスは、ルービックキューブの状態を操作したり、解答を見つけるためのクラスです。
CStackクラスは、文字列のスタック構造を実現するクラスで、CRubicCubeクラス内で使用されます。
プログラムの内容について複雑なので細かく解説はできませんので、コメントやソースコードから理解していただければと思います。
内容に関する質問などは、メールを頂ければ可能な限りお答えします。
実際のツールの使い方についてはこちらのページを参照してください。
コメント