Assemblable Interlocking Polyominoes
Author(s)Andres Bejarano, Christoph Hoffmann

Interlocking Polyominoes sets are required for representing certain protein folding, self-assembly models and even computational models. However, finding an interlocking design is not an easy task; it is a time consuming process which requires many trials and errors. It is proved that the interlockedness of polyominoes with an arbitrary number of squares is PSPACE hard. Our current research is focused on the study of assemblable interlocking polyominoes (there exist an assembly order of the pieces such that the intended design is achievable and the pieces interlock themselves). The obtained results show that it is possible to have an interlocking boundary based on S-shaped pieces. Moreover, it was observed that the assemblability feature is possible when three consecutive S-shaped pieces are found in the interlocking boundary.