I suggested in a comment, to look for colorings that are the same for each <i>a</i>, except for a fixed permutation.

Suppose the colors are given by function c(x), for x &ge; 1. And a permutation function p(i,j), where i,j &isin; [1..n]. Where i is the index of the permutation, and j the index of the permutation of the color.

If n = 4 and the coloring starts with abcd, then p(1,1) = a, p(1,2) = b, p(1,3) = c, p(1,4) = d, p(2,1) = b, p(2,2) = d.

If the coloring is the same for each <i>a</i>, then we get the following equation:

c(an) = p(c(a),c(n))

From this it follows, that the permutation must p(i,j)=p(j,i).

More important, is to reverse this:

<b>Lemma 1:</b>If p(i,j) = p(j,i) and p(1,xy) = p(x,y) for xy &le; n, then a coloring can be constructed.

<b>Lemma 2:</b>For each n a permutation exists such that p(i,j) = p(j,i) and p(1,xy) = p(x,y).

To see how this works, for n = 4, we start the following permutation matrix:<br/>
abcd<br/>
bd..<br/>
c...<br/>
d...<br/>

Fill in the second row:<br/>
abcd<br/>
bdac<br/>
ca..<br/>
dc..<br/>

And complete it:<br/>
abcd<br/>
bdac<br/>
cadb<br/>
dcba<br/>

From this construct the coloring:
abcdxaxcdxxbxxxa

By each prime number > n (the x values in the coloring), you can choose a color, but you have to continue with the permutation of that color.

Lemma 1 is trivial to prove, because it follows that c(xy) is c(yx).

I haven't proven lemma 2 yet. For n is 1,2,3,4, there is only 1 permutation matrix. For n = 5 there are a few. The percentage that the condition p(1,xy) = p(x,y) fills in the matrix becomes smaller for larger n. So, I don't think it is a problem to create such permutation matrix (also given the number of different Sudokus). Of course, lemma 2 needs to be proven properly.