  Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum
tile set to uniquely self-assemble a given rectangular color pattern. For $k
\ge 1$, $k$-PATS is a variant of PATS that restricts input patterns to those
with at most $k$ colors. We prove the {\bf NP}-hardness of 29-PATS, where the
best known is that of 60-PATS.

Computational Complexity