Wikipedia:Reference desk/Archives/Mathematics/2023 July 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 27

Finding diagonal-complete Latin squares

Some mathematicians call Latin squares which have distinct elements in their diagonals "diagonal-complete Latin squares", such as this order-4 one:

0123
3210
1032
2301

which has diagonals 0231 and 2013.

I understand that there are no order-3 ones as one diagonal has repeated elements:

012
201
120

This PDF gives an order-5 one:

01234
23401
40123
12340
34012

but I can't understand the algorithm to construct diagonal-complete Latin squares. Can someone please explain in simple terms? For example, how can I build an order-6 one?

Thanks,
cmɢʟee⎆τaʟκ 19:56, 27 July 2023 (UTC)

A standard method is by backtracking. The top row can obviously be filled with 0 1 ... n−1. Given an incomplete square, the process tries to fill the next empty cell, where the first position is (0, 0) and position (i, j) is succeeded by (i, j+1) except when j = n−1, in which case the successor is (i+1, 0). The numbers above it in the same column and to the left on the same row are impossible, and if the empty cell is on a diagonal, the numbers above it on that diagonal are also impossible. If not all numbers in the set {0, 1, ..., n−1} are impossible, fill the designated empty cell with the least of the possible numbers and proceed. Otherwise, the process needs to backtrack to the last filled position and try the next allowed number for that position. (For example, if before the possible numbers were {4, 6, 7}, so the cell is filled with a 4, it is now clear that 4 is also impossible, so the process should try 6. If all possibilities are exhausted, the process needs to clear the cell and backtrack likewise to the position before this one.

If at some point all n² cells are filled, a solution has been found. But if the process backtracks to the top row, no solution is possible.

This backtracking method gives the lexicographical;ly first solution (if any). For order 5 it gives us

0 1 2 3 4

1 3 4 2 0

4 2 1 0 3

2 0 3 4 1

3 4 0 1 2.

For order 6,

0 1 2 3 4 5

1 2 0 5 3 4

4 3 5 0 2 1

3 0 1 4 5 2

5 4 3 2 1 0

2 5 4 1 0 3

Before the process found this, it tried the number 1 for cell (2, 2) and got as far as

0 1 2 3 4 5

1 2 0 5 3 4

4 3 1 2 5 0

5 0 4

but then got stuck on cell (3, 3) and had to backtrack all the way back to (2, 2).

 --Lambiam 00:36, 28 July 2023 (UTC)

Thanks a lot for the clear explanation, @Lambiam: pity that backtracking is the simplest solution for it. Cheers, cmɢʟee⎆τaʟκ 18:36, 30 July 2023 (UTC)

Maybe there are also simple solutions for orders divisible by 2 or 3, yet to be discovered.  --Lambiam 19:06, 30 July 2023 (UTC)

The algorithm given in the linked PDF works for n relatively prime to 6; it fails for n=6, 8, 9, 10, 12, ... . For n=7 you get

0 1 2 3 4 5 6

2 3 4 5 6 0 1

4 5 6 0 1 2 3

6 0 1 2 3 4 5

1 2 3 4 5 6 0

3 4 5 6 0 1 2

5 6 0 1 2 3 4

Basically add the column number (starting at 0) and twice the row number, then take the remainder when you divide by 7. As far as I can tell, the PDF doesn't tell you how to do n=6, so you might have to do a backtracking approach as given by Lambiam. --RDBury (talk) 02:39, 28 July 2023 (UTC)

Thank you very much for your clear explanation, @RDBury: I understand it now. Cheers, cmɢʟee⎆τaʟκ 22:46, 2 August 2023 (UTC)