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).
However, it is more important to give a condition when a coloring can be constructed:
Lemma 1:If p(x,y) = p(v,w) for xy = vw, then a coloring can be constructed.
Lemma 2:For each n a permutation exists such that p(x,y) = p(v,w) for xy = vw.
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 condition p(x,y) = p(v,w) for xy = vw becomes relative weaker 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.