4

小さなパズルを解くためのアルゴリズムについて考えています。インターネットとスタックオーバーフローでさまざまなアルゴリズムを見つけましたが、いくつかの点で私のニーズを満たしていません:

  • 私のパズルのピースは一色で、画像/パターン/...はありません
  • パーツのすべてのエッジは、図のように 8 つのオプションのいずれかになります (たとえば、パーツを ABCD、cdab、cBBb、ADcb と記述できます)。これ以上複雑な構造などはありません
  • 私が解きたいパズルはそれほど大きくなく、8x8より大きいものはありません
  • コーナー/エッジ部分には特定のエッジがありません。結果はきれいな長方形にはなりません。
  • すべてのパズルが解けるわけではありません
  • 部品は回転できますが、回転できません
  • すべてのパズルパーツはユニークです

パズルのパーツ例

4

1 に答える 1

2

したがって、私の出発点は単なる力ずくです。ピース 0 を (0,0) の位置に置き、残りのピースを (0,1) に収まるまで試してから、(0,2) に移動します。など。どのステップでも、そのスペースに収まるピースがない場合は、以前に収まったピースを取り出して、その正方形に新しいフィットを見つけようとします.

それを証明することはできませんが、2 つの制約があるピースを評価する可能性が高くなるようにピースを埋める (つまり、より大きな正方形、2x2、3x3、4x4 を移動する代わりに) より速く終了するのではないかと思います。行を行うだけではありません。

動物の頭と尻尾が付いた四角いピースがある 3x3 パズルを思い出します。A最適化の 1 つは、ペア間のミスマッチをカウントアップすることです。自分よりも多くのペアを持っている場合は、パズルの端に位置する傾向があるaことがわかりますAが、8x8 パズルでは、より少ないエッジを持っています。内比なので、差はあまり役に立ちませんし、それをアルゴリズムに統合するための良いアイデアもありません。

（編集）もっと考えてみると、数えることで最初に得られるのは、解決策が存在しない場合の早期終了だと思います。NxN グリッドには2*N*(N-1)、満たさなければならない内部一致があります。min(A,a) + min(B,b) + min(C,c) + min(D,d) < 2*N*(N-1)解決策が存在しないことがわかっている場合。

（編集2）min（）を持つつもりだったところにabs（）がありました。おっと。

于 2013-02-27T21:05:06.773 に答える