Description: Tiling problems in general are about perfectly filling a finite or infinite region of the plane by using non-overlapping copies of some given shapes called tiles. A wide range of such problems exist. The goal in this topic is to implement a software solving a specific class of tiling problems. Decide if a perfect tiling exists, if the regions and tiles all consist of squares of a rectangular grid. The focus is on being as general as possible: support multiple tiles and arbitrary regions, possibly with additional features like restrictions on tile count, rotation, placement, and finding imperfect solutions. Editing the problem itself and showing the result shall be implemented in some user-friendly manner, like graphically. Care shall be taken to investigate the problem itself and decide whether it would require too much memory or runtime, based on the solution approach chosen. Dynamic programming will likely be needed to be learnt during the work.
Supervisor: András Éles