Enumeration of Tiling Patterns

We show an efficient algorithm for finding all solutions of an exact cover problem. Several practical tasks including floor planning and layout designing of electric circuits can be solved as exact cover problems. Our method is 10,000 times faster than baseline methods. Moreover, we can store the set of all solutions by compressing it and then efficiently picking up solutions that satisfies additional constraints. The key of the technology is the use of data structure that represents the set of all solutions as a directed graph. Our technology supports users to find good tiling patterns. For example, it helps to find layouts of electric circuits with low power consumption and floor plans of a condominium that matches to the owner’s requirement.

Please click the thumbnail image to open the full-size PDF file.