As a part of a project, I am troubled with the following problem:

Given an l x w rectangle, where 1 <= l, w <= n as well as n polygon-shaped dominoes d1, d2, d3, ..., dn (each domino does not necessarily have just a length and width -- it is a polygon), I want to cover as much of the l x w rectangle as possible using the given dominoes.

The dominoes that are placed into the rectangle don't necessarily need to be small enough to fit inside of the rectangle, so we need to be able to recognize this and not use those dominoes in invalid places.

Now suppose I hypothetically have an O(n^k) algorithm that solves the following problem:

"Given the list of dominoes, the rectangle dimensions (l and w) and some value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and the algorithm returns false otherwise."

Now using this algorithm, is it possible to find a tiling of the l x w rectangle that covers as many squares as possible (i.e. a maximal orientation) in polynomial time? I want to figure out if it is possible and how fast it would be.

You can find the maximal value of x in polynomial time. But then finding which dominoes to use and their orientation is difficult.

Some ideas (but I might be completely wrong):

• Represent the squares as nodes in a graph?

• Maybe something clever with DP?