Combinatorial and Computational aspects of Tilings

Recent developments in the study of anisohedral shapes, particularly the work of Joseph Myers, have been the product of exhaustive computer searches through various polyforms (edge-to-edge assemblies of unit squares, regular hexagons, or equilateral triangles). I have reimplemented this work using a different approach that provides independent confirmation of previous results and allows generalization to previously unexplored classes of polygons.

Rather than treating a shape as a collection of occupied cells on a regular lattice, I observe that a polyform with no internal holes can be completely described by a sequence of characters representing unit length steps taken from a finite language of directions. I define the concept of a polysnake as a closed self-avoiding walk in the plane composed of unit length steps each parallel to an edge of a regular n-gon for some fixed n. By choosing a suitable set of directions as the underlying alphabet, polysnakes can be represented by the same "boundary string" approach as polyforms.

With this string representation in hand, I have implemented tests for isohedral tiling, anisohedral tiling, and proofs of non-tiling that treat these properties as problems in formal languages. Although the implementation is not yet as powerful or efficient as past work, I have already confirmed results for smaller polyforms and identified two previously unknown 4-anisohedral polysnakes.