I suggested in a comment, to look for colorings that are the same for each a, except for a fixed permutation.
Suppose the colors are given by function c(x), for x ≥ 1. And a permutation function p(i,j), where i,j ∈ [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 a, 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:
Lemma 1:If p(i,j) = p(j,i) and p(1,xy) = p(x,y) for xy ≤ n, then a coloring can be constructed.
Lemma 2: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:
abcd
bd..
c...
d...
Fill in the second row:
abcd
bdac
ca..
dc..
And complete it:
abcd
bdac
cadb
dcba
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.