3
$\begingroup$

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 latin square.

The text of Knuth's explanation is available in this PDF, starting on page 16 (pp 6) and continuing to the next page: http://www.cs.utsa.edu/~wagner/knuth/fasc0a.pdf

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. A transversal is a sequence of ten values, one from each column that are each also in a separate row, and that have no repeated values. For example, 0859734216 is one transversal of the 808 in the original square.

I've worked out how to calculate the transversals and I come up with the exact same number Knuth describes of each starting number, so I feel confident about that part.

It seems the problem I'm having is how to combine those to make the orthogonal mate. The way I interpret his instructions is that you find one of the 808 that starts with 0 and that's the first row, then find one that starts with 1 and that's the second row. If you can find such a row for each of the ten values such that each column has exactly one of each value, that's a latin square orthogonal to the original. (The transversals already only have one of each value.)

Where his description doesn't square with the example orthogonal is that one can see by inspection the first row of the orthogonal square is not a transversal of the original square. In fact, none of the first five rows are; I stopped checking after that :)

So I must be getting something wrong.

I've worked out an algorithm for finding a disjoint set of transversals and it does indeed produce only a single solution, as Knuth claims, and it is a latin square (kind of by definition) 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?

Note: I originally submitted this question on the Mathematics site, but got no takers; I'm submitting it here thinking this might be the more appropriate site.

$\endgroup$
  • $\begingroup$ After reading this part, I have the same problems with you. I found these two papers cited by Knuth: Orthogonal Latin Squares, 1959 and Further Results, 1960. However, the methods in the papers seem complex than the transversal-finding + transversal-combining method described in the book. $\endgroup$ – hengxin Jan 18 '15 at 8:59
1
$\begingroup$

Find 10 transversals that don't intersect; these cover all the cells of the square. Fill the transversal that starts with 0 will all 0's; fill the transversal that starts with 1 with all 1's, and so on. In the example, the transversal that gives rise to the position of the 0's in the second square is 0349728615.

It seems to me that it would be clearer to use the row numbers, rather than the number stored in that row, to indicate the transversal, but of course, I've used Euler's notation above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.