Rectangular tileability and complementary tileability are undecidable

Jed Yang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Does a given set of polyominoes tile some rectangle? We show that this problem is undecidable. In a different direction, we also consider tiling a cofinite subset of the plane. The tileability is undecidable for many variants of this problem. However, we present an algorithm for testing whether the complement of a finite region is tileable by a set of rectangles.

Original languageEnglish (US)
Pages (from-to)20-34
Number of pages15
JournalEuropean Journal of Combinatorics
StatePublished - Oct 2014

Bibliographical note

Funding Information:
I am grateful to my advisor Igor Pak for proposing these problems, helpful conversations, reading this paper, and providing invaluable feedback. I also thank the anonymous referees for attentive reading of the paper and useful comments. The work is supported by the NSF under Grant No. DGE-0707424 .


Dive into the research topics of 'Rectangular tileability and complementary tileability are undecidable'. Together they form a unique fingerprint.

Cite this