perl - 定義済みの形状でグリッド/マトリックスを埋める

Question

質問に 2 票の賛成票が投じられたことをうれしく思います。混乱を避けるために、ここで質問を言い直します。

問題は、mxn グリッド/マトリックスを、穴のないランダムだが事前定義された形状で埋める方法です。定義済みの形状には変数 k があり、これは形状が構成されているブロックの数です。各ブロックは正方形で、グリッドの正方形 (つまり、1x1 グリッド) と同じサイズです。図形は、グリッドに収まるように回転できますが、縮小または拡大することはできません。k は 1 回のラウンドで変化しません。つまり、応答スクリプトを実行している間、m、n、および k は変化しません。スクリプトを 2 回目に実行すると、それらの 1 つまたはすべてが変更される可能性があります。たとえば、初めて、k=4、m=10、n=20 で応答スクリプトを実行する場合があります。スクリプトが終了し、出力が出力されます。2 回目は k=3、m=6、n=10 とします。m かける n と積変調 k がゼロ (mxn % k = 0) に等しいことを保証して、それらが数学的に互いに適合することを確認します。さて、もう 1 つの条件: 1

スクリプトは、プリセット k のプールからランダムな形状でグリッドを埋める必要があります。k=2 の場合、事前定義された形状は 1 種類だけで、2 つのブロックが一緒になります。回転なしで考えると、横と縦の2種類があります。k=4 の場合、グリッドは基本的に Tetris ブロックでいっぱいになります。つまり、全部で 7 種類の事前定義された形状 (それぞれが回転し、最大 20 種類を作成できます) です。k=5 の事前定義された形状は何ですか? まだわかりません。k=5 のすべての形状を見つけることは難しくないため、答えはそれを計算するか、ハードコードすることができます。

解が限られている場合、乱数は必要ありません。たとえば、m=2、n=2、および k=4 です。または m=1、n=4、k=2。他の方法はありません。ランダムではありません。

グリッドのどこにも穴を残すことはできません。mxn と mxn%k=0 の多くのグリッドには、穴のな​​い解があると思います。直感的には合理的に聞こえますが、数学的にはわかりません。m または n が k の倍数である場合、(すべての直線棒の) 解があることが保証されます。

理想的には、k は k<10 のような小さい整数である必要がありますが、2 から 5 の範囲は許容されます。より単純な場合、Tetris にはよく知られている 7 つの形状 (ITOLJSZ) が付属しているため、4 などの固定の k をここで使用できます。

できればPerlで解決策を探しています。パイソンでも大丈夫です。プログラムの実行には、毎回 m、n、k が必要です。ここでも、m,n,k を mxn%k=0 に適合させます。

Perl で試してみた自分の努力で、k=3 のいくつかのケースを解決でき、エッジ/コーナーのシングルトン (穴) のためにいくつかのケースで失敗しました。ブロックがシングルトンになるかどうかを確認する良い方法が必要です。私のテキスト出力は次のようになります (m=4、n=9、k=3)。もちろん、この種の形式または意味のある任意の形式を使用できます。

AABB
ACCB
DCEE
DFFE
DFGH
IGGH
IIJH
KKJJ
KLLL

最高のソリューションを授与するために、100 ポイントの報奨金を設定します (2 つの賛成票に感謝します。現在、107 の評判があります)。

ご意見ありがとうございます。

Answer 1

ソリューションの設計に関するドライブバイの考えを次に示します。

すべてのピースを配置する必要がない場合は、一連の直線または正方形ができるまでスキップすることができます. そこにあるアルゴリズムは非常に簡単に思いつくでしょう - 1行または2行を埋めるためのピースの構成を見つけ出し、それを繰り返します。(nm mod k != 0) の場合、解はありません。それ以外の場合は、レイアウトできる一般的な一連のルールがあると思います。たとえば、(m mod k = 0) または (n mod k = 0) の場合、直線を使用できます。それらについて考えるのは楽しいでしょうが、私はそれらをあなたに任せます。

実際、あなたの問題を読んでみると、2 <= k <= 5 と書かれていることがわかりました。これは、2、3、および 5 が素数であるため、非常に簡単です。数論では、nm mod a素数 p = 0 の場合、n または m は p で割り切れる必要があるため、k = 2、3、5 の場合、n、m のどれが k で割り切れるかを見つけて、行または長さ k の直線を含む列。k = 4 の場合、n、m のいずれかが 4 で割り切れる (この場合は同じ戦略を使用する) か、どちらも 2 で割り切れる場合は一方が (4x + 2) である必要があり、各列に入力するだけです直線で上に上げ、最後に正方形を配置します。

与えられたすべてのピースを配置する必要がある場合は、ビンを埋める必要がある (nm/k) 個のピース​​を最初から知っています。これにより、NP 困難なビン パッキング問題の標準的なケースが得られますが、優れたヒューリスティック ベースのアルゴリズムが存在します。よくあるのは、各図形を最初に開いた場所に配置する貪欲なヒューリスティックです。

ただし、問題には正確な解決策が必要です。つまり、「十分に近づく」だけでは十分ではありません。バックトラッキング アルゴリズムを使用することもできますが、より良いアプローチは、グリッドの有効な位置の状態空間で双方向検索を行うことです。ある位置を目標位置として定義し、そこから後方に移動します。これには、ランダムな (実際にはそうではありません - 適切なヒューリスティックを見つける必要があります) 位置からピースを取り出すことが含まれます。次に、別の位置を開始位置として定義し、ピースを挿入することを伴う前方への移動を行います。2 本の木が交差したら停止し、その道を進みます。

対処しなければならない問題は、与えられたピースでグリッドを埋めることができない場合があることです。たとえば、am = 2、n = 2、k = 4 の場合、ピースは 1 つしか得られず、それが正方形以外のピースである場合、状態空間を埋めることはできません。

Answer 2

この問題は確かに NP 困難 (ナップザックのようなもの) です。つまり、一般的に解決する唯一の方法は、実行可能なすべてのブロック配置の一部をチェックするアルゴリズムです。これには、ジグソー パズルで作業するのと同じ方法でピースを組み立てる分枝限定検索のようなものが必要になりますが、各パズル ピースの任意の数のコピーがあることを除きます。穴を開けないとピースが収まらないポイントに到達したら、バックトラックします。擬似コード:

place one piece to make the initial blob B containing no holes

procedure branch_and_bound
loop
  for each shape S
    for each position P that S can be added 
            to B without creating an unfillable hole
       place S in P to enlarge B
       if puzzle is complete throw DONE!
       call branch_and_bound

位置 P を見つける方法に焦点を当てているように聞こえます。これにアプローチする簡単な方法の 1 つは、B に接触する各空のグリッド スクエア E を検討し、S を構成する各スクエアを E に配置して、オーバーラップを引き起こすすべてのケースを破棄することです。 B. 埋められない穴を回避するには、B によって埋められないスペースが連続したままであることを要求するだけです。埋められていないスペースの「島」が発生しないようにします。空の正方形を選択し、DFS または BFS を実行して埋められていない可能性のあるすべてのスペースに触れてから、残っている塗りつぶされていない正方形をチェックすることで、島を簡単に検出できます。

ヒューリスティックを使用して、図形を選択してピースを配置する順序をガイドできます。

実際、このアルゴリズムは、ヒューリスティックが優れているか、ブロックが自明な形状 (またはその両方) でない限り、すぐに役に立たなくなります。これが NP 困難問題の性質です。ヒューリスティックがしばしば優れていたとしても、惨めに失敗する問題が必ずあります。これは NP 困難問題の性質でもあります。

多くのパズル ソルバーで使用される手法は、限られたソリューション セットのみを考慮することによって複雑さを軽減することです。ここでの例は、m = Ap および n = Bp の場合、ある A 整数 A、B、p に対して、apxp 平方の解を見つけるだけで明らかに十分です。これをタイル状に並べて、より大きなソリューションを得ることができます。膨大な数の同様のアイデアを想像できます。

Answer 3

穴の問題に関しては、これを解決する簡単な方法があるはずです... 3! (k<=9 の場合は ;))

説明させてください、すべてのブロックは別のブロックまたは 2 つに隣接しているだけでなくEMPTY SPOTS、k の形状に関しても隣接k*2+2していk=1 -> 4, k=2 -> 6 .... k=9 -> 20 ます。 .length 位置がわかりますよね？マトリックスでは、両側に1つずつ移動して、それが空のスペースであるかどうかを確認できます..その（空白の）位置に一時的に注意してください.kをそのように概説すると、空のスペースの数が明確になりますは上記の計算値以下です。

等しい場合、k に穴をあけることはできず、次に進むことができます。少ない場合は、どれだけ少ないかを確認します。1 つを逃した場合は L 字型になり、2 つを逃した場合は、U 字型または T 字型になります (特殊なケース k=9 an S)、あなたの準備はいいですか

3 つ以上ミスした場合は、さらに調査する必要があります。次に、隣接するブロックについて一時的にメモした空白の位置をすべて確認します。そのようなすべての空白に対して数が 3 以下の場合、穴がなく、1 つ以上の空白に隣接するブロックが 3 つあるとすぐに続行できます。ただし、k には穴があります。

k=10 の場合、これを正しく行うのは困難ですが、これらの単純なルールを 9 つまで使用することで、k オブジェクトの穴を防ぐことができます。

申し訳ありませんが、私は perl に精通していません。それ以外の場合は、単なるヒントではなくコードを提供していました ;)

したがって、どの k-object にも穴が開いていないので、どのm*n%k=0グリッドでも解けることが保証されます。常に心に留めておかなければならないことが 1 つだけあります。それは古典的なドミノ チェスの質問です*。常に 1 つのコーナー/エッジから開始してグリッドを埋め、最後のピースをグリッドに挿入するまで空白を残さないでください。 、それらの状況を回避するために。

*domino-chess question は、ボード上に 2 つのチェスの駒がある場合、チェスフィールド (8x8) に 31 個のドミノ (2x1 ブロック) を並べることができるかどうかの質問です。(答え: 1 つが白地に、もう 1 つが黒地にあればできます。それ以外の場合はできません)