一个正方形的特殊矩形铺法

Question

假设我们有一边长为S的正方形，以及N块长为X，宽为Y的矩形瓷砖。程序必须展示所有这些瓷砖可以如何排列在一个网格中，以便没有两个瓷砖相互接触。

通过展示，我指的是程序必须展示每个瓷砖左上角的坐标集合。

我尝试按照以下方式进行：

1. Find a base case where I try to place every copy with 1 square separation. For example, for 6 copies of a 1x2 tile on a 6x6 grid, the base case is

   xx_xx_
   ______
   xx_xx_
   ______
   xx_xx_
   ______
   

2. Move the last tile to possible positions.

3. Return the last tile to the base case, move the tile before the last one to the possible position. Repeat Step 2.

4. Do it back for every tile.

基本问题是我找不到行或列号之差为1但它们不相邻的情况。例如，我找不到这种情况：

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

你能建议一些东西吗？或者也许有一个更高效的算法吗？

注意：我试图在Prolog中实现它。

- Kudayar Pirimbaev

---

这些矩形可以垂直放置吗？ - VoronoiPotato

不，要使它们垂直排列，必须交换宽度和长度。 - Kudayar Pirimbaev

当您将正方形和矩形向下扩展一行（底部）和向右扩展一列（右侧），即具有一个 (S+1) 正方形和 N 个尺寸为 (X+1)x(Y+1) 的矩形时，"不接触" 条件转化为 "不重叠"。这应该更容易实现。 - coproc

Answer 1

你会发现这个问题适合使用约束编程（与你尝试使用的Prolog并不相距）：

给定S，你想要一组成对的集合A={(x,y)},其中x属于{1..S}，y属于{1..S}，x和y表示瓷砖左上角的位置，

使得对于所有(x,y)，(x+1, y)不在A中，(x+2, y)不在A中，(x+3,y)不在A中，(x,y+1)不在A中...更多的约束条件，意味着如果在(x,y)处有一个瓷砖，则不会有任何瓷砖“开始”在(x+1,y)或(x+2,y)或(x+3,y)即它们不重叠且不接触。

美妙的是，以上内容以声明方式指定了问题，然后你最喜欢的约束求解器（我选择GECODE）就可以为你找到所有的解。如果你的说明不完整，你会得到一些不期望的、相互接触或重叠的瓷砖，你可以修改说明而不必重新发明轮子。这将适用于相当大的问题实例...当你能够添加聪明的搜索树剪枝方法时，你只需要从需求开始付费，而不是发明聪明的算法，如果你需要很大的S，那么你才需要开始发明聪明的算法。

- user1666959

Answer 2

每次填充特定行时，您可以使用上一行的位掩码。例如：

如果上一行是这样的：

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
 }

我会让你自己想出实际的实现方法。

- Aravind