A particular tiling of a square with rectangles

Suppose we have a square with side length S, and N copies of rectangular tile with length X and width Y. The program must show all the ways in which these copies can be arranged in a grid so that no two copies can touch each other .

By showing, I mean that it must show the set of coordinates of upper left corners of every copy in a grid.

I tried to do it in the following way:

xx_xx_
______
xx_xx_
______
xx_xx_
______

Basically the problem is that I cannot find the cases where the difference in row or column numbers is 1 but they don't touch each other. For example, I cannot find this case:

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

Can you suggest something? Or maybe a more efficient algorithm?

NOTE: I try to implement it in Prolog.

You'll find that the problem lends itself to constraint programming (which isn't that far from Prolog what you are trying to use):

The beauty is that with the above you declaratively specified the problem, and then your favourite constraint solver (I'd go with GECODE) goes and finds all solutions for you. And if your specification is not complete you get tiles which touch or overlap in unexpected ways, you can modify the specification and don't have to reinvent the wheel. This will work for quite large instances of the problem...when you can add clever ways of pruning the search tree, you only have to start inventing clever algorithms if you need large S. Sort of pay as you go.

You can use a bitmask for the previous row each time you fill a specific row. For example:

If previous row is like:

XX----

Then have a bitmask like 110000. To fill next row, see that you don't use the places where there are 1's in the bitmask.

So you can do this:

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
 }

I will let you figure out the actual implementation.

上一篇: 算法挑战合并集合

下一篇: 特殊的矩形矩形平铺