特殊的矩形矩形平铺
假设我们有一个边长为S的正方形，并且有长度为X和宽度为Y的矩形块的N个副本。程序必须显示所有这些副本可以排列在网格中的方式，以便两个副本不能相互接触 。
通过显示，我的意思是它必须显示网格中每个副本左上角的一组坐标。
我试图按照以下方式做到这一点：
找到一个基本案例，我尝试将每个副本放在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中实现它。
你会发现这个问题适用于约束编程（这与Prolog不太相似，你试图使用它）：
美的是，通过上面你声明性地指定了问题，然后你最喜欢的约束求解器（我会去GECODE）去找到所有的解决方案。 如果你的规格没有完成，你会得到以意想不到的方式接触或重叠的瓷砖，你可以修改规格并且不必重新发明轮子。 这将适用于相当大的问题实例...当您可以添加巧妙的修剪搜索树的方法时，如果您需要大S的话，您只需开始创造聪明的算法。
每次填充特定行时，您都可以为上一行使用位掩码 。 例如：
如果前一行是这样的：
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
}
我会让你弄清楚实际的执行情况。
链接地址: http://www.djcxy.com/p/40221.html上一篇: A particular tiling of a square with rectangles
下一篇: Combinatorial Game. Who wins if both players play optimally