4

假设我们有一个边长为 S 的正方形，以及 N 个长度为 X 和宽度为 Y 的矩形瓷砖的副本。程序必须显示这些副本可以在网格中排列的所有方式，这样两个副本就不会相互接触。

通过显示，我的意思是它必须显示网格中每个副本的左上角坐标集。

我试图通过以下方式做到这一点：

  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，
  • 你想要一组对 A={(x,y)} 其中 x elem {1..S} 和 y elem {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 时才需要开始发明聪明的算法。随用随付。

于 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 回答