# Is there an efficient algorithm for solving tiling puzzles?

As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how to place two copies of T and two copies of P inside R with no overlap.

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).

Tiling figures of the plane with two bars shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.