Algorithm for sorting with constraints
The question of whether we can solve this problem without violating any rules is a set cover problem.

In particular, the universe is $U=\{1,2,\dots,30\}$, and each possible tuple $t_i$ that follows all the rules corresponds to a set $S_i \subseteq U$.  In this way, we get many sets $S_1,S_2,\dots,S_n$.  We want to know whether there is some 10 of these sets whose union is all of $U$.  That's the set cover problem.  There are well-known hardness results and approximation algorithms for the set cover problem.



Now let's introduce the opportunity to violate some of the rules.  Associate to each tuple $t_i$ a cost $c_i$.  If the tuple $t_i$ follows all the rules, there is no cost for using that tuple: $c_i=0$.  If the tuple $t_i$ violates some of the rules, we'll set $c_i$ to denote the cost of those violations (for instance, if each rule that is violated costs \$1, then $c_i$ can be set accordingly).  In this way we get a collection of sets $S_1,S_2,\dots,S_n$ with associated costs $c_1,c_2,\dots,c_n$ for each of them.

Now our goal is to find some 10 of those sets whose union is $U$, and where the sum of their costs is minimized.

This can be formulated as an integer linear program (ILP).  In particular, we'll introduce $n$ integer variables $x_i$; the intended meaning is that $x_i=1$ means that $S_i$ is one of the 10 sets that were selected, and $x_i=0$ means $S_i$ was not selected.  Now we want to minimize

$$\sum_i c_i x_i,$$

subject to the constraints

$$\sum_{j \in S_i} x_i \ge 1 \text{ for each $j=1,2,\dots,30$}$$

(where the sum is over all $i$ such that $j \in S_i$) and $0 \le x_i \le 1$.  Now you could throw any ILP solver at this problem and see what solution it turns up.