CODEWITHSUNDEEP
algorithm
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

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:

  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.

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.

Upvotes: 3

Views: 640

Answers (2)

Aravind
Aravind

Reputation: 3179

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.

Upvotes: 0

user1666959
user1666959

Reputation: 1855

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

  • given S,
  • you want a set of pairs A={(x,y)} where x elem {1..S} and y elem {1..S} and x and y denotes the top left corner of your tile,
  • such that for all (x,y) (x+1, y) is not in A and (x+2, y) is not in A and (x+3,y) is not in A and (x,y+1) is not in A ...more constraints, meaning that if you have a tile on (x,y) no tile 'starts' on (x+1,y) or (x+2,y) or (x+3,y) ie they don't overlap and don't touch.

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.

Upvotes: 3

Related Questions