Python と 2 辺幅優先検索を使用して 2x2 ルービック キューブを解きました。
MIT 6.006 のプロジェクトからインスピレーションを受けました。独自にゼロから作成しました。
https://youtu.be/ZHxLO6fubaU
キューブ API、アルゴリズム、GUI をゼロから作成しました。 6 つの辺のそれぞれに 4 つの異なる正方形があり、結果として 24 個の正方形になります。さらに、立方体を構成するコーナーピースは合計 8 つあり、それぞれに 3 つの方向があるため、24 個の正方形に沿っています。
各辺の 24 のサブセクションのそれぞれを、形式として「xyz」を使用した文字列として定義しました。ここで、x はすぐ向かい合う色で、y と z はその角の立方体の周りを時計回りの順に進みます。
私は立方体の周りを一周し、解決された状態を表す固定番号を各面に割り当てました。たとえば、0、1、2、3 は正面を向いた白い面の 4 つの部分で、0 は左上、残りは時計回りの順です。
キューブ上で実行できる動きが 12 あります。右、左、上、下、前、後ろ。これらのそれぞれには反時計回りの動きもあるので、6x2 = 12 の動きになります。これら 12 個のそれぞれが立方体の半分、つまり 12 個の正方形を操作します。これらの動きを行うために、サブスクエアが元の位置から次の位置まで時計回りに回転する 6 つのそれぞれについて辞書を作成しました。素数を実行するには、キーと値を切り替えるだけです。
立方体の可能な順列は膨大な量であるため、この問題を解決するのは特に困難です。サブスクエアは 24 個あり、24P24 = 24! となります。これは 10^23 の大きさです。状況によってはこれより少ない場合もありますが、その数は依然として膨大です。
ツリーを作成するには、それぞれの動きを実行し、非常に大きくなる動きからすべての動きを実行する必要があります。 12^ 木の高さ。訪問した位置の辞書を作成することでこのサイズを制限することができ、以前に訪問した順列に対するアクションがやり直しにならないようにしました。
私は片側 BFS の作成から始めましたが、分岐ツリーが大きくなりすぎるため、再帰制限に達してしまいます。これを修正するために、開始ソリューションと終了ソリューションから交互にブランチを作成することで、両面 BFS を使用しました。ツリーを作成し、反対側がすでにポイントを見つけているかどうかを確認します。存在する場合、接続ポイントが返されます。
このすべての間、各ノードはその親 (前方分岐の場合) または子 (後方分岐の場合) を保存します。たどったルートを見つけるために、接続ノードから親を再帰的に見つけてから、そのポイントのすべての子を見つけました。これにより、スクランブルから解決までの一連の位置が得られました。
このプロジェクトでは、グラフ理論と幅優先探索を使用しました。 Python と再帰の能力を向上させました。また、これより長い時間がかかる解決策を見つけることができなかったため、2x2 立方体を解くための最大手数は11 手手であることが実験的にわかりました。
tkinter ライブラリを使用してプロジェクトの GUI を作成する方法を学習しました
