はじめに

皆さん、こんにちは。
今回は、Pythonプログラミングの中上級エクササイズとして、ルービックキューブを自動で解いてくれるプログラムについて、紹介させて頂こうと思います。

なぜ、そんなことを！？

昨今、プログラミングや機械学習などが注目されていると思いますが、その実力向上に向けたエクササイズとして、ルービックキューブの解読が適切だと思ったためです。

Pythonとは

Pythonというプログラミング言語について、ご存知でない方は、以下にその辺りの話を記載しておりますので、よければ参考にして下さい。

ルービックキューブとは

ルービックキューブとは、すごく有名な立体パズルです。
6面の立方体の、各面が3x3の9マスに分割されており、任意の列を回転させて、各面を同一色に揃えればゴールとなります。
ご存知の方の方が多いかと思います。

wikiに詳しく書いてありますので、興味のある方は参照してみて下さい。

「適当には解けない」という特性

ルービックキューブは、実は、適当には解けないという特性があります。
「ルービックキューブ　適当に回す」などで検索をすると、以下の記事などが見つかります。
盤面の組み合わせが、4325京2003兆2744億8985万6000通りもある為に、適当に回してゴールに辿り着く可能性は、ほぼゼロなのだそうです。

また、以下の記事によれば、どんな盤面からでも、20手以内でゴールに辿り着けるという研究結果があるそうです。

ルービックキューブの回し方の選択肢は、回転軸の「①ロール・②ピッチ・③ヨー」毎に、回す列が3つずつあり、かつ、回す方向が手前と奥の2パターンあることから、3 x 3 x 2 = 18通りです。

ここで、盤面の組み合わせ数が多いことから、回し方が異なる場合には、盤面が合致しないとの仮説を立ててみます。
仮に、10手で解ける状態から、適当に10回の手数だけ回したとして、唯一解である回し方を選択できる確率、即ち、ゴールに辿り着ける確率は、「18の10乗＝3兆5704億6722万6624」分の1という確率になります。
なるほど、確かに解けなそうです…。

実際にプログラムにて、ランダムにキューブを回転させるシミュレーションも行ってみたのですが、やはり解けませんでした。

「解き方がある」という事実

「え、じゃあ、どうやって解くのよ…？」と、私自身、途方に暮れてしまいそうになりましたが、実は解き方があるようでした。
バンダイナムコグループ系列の1社である、メガハウスさんが解法をサイトに上げてくれています。
非常に手順を追いやすくなっているものです。

解き方を見ていくと、徐々に足場を固めながら、ゴールに一歩一歩近付いていくような手順となっており、このことからも適当には解けないことが伺えました。
一度うまく進捗できた盤面を崩さないように、他の盤面を揃えていくとイメージです。

私もサイトを見ながらであれば、盤面の色を揃えることができました。
尚、上記のリンクで紹介している解き方は、LBL法という解き方だそうで、他にも色々と解き方はあるんだそうです。

プログラムで解くには

メガハウスのサイトが紹介しているルービックキューブ解法に沿って、手動にて、ルービックキューブを何度か解いてみると、回し方にパターンがあることが分かってきます。
また、盤面の状況毎に、選択すべき回し方のパターンが異なることも分かります。
プログラムで、ルービックキュープを解く場合には、盤面の状況を認識しながら、適切な回し方を実践する必要があります。
或いは、幾つかの盤面においては、共通の回し方なども存在する為、ある程度はラフに共通する回し方を実践しても良いかと思われます。

また、そもそも、ルービックキューブの状態を、3x3x6の要素を持つ配列にて管理する必要があります。
そして、ルービックキューブを回す動作を実践するために、それら配列が上手く連動する必要があります。
立体上の表面の色を、配列の管理値に反映させるのは、例えば、それ用の関数を用意して、テストをしながら整合性の確証を得る必要があります。

また、盤面の認識をする上で、ルービックキューブ全体を横に回転させたり、ゴロリと転がすような動作も、時に必要となります。
それについても用意しておくと、人間が多角的にキューブの状態を確認する動作を、プログラムによるシミュレーション上でも再現ができることでしょう。

ルービックキューブを自動で解いてくれるプログラム

ここに私が実装した例を載せていきます。

（続く…）