Separate tile of a square with rectangles

Question

Suppose we have a square with side lengths S and N of copies of a rectangular tile with length X and width Y. The program should 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 should show the set of coordinates of the upper left corners of each copy in the grid.

I tried to do it as follows:

• Find the base case when I try to place each copy with 1 square division. For example, for 6 copies of a 1x2 tile in a 6x6 grid, the base case

  xx_xx_ ______ xx_xx_ ______ xx_xx_ ______ 

• Move the last fragment to possible positions.

• Return the last tile to the base case, move the tile to the last to a possible position. Repeat step 2.

• Do this for each tile.

Basically the problem is that I cannot find cases where the difference in the number of rows or columns is 1, but they do not 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 offer something? Or maybe a more efficient algorithm?

NOTE. I am trying to implement it in Prolog.

Answer 1

You will find that the problem lends itself to programming restrictions (which is not so far from Prolog that you are trying to use):

• taking into account S,
• you need a lot of pairs A = {(x, y)}, where x elem {1..S} and y elem {1..S}, and x and y denotes the upper left corner of your tile,
• such that for all (x, y) (x + 1, y) is not in and (x + 2, y) is not in and (x + 3, y) is not in A and (x, y + 1) is not is in A ... more restrictions, which means that if you have a tile on (x, y), then no tile starts (x + 1, y) or (x + 2, y) or (x + 3, y), i.e. they do not overlap and do not touch.

The beauty is that with the above you declaratively indicated the problem, and then your favorite constraint resolver (I would go with GECODE) went and found all the solutions for you. And if your specification is not completed, you get tiles that unexpectedly find or overlap, you can change the specification and not reinvent the wheel. This will work for fairly large instances of the problem ... when you can add smart ways to trim the search tree, you only need to come up with smart algorithms if you need a large S. Type of payment on the go.

Answer 2

You can use the bitmask for the previous line each time you fill out a specific line. For example: If the previous line is similar: XX ---- Then you have a bitmask, such as 110000. To fill in the next line, see That you are not using places where there is 1 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 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 is of length X //If all is well recursively call this function to fill the next row using i as the bitmask } 

I will tell you about the actual implementation. If you have more questions, ask.