0

次のルールでパズルを解く手順を見つけるプログラムを作成しようとしています。

  • 4x4 グリッド内の任意の色のセットが与えられた場合、同じ数の色で終了パターンに一致するように試みます。
  • 色は交換されませんが、水平または垂直に回転します。

{わ、わ、わ、わ}

に回転することができます

{W、W、W、B}

{B、W、W、W}

{わ、わ、わ、わ}

  • パズル全体は 16 ステップ未満で解決できます。

パズル自体のデータを保存する方法はすでにわかっていますが、ステップを表示できるソリューションを見つけることについてどのように進めるかについて苦労しています。深さは 16 ステップに制限されているので、力ずくでやってみることは問題ありませんが、パターンを確立する方法がわかりません。

これは、ルービック キューブを解くのに似ています。私はすでに次のリソースを見てきました。

  • stackoverflow.com/questions/34656587/solving-rubiks-cubes-for-dummies/34656726#34656726

  • stackoverflow.com/questions/5563671/solving-rubiks-cube-programmatically

  • amzi.com/articles/rubik.htm

  • chessandpoker.com/rubiks-cube-solution.html

そして15の数の問題

  • stackoverflow.com/questions/3621623/how-to-programatically-solve-the-15-moving-numbers-puzzle

この質問をできるだけ明確にするために、a) 手順を保存/印刷し、b) 手順を最小限に抑えるソリューションを見つけるには、どのような方法がよいでしょうか?

4

1 に答える 1

0

写真なしで木を説明することはできないと思います。

次の開始パターンがあるとします。

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

これは、ツリーの最上位ノードになります。レベル 0。

これで、考えられるすべての水平方向と垂直方向の回転を行います。最初に右に水平に。

[B, W, W, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[B, W, W, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, B, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[B, W, W, W]

左に水平。

[W, W, B, W]
[W, W, W, B]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, B, W]
[B, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[W, W, W, B]
[W, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, W]
[W, W, B, W]

垂直上

[W, W, W, B]
[B, W, W, B]
[W, W, W, W]
[W, W, W, B]

[W, W, W, B]
[W, W, W, W]
[B, W, W, B]
[W, W, W, B]

垂直ダウン

[W, W, W, B]
[W, W, W, B]
[W, W, W, W]
[B, W, W, B]

[W, W, W, B]
[W, W, W, B]
[B, W, W, B]
[W, W, W, W]

2列目と3列目はすべてWなので、上下上下の2パターンしかありません。

レベル1で全部で12パターンあります。

私たちは非常に整然と移動しました。私たちの動きにはランダム性はありませんでした。右に水平、左に水平、垂直上、垂直下。

ここで、レベル 1 の 12 個のパターンのそれぞれを取得して、16 個のパターンを生成します。レベル 0 とレベル 1 のパターンに一致するパターンを保存する必要はありません。

生成および保存されたパターンは、レベル 2 を構成します。

レベル 16 に到達するか、解決策が見つかるまで、各レベルの生成を続けます。ツリー レベルから重複を削除しているため、レベル 16 の理論上の最大値である 16 から 16 乗ノードに達することはありません。

移動数が最小のソリューションが複数ある場合は、レベルを終了します。

于 2016-01-22T08:54:19.860 に答える