4

一辺の長さが S の正方形と、長さ X、幅 Y の長方形タイルの N 個のコピーがあるとします。プログラムは、2 つのコピーが互いに接触しないように、これらのコピーをグリッドに配置できるすべての方法を示さなければなりません。

表示とは、グリッド内のすべてのコピーの左上隅の座標のセットを表示する必要があることを意味します。

私は次の方法でそれをやろうとしました：

  1. すべてのコピーを 1 マスの間隔で配置しようとする基本ケースを見つけます。たとえば、6x6 グリッド上の 1x2 タイルの 6 つのコピーの場合、基本ケースは次のようになります。

    xx_xx_
______
xx_xx_
______
xx_xx_
______

  2. 最後のタイルを可能な位置に移動します。

  3. 最後のタイルを基本ケースに戻し、最後のタイルの前のタイルを可能な位置に移動します。手順 2 を繰り返します。

  4. タイルごとに戻します。

基本的に問題は、行番号または列番号の差が1であるが、互いに接触していないケースを見つけることができないことです。たとえば、次のケースは見つかりません。

xx____  This tile
___xx_  and this one has a difference in row numbers 1.
xx____
___xx_
xx____
___xx_

何か提案できますか？それとも、より効率的なアルゴリズムでしょうか?

注: Prolog で実装しようとしています。

4

2 に答える 2

3

問題が制約プログラミングに役立つことがわかります (これは、使用しようとしている Prolog からそれほど遠くありません)。

  • 与えられた S
  • x elem {1..S} と y elem {1..S} のペア A={(x,y)} のセットが必要で、x と y はタイルの左上隅を示します。
  • すべての (x,y) に対して (x+1, y) は A になく、(x+2, y) は A になく、(x+3,y) は A になく、(x,y+ 1) は A ...more 制約に含まれていません。つまり、(x,y) にタイルがある場合、(x+1,y) または (x+2,y) または (x+) で「開始」するタイルはありません。 3,y) つまり、それらは重なったり、接触したりしません。

美しさは、上記で宣言的に問題を指定すると、お気に入りの制約ソルバー (GECODE を使用します) がすべてのソリューションを見つけてくれることです。また、仕様が完全でない場合、予想外の方法で接触またはオーバーラップするタイルが得られます。仕様を変更することができ、車輪を再発明する必要はありません。これは、問題の非常に大きなインスタンスで機能します...検索ツリーを剪定する巧妙な方法を追加できる場合、大きなSが必要な場合にのみ、巧妙なアルゴリズムの発明を開始する必要があります。

于 2013-06-10T15:25:19.780 に答える
0

特定の行を埋めるたびに、前の行にビットマスクを使用できます。例えば：

前の行が次のような場合:

XX----

次に、110000 のようなビットマスクを用意します。次の行を埋めるには、ビットマスクに 1 がある場所を使用しないように注意してください。

だからあなたはこれを行うことができます：

for(int i=0;i<(1<<S);i++)
 if(i & bitmask)
 {
 //can't place tile in this fashion as few tiles of previous row touch this row's tiles
 continue;
 }
 else
 {
 //No conflicts between rows, but with in this row there could be touching tiles as in 111100
 //Use a for loop to check if the given row has no two tiles touching
 //Check if each string of 1's is of length X
 //If all is well recursively call this function to fill the next row using i as the bitmask
 }

実際の実装について説明します。

于 2013-06-10T14:21:21.357 に答える