アルゴリズムNxNxNルービックキューブ

Question

を解決するために、私はどのサイズのルービックキューブのcubesolverを書きたいです。

私は3×3×3よりも大きなキューブを解くことができるかの方法を知っている：

• まず我々は、立方体の中央（フラット）フィールドを解決する必要があるので、彼らは絵を次のようになります。

• 第二に、我々はエッジ解決：

• そして最後に、我々は3×3×3キューブの解決に全体の問題を軽減することができます：

を

---

それは非常に簡単に聞こえるが、問題は、センターとエッジを解決するための方法は、キューブのサイズに依存していることです。中心と辺を解くための3x3x3のアルゴリズムは0の動きを持ち、4x4x4の方が長くなり、5x5x5の場合はもっと長くなります。

しかし、どのように、私はこれらの動きを計算することができますか？簡単な方法はありますか？

ありがとうございます！

Answer 1

あなたは順列と移動の各ソートを考慮することによって、グループの理論的には練習としてこれを見ることができます。次に、キューブのスクランブルされた順序が、利用可能な順列のいくつかの積と、もしあれば、その順序であるかどうかを調べる必要があります。

これは、これを動作させるアルゴリズム、およびそれらを実装するいくつかの非常に洗練された、とコンピュータのパッケージがあることが判明しました。パッケージと対象については、開始点はhttp://en.wikipedia.org/wiki/Computational_group_theoryです。実現可能なアルゴリズムに

つの基準はhttp://arxiv.org/pdf/math.GR/9201304.pdfでクヌースによるものです。私はこのバージョンを実装していますので、実行可能ですが、用紙は非常に密集しています。Regarding approach to solving sliding tiles puzzleの参照を参照してください。あなたが私より多くのグループ理論を知っていれば、より密度の高い論文を読むことができ、より効率的なアルゴリズムを実装することができます。オハイオ州では、問題を解決できるかどうかを最初に調べることができなければならず、理論的にはそれを解決する順列を見つけることができますが、そのシーケンスは非実用的に長くなる可能性があります。

この特定のアルゴリズムは、他のオブジェクトを適切な場所に復元しながら、置換されたオブジェクトの一部を固定しておくことができる利用可能な移動の組み合わせを探し出すという点で、上に概説したスキームとは完全に異なりません。