CODEWITHSUNDEEP
algorithm
Hugo Hismans
Hugo Hismans

Reputation: 173

Exact cover problems. Tetrominos in a geometric figure

I'm trying to use algorithm X to solve a problem. I think that the problem can be represented as an exact cover problem, but I'm not sure.

Here it is: Does a set of tetrominos can be fit in a specific geometric figure. example: enter image description here

The exemple is two "duominos" which need to be fit in the rectangle. I see that the pentaminos problem is a famous example for the exact cover problem. But here I'm not trying to "exactly cover" the rectangle, I want to know if my piece will fit in the rectangle, and of course, in which configuration.

For the pentaminos problem, the figure's elements is the universe, and the collection of set is the pentaminos. But here's my issue.... For my problem i don't want to absolutly fill all the element of the figure, i just want to fit all my piece in my figure.

My idea was to consider the piece as the univers (because I want to "cover" all my piece) and the element of my figure as the set of collection.

Maybe it's really stupid and impossible, but does someone have an idea how to build the matrix needed in the algorithm X for this problem?

Upvotes: 1

Views: 410

Answers (1)

Matthew Pope
Matthew Pope

Reputation: 7679

Tetromino as the Universe

Suppose we have a T shaped tetromino and a 2x3 area that we wish to fit it into. We can determine the partial covering sets by assigning a number each part of the tetromino and a letter to each possible covering set.

A [1][2] 3      B [ ][1]      C  [1][ ]
  [ ][4]          [4][2]        4[2][ ]
  [ ][ ]          [ ][3]         [3][ ]

Then, in your matrix, you would set A1 to 1 because box A contains tetromino part 1. You would set A3 to 0 because box A does not contain tetromino part 3.

    1  2  3  4
A [ 1  1  0  1 ]
B [ 1  1  1  1 ]
C [ 1  1  1  0 ]

You will end up with box_area * piece_orientations rows in your matrix, which you could reduce by taking advantage of the symmetry of the box and tetromino. However, you don't need to use Algorithm X. You just need to check and see if there are any rows that have no zeros, and that will be your solution

Box as the Universe

If you use the box as your universe, Algorithm X will try to find a combination of tetrominos that will fully cover the box, which is not what you are trying to do.

Algorithm X is not well suited for this task. The algorithm is designed to find a suitable combination of sets to cover a universe. You are trying to find a single set (box) that covers the universe (tetromino).

Your problem is really more of a packing problem than an exact cover problem. If you were trying to fit multiple tetrominos into a box, then it could be a packing problem or an exact cover problem, depending on whether you allow any empty space in the box.

Upvotes: 1

Related Questions