In your count you are missing (on purpose) the $6^{10}$ cases that are maximal too, but unreasonable because you leave holes in the pattern already during the process.

Ok, thank you. Then a reasonable trial-and-error can be done by checking $3086$ patterns. I count that as an answer to my question. If you need say $1$ minute to do one pattern by hand, then you need about $2$ days (and a good memory); so the abstract argument is worth it.

Thanks for your answer. I would expect it is less than $5 \cdot 10^8$. The only real flexibility arises when all tiles are parallel and you have $2$ in each column. There are six configurations of two tiles in a column, hence $6^{10}$ such patterns. This gives about $60$ million configurations and I do not think that there is more than $500$ million in total. However, all the ones I described are obviously not solving the puzzle -- so how many does one really have to check if one searches systematically?

@DavidHandelman: You can express stronger conditions like the Cuntz algebra relations: $xy+wz=1$ and $yx=zw=1$.

If you start out with a non-trivial finitely presented group $G$ that has no finite-dimensional representations, then you get relations that are no satisfiable in matrices but are satisfied in $\ell^1(G)$. On the other side, in a suitable form there is no such example known where one would be able to show that relations cannot be "almost" satisfied in matrices (given a suitable norm like the operator norm).

In particular, the spectrum of $dd^*+d^*d$ is a subset of $[0,1]$ if $d$ is a contraction with $d^2=0$.

@AliTaghavi: The universal $C^*$-algebra generated by a contraction $d$ with $d^2=0$ can be understood by observing that $Z=dd^*+d^*d$ is central in the $*$-algebra generated by $d$. Hence, in any irreducible representation $Z$ will act as a scalar $t \in [0,2]$. This and the observation for $t=1$ implies that the universal $C^*$-algebra (which can be decomposed over its center) is the non-unital algebra $M_2(C_0((0,1]))$ where the generator $d$ corresponds to the matrix with one non-zero entry $t \in C_0((0,1])$ in the upper right corner.

It is an exercise to see that the complex $*$-algebra generated by an element $d$ satisfying the relations above is $M_2(\mathbb C)$. Hence, any $*$-algebra contains such an element if and only if it contains a unital copy of $M_2(\mathbb C)$.

@Qfwfq: This is a question which can be answered by any competent google search and thus is not of research level. We see a lot of questions asked for the sake of asking (I believe) and this should be discouraged in my opinion.

The answer is: no. You do not need to know anything fancy, only that every element in $Sym(X)$ is conjugate to its inverse -- which is obvious from looking at the cycle decomposition. What is less trivial is Vitali's theorem, but that is not needed to exclude existence homomorphisms to $Z$.

This has been improved to $O(n^{3/2})$ (up to logarithmic factors), see arxiv.org/abs/1701.08121.

@F.Webber: It seems one has equality if and only if ${\rm rk}(A-B) \leq 1$.

$\delta=[G:H]^{-1/2}$ and I was only thinking about finite $S$.