java - ルービックキューブのアルゴリズムをコーディングするのが最も簡単ですか？

Question

ルービックキューブを解くためにJavaでコーディングする比較的簡単なアルゴリズムは何でしょうか。効率も重要ですが、二次的な考慮事項です。

Answer 1

適切な解決策が得られるまで、ランダムな操作を実行します。最も簡単なアルゴリズムと最も効率の悪いアルゴリズム。

Answer 2

私が見つけた最も単純な自明でないアルゴリズムはこれです：

http://www.chessandpoker.com/rubiks-cube-solution.html

コードを書くのはそれほど難しくはありません。Yannick M.の回答で言及されているリンクも良さそうですが、「クロス」ステップの解決策は、私にはもう少し複雑かもしれないように見えます。

あなたが見てみたいと思うかもしれない多くのオープンソースソルバーの実装があります。これがPythonの実装です。このJavaアプレットにはソルバーも含まれており、ソースコードが利用可能です。ダウンロード可能なソースコードを備えたJavascriptソルバーもあります。

Anthony Gatlinの回答は、このタスクに対するPrologの適切性について優れた点を示しています。独自のPrologソルバーを作成する方法についての詳細な記事があります。それが使用するヒューリスティックは特に興味深いものです。

Answer 3

チェックアウトしたいかもしれません：http：//peter.stillhq.com/jasmine/rubikscubesolution.html

3x3x3ルービックキューブを解くためのアルゴリズムのグラフィック表現があります

Answer 4

あなたの質問はJavaに関連していると思いますが、実際には、Prologのような言語は、ルービックキューブを解くような問題にはるかに適しています。これはおそらくクラス用だと思いますが、ツールの選択に関しては余裕がないかもしれません。

Answer 5

BFS（幅優先探索）を実行することでそれを行うことができます。実装はそれほど難しくないと思います（グラフのカテゴリで最も単純なアルゴリズムの1つです）。キューと呼ばれるデータ構造を使用してこれを行うことにより、実際に作業するのは、BFSツリーを構築し、指定された条件から目的の条件へのいわゆる最短パスを見つけることです。このアルゴリズムの欠点は、十分に効率的ではないことです（変更を加えなくても、2x2x2立方体をソルバーする場合でも、必要な時間は約5分です）。しかし、あなたは常にスピードを上げるためのいくつかのトリックを見つけることができます。

正直、MITの「アルゴリズム入門」というコースの宿題のひとつです。宿題のリンクは次のとおりです：http：//ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps6.pdf。彼らはあなたがそれを視覚化し、あなたが不必要な努力を避けるのを助けるのに役立ついくつかのライブラリを持っています。

Answer 6

参考までに、このJava実装を確認できます。-> ルービックキューブを解くために2相アルゴリズムを使用します。そして、このコードを試してみましたが、それも機能します。

Answer 7

1つの解決策は、考えられるすべてのルートを同時に実行すると推測することです。それはばかげているように聞こえますが、ここに論理があります-可能なスクランブルの99％以上が20回未​​満の動きで解決可能になります。これは、膨大な数の可能性を循環させても、最終的にはそれを実行することを意味します。基本的に、これはスクランブルされたキューブとして最初のステップを実行することで機能します。次に、最初のキューブで可能な移動ごとに、新しいキューブを変数に格納します。これらの新しいキューブのそれぞれについて、同じことを行います。可能な移動のたびに、それが完了しているかどうかを確認し、完了している場合はそれが解決策です。ここで解決策があることを確認するには、各ルービックキューブに、その段階に到達するために行われた移動を示す追加のデータが必要になります。