一辺の長さが S の正方形と、長さ X、幅 Y の長方形タイルの N 個のコピーがあるとします。プログラムは、2 つのコピーが互いに接触しないように、これらのコピーをグリッドに配置できるすべての方法を示さなければなりません。
表示とは、グリッド内のすべてのコピーの左上隅の座標のセットを表示する必要があることを意味します。
私は次の方法でそれをやろうとしました:
すべてのコピーを 1 マスの間隔で配置しようとする基本ケースを見つけます。たとえば、6x6 グリッド上の 1x2 タイルの 6 つのコピーの場合、基本ケースは次のようになります。
xx_xx_ ______ xx_xx_ ______ xx_xx_ ______
最後のタイルを可能な位置に移動します。
最後のタイルを基本ケースに戻し、最後のタイルの前のタイルを可能な位置に移動します。手順 2 を繰り返します。
タイルごとに戻します。
基本的に問題は、行番号または列番号の差が1であるが、互いに接触していないケースを見つけることができないことです。たとえば、次のケースは見つかりません。
xx____ This tile
___xx_ and this one has a difference in row numbers 1.
xx____
___xx_
xx____
___xx_
何か提案できますか?それとも、より効率的なアルゴリズムでしょうか?
注: Prolog で実装しようとしています。