PATS problem and tile set generation

In order to produce a surface with a complex template for potentially guiding the attachment of functional materials, an interesting problem in tile-based self-assembly is the Patterned self-Assembly Tile set Synthesis (PATS) problem. The PATS problem is concerned with finding the minimal tile set which will self-assemble into a given 2-D pattern of colors (where tile types are assumed to be assigned colors) and was introduced by Ma and Lombardi in . In Göös and Orponen presented an exhaustive branch-and-bound algorithm which works well for finding exact solutions to patterns of sizes up to 6 × 6, and approximate solutions for larger patterns. In , Lempiäinen, Czeizler, and Orponen modified the previous algorithm to be more efficient (but still require exponential time). In , Czeizler and Popa proved that the PATS problem is NP-hard, and in Seki examined the parameterized version of the problem, c-PATS, in which any given pattern is guaranteed to contain at most c colors, and showed that 59-PATS is NP-hard by using a 3-SAT reduction.