不規則な形状の格子を塗りつぶす

Question

私は、12個の特定のテトリスのようなピースを6×10グリッドに塗りつぶす方法がいくつあるかを決定するアルゴリズムを構築したいと考えています。

すべてのピースはそれぞれ5つのブロックで構成されており、自由にミラーリングおよび回転できます。それらはすべてグリッドに（重なりなく）フィットしなければならず、余白を残してはいけません。

さらに、アレンジメントは、既存のアレンジメントのミラーリングまたは回転イメージでない場合にのみ、別個のものと見なされます。

私はそれが自分の行列だ各回転ステップを与えるために選択した、とT-ブロックの表現は次のようになります。

私の最初のアプローチは強引だった

[ 
    0, 0, 0, 0, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 1, 0, 0, 
    0, 0, 1, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 1, 0, 0, 
    0, 0, 1, 1, 1, 
    0, 0, 1, 0, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 1, 0, 0, 
    0, 0, 1, 0, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
], 
[ 
    0, 0, 0, 1, 0, 
    0, 1, 1, 1, 0, 
    0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0 
] 

。 1つの図形で開始点を1つずつ試してから、左上隅から順に1つずつ他のすべての図形に合わせようとします。

しかし、誰かがこの問題に対してより良いアプローチをしているのか不思議です。

Answer 1

一般的には、特定のケース（例：すべてが2x2のキューブ）でない限り、ブルートフォースしかできないと思います。あなたはしかし、いくつかのトリックを使用することができます。

• 唯一の「S」形状がある場合、あなたは一般性を失うことなく、それは左上の象限にあると仮定し、そして4で結果を掛け、プラスおそらくいくつかの例することができますそれは軸上にあるためです。

• 「タイルを拾い、すべての位置を再帰的に試してみる」とは、「最初に利用可能な位置を選んで、それをカバーするすべての可能なタイルを試してみてください。

• 4で割り切れないサイズの穴がある場合は、破損する可能性があります。

• 穴がある場合、計算を分割することができます（すべてを埋める方法の数=穴を埋める方法の数*残りの部分を埋める方法の数）。

多分もっと多分です。