I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal square.
The square he uses in his example is this one:
0 1 2 3 4 5 6 7 8 9
1 8 3 2 5 4 7 6 9 0
2 9 5 6 3 0 8 4 7 1
3 7 0 9 8 6 1 5 2 4
4 6 7 5 2 9 0 8 1 3
5 0 9 4 7 8 3 1 6 2
6 5 4 7 1 3 2 9 0 8
7 4 1 8 0 2 9 3 5 6
8 3 6 0 9 1 5 2 4 7
9 2 8 1 6 7 4 0 3 5
and its orthogonal mate is this one:
0 2 8 5 9 4 7 3 6 1
1 7 4 9 3 6 5 0 2 8
2 5 6 4 8 7 0 1 9 3
3 6 9 0 4 5 8 2 1 7
4 8 1 7 5 3 6 9 0 2
5 1 7 8 0 2 9 4 3 6
6 9 0 2 7 1 3 8 4 5
7 3 5 1 2 0 4 6 8 9
8 0 2 3 6 9 1 7 5 4
9 4 3 6 1 8 2 5 7 0
I've checked it, and it is indeed orthogonal. I just can't figure out how he produced it from the instructions he gave.
The general procedure he describes is to calculate all the transversals and then find a set of those that are disjoint, and that makes an orthogonal square.
I've worked out how to calculate the transversals and I come up with the exact same number he describes of each starting number, so I feel confident about that part. The first one is 0859734216, for example.
It seems the problem I'm having is how to combine those to make the orthogonal mate. One can see by inspection that the first row of the orthogonal square is not a transversal of the original square, so I must be getting something wrong.
I've also worked out an algorithm for finding a disjoint set of transversals and it does indeed produce only a single solution, as Knuth claims, but it neither matches this solution nor is the resulting matrix orthogonal to the first.
Does someone understand the Parker method well enough to point out where I've gone wrong in the procedure?
If we overlap the Latin squares, for any $i \in \{0,1,\ldots,9\}$, the copies of the symbol $i$ in the second Latin square identify a transversal in the first Latin square. (It's not the rows that give the transversals, but the symbols.)
In the given example, we have:
So, for example, the dark blue cells correspond to the positions of the $5$s in the second matrix, and identify a transversal in the first matrix. Similarly for the other colors.
So the second Latin square identifies $10$ transversals in the first Latin square. These transversals are disjoint, in that they do not share a cell. So the $100$ entries are divided into $10$ transversals (each containing $10$ entries).
Any set of $10$ disjoint transversals will give an orthogonal Latin square: if the entry in cell $(i,j)$ occurs in the $t$-th transversal, we set $M(i,j)=t$.
One technical issue that might arise is the way you've written transversals (e.g. $0859734216$): it gives the symbol in the $j$-th column. You'll need to compute the cells these symbols lie in to generate the orthogonal square.