|
|
Совершенные латинские квадраты
| |
В статье [1] приводится доказательство существования совершенного латинского
квадрата порядка n2 для любого n . Определение совершенного квадрата
приведено там-же: совершенным латинским квадратом порядка n2 называют
диагональный латинский квадрат, такой, что элементы во всех его
основных субквадратах встречаются ровно один раз. Субквадрат (subsquare) Sij
латинского квадрата порядка n2 - это квадрат порядка n , ячейки которого
определены как: {(i+t,j+s): 0≤i,j≤n2-n, 0≤t,s≤n-1} . Когда i = 0 (mod n)
и j = 0 (mod n), субквадрат Sij называют основным (main subsquare).
Пример совершенного латинского квадрата 9-го порядка:
0 2 1
5 4 3
7 6 8 |
8 7 6
1 2 0
3 5 4 |
4 3 5
6 8 7
2 0 1
|
1 0 2
3 5 4
8 7 6 |
6 8 7
0 1 2
4 3 5 |
5 4 3
7 6 8
1 2 0
|
2 1 0
4 3 5
6 8 7 |
7 6 8
2 0 1
5 4 3 |
3 5 4
8 7 6
0 1 2
| |
Доказательство существования совершенного латинского квадрата одновременно
является и алгоритмом его построения.
Чтобы построить совершенный квадрат, нужны n2 латинских квадратов Ai,j,
для которых выполняется два условия: ячейка (j,i) содержит элемент i и
ячейка (n-1-j, n-1-i) содержит элемент j. В разделе 4 статьи приведен
алгоритм построения таких квадратов.
Начинаем с квадрата A=(ar,s), ar,s=(r-s) mod n. Каждый из квадратов
Ai,j строится из этого квадрата. В статье приводится серия условий и
действия для каждого из квадратов в зависимости от элементов (i, j) и
(n-1-j, n-1-i) исходного квадрата A:
Для каждого i и j берем один и тот-же исходный квадрат A
Если i = j:
- если i <> 0, меняем местами элементы 0 и i
Квадрат A становится квадратом Aij
Если i <> j:
Берем два элемента исходного квадрата A: x = A[i,j], y = A[n-1-j,n-1-i]
- если x = y, меняем колонку i с любой другой, не равной n-1-i
Теперь x <> y и возможен один из следующих ниже вариантов
- (x = i) and (y = j) -
- (x = i) and (y <> i) and (y <> j) - меняем элементы y, j
- (x <> i) and (x <> j) and (y = j) - меняем элементы x, i
- (x = j) and (y = i) - меняем элементы i, j
- (x = j) and (y <> i) and (y <> j) - меняем j на i, y на j, i на y
- (x <> i) and (x <> j) and (y = i) - меняем i на j, x на i, j на x
- (x <> i) and (x <> j) and (y <> i) and (y <> j) and (y <> x) - меняем элементы (x и i) и (y и j)
|
Посмотрим на примере для n=6, что у нас получается. Исходный квадрат A:
0 5 4 3 2 1
1 0 5 4 3 2
2 1 0 5 4 3
3 2 1 0 5 4
4 3 2 1 0 5
5 4 3 2 1 0
|
Построенные из него 36 квадратов Ai,j:
Серия квадратов A(i,j)
0 5 4 3 2 1 |5 1 4 3 2 0 |4 5 2 3 0 1 |5 2 4 3 0 1 |2 5 0 3 4 1 |1 0 4 3 2 5 |
1 0 5 4 3 2 |0 5 1 4 3 2 |1 4 5 2 3 0 |2 1 5 4 3 0 |1 2 5 0 3 4 |5 1 0 4 3 2 |
2 1 0 5 4 3 |2 0 5 1 4 3 |0 1 4 5 2 3 |1 0 2 5 4 3 |4 1 2 5 0 3 |2 5 1 0 4 3 |
3 2 1 0 5 4 |3 2 0 5 1 4 |3 0 1 4 5 2 |0 3 1 2 5 4 |3 4 1 2 5 0 |3 2 5 1 0 4 |
4 3 2 1 0 5 |4 3 2 0 5 1 |2 3 0 1 4 5 |3 4 0 1 2 5 |0 3 4 1 2 5 |4 3 2 5 1 0 |
5 4 3 2 1 0 |1 4 3 2 0 5 |5 2 3 0 1 4 |4 5 3 0 1 2 |5 0 3 4 1 2 |0 4 3 2 5 1 |
------------------------------------------------------------------------------
5 1 4 3 2 0 |1 5 4 3 2 0 |0 2 4 3 5 1 |0 5 3 4 1 2 |0 3 5 4 1 2 |0 2 1 3 5 4 |
0 5 1 4 3 2 |0 1 5 4 3 2 |1 0 2 4 3 5 |2 0 5 3 4 1 |2 5 0 3 4 1 |4 0 2 1 3 5 |
2 0 5 1 4 3 |2 0 1 5 4 3 |5 1 0 2 4 3 |1 2 0 5 3 4 |1 0 2 5 3 4 |5 4 0 2 1 3 |
3 2 0 5 1 4 |3 2 0 1 5 4 |3 5 1 0 2 4 |4 1 2 0 5 3 |4 2 1 0 5 3 |3 5 4 0 2 1 |
4 3 2 0 5 1 |4 3 2 0 1 5 |4 3 5 1 0 2 |3 4 1 2 0 5 |3 1 4 2 0 5 |1 3 5 4 0 2 |
1 4 3 2 0 5 |5 4 3 2 0 1 |2 4 3 5 1 0 |5 3 4 1 2 0 |5 4 3 1 2 0 |2 1 3 5 4 0 |
------------------------------------------------------------------------------
4 5 2 3 0 1 |0 2 4 3 5 1 |2 5 4 3 0 1 |0 3 4 5 1 2 |0 5 4 3 2 1 |0 3 1 5 4 2 |
1 4 5 2 3 0 |1 0 2 4 3 5 |1 2 5 4 3 0 |2 0 3 4 5 1 |1 0 5 4 3 2 |2 0 5 4 3 1 |
0 1 4 5 2 3 |5 1 0 2 4 3 |0 1 2 5 4 3 |1 2 0 3 4 5 |2 1 0 5 4 3 |1 2 4 3 0 5 |
3 0 1 4 5 2 |3 5 1 0 2 4 |3 0 1 2 5 4 |5 1 2 0 3 4 |3 2 1 0 5 4 |5 1 3 0 2 4 |
2 3 0 1 4 5 |4 3 5 1 0 2 |4 3 0 1 2 5 |4 5 1 2 0 3 |4 3 2 1 0 5 |4 5 0 2 1 3 |
5 2 3 0 1 4 |2 4 3 5 1 0 |5 4 3 0 1 2 |3 4 5 1 2 0 |5 4 3 2 1 0 |3 4 2 1 5 0 |
------------------------------------------------------------------------------
2 5 4 3 0 1 |0 5 3 4 1 2 |0 3 4 5 1 2 |3 5 4 0 2 1 |0 4 5 1 2 3 |0 4 5 2 3 1 |
1 2 5 0 4 3 |2 0 5 3 4 1 |2 0 3 4 5 1 |1 3 5 4 0 2 |3 0 4 5 1 2 |1 0 4 5 2 3 |
3 1 2 4 5 0 |1 2 0 5 3 4 |1 2 0 3 4 5 |2 1 3 5 4 0 |2 3 0 4 5 1 |3 1 0 4 5 2 |
0 3 1 5 2 4 |4 1 2 0 5 3 |5 1 2 0 3 4 |0 2 1 3 5 4 |1 2 3 0 4 5 |2 3 1 0 4 5 |
4 0 3 2 1 5 |3 4 1 2 0 5 |4 5 1 2 0 3 |4 0 2 1 3 5 |5 1 2 3 0 4 |5 2 3 1 0 4 |
5 4 0 1 3 2 |5 3 4 1 2 0 |3 4 5 1 2 0 |5 4 0 2 1 3 |4 5 1 2 3 0 |4 5 2 3 1 0 |
------------------------------------------------------------------------------
2 5 0 3 4 1 |0 5 2 1 3 4 |0 5 4 3 2 1 |0 4 5 1 2 3 |4 5 0 3 2 1 |0 5 1 3 2 4 |
1 2 5 0 3 4 |3 0 5 2 4 1 |1 0 5 4 3 2 |3 0 4 5 1 2 |1 4 5 0 3 2 |4 0 5 1 3 2 |
4 1 2 5 0 3 |4 3 0 5 1 2 |2 1 0 5 4 3 |2 3 0 4 5 1 |2 1 4 5 0 3 |2 4 0 5 1 3 |
3 4 1 2 5 0 |1 4 3 0 2 5 |3 2 1 0 5 4 |1 2 3 0 4 5 |3 2 1 4 5 0 |3 2 4 0 5 1 |
0 3 4 1 2 5 |2 1 4 3 5 0 |4 3 2 1 0 5 |5 1 2 3 0 4 |0 3 2 1 4 5 |1 3 2 4 0 5 |
5 0 3 4 1 2 |5 2 1 4 0 3 |5 4 3 2 1 0 |4 5 1 2 3 0 |5 0 3 2 1 4 |5 1 3 2 4 0 |
------------------------------------------------------------------------------
1 0 4 3 2 5 |0 2 1 3 5 4 |0 5 4 2 3 1 |0 4 5 2 3 1 |0 5 1 3 2 4 |5 0 4 3 2 1 |
5 1 0 4 3 2 |4 0 2 1 3 5 |5 3 1 4 2 0 |1 0 4 5 2 3 |4 0 5 1 3 2 |1 5 0 4 3 2 |
2 5 1 0 4 3 |5 4 0 2 1 3 |3 2 0 1 4 5 |3 1 0 4 5 2 |2 4 0 5 1 3 |2 1 5 0 4 3 |
3 2 5 1 0 4 |3 5 4 0 2 1 |2 4 5 0 1 3 |2 3 1 0 4 5 |3 2 4 0 5 1 |3 2 1 5 0 4 |
4 3 2 5 1 0 |1 3 5 4 0 2 |4 1 3 5 0 2 |5 2 3 1 0 4 |1 3 2 4 0 5 |4 3 2 1 5 0 |
0 4 3 2 5 1 |2 1 3 5 4 0 |1 0 2 3 5 4 |4 5 2 3 1 0 |5 1 3 2 4 0 |0 4 3 2 1 5 |
|
Возьмем еще один произвольный латинский квадрат B=(bi,j) порядка n
(Например, возьмем тот-же квадрат A) и выполним преобразование:
C = n*bi,j J + Ai,j
Здесь J - матрица n x n из единиц. Другими словами каждый элемент матрицы B
(bi,j) заменяем матрицей Ai,j, к каждому элементу которой прибавляем n*bi,j.
pascal
// C - матрица порядка n*n, составленная из элементов матриц A(i,j)
for i := 0 to n*n - 1 do begin
for j := 0 to n*n - 1 do begin
C[i,j] := n*A[0,0][i div n,j div n]+C[i][j];
end;
end;
|
Получим такую матрицу
Промежуточная матрица C
0 5 4 3 2 1 35 31 34 33 32 30 28 29 26 27 24 25 23 20 22 21 18 19 14 17 12 15 16 13 7 6 10 9 8 11
1 0 5 4 3 2 30 35 31 34 33 32 25 28 29 26 27 24 20 19 23 22 21 18 13 14 17 12 15 16 11 7 6 10 9 8
2 1 0 5 4 3 32 30 35 31 34 33 24 25 28 29 26 27 19 18 20 23 22 21 16 13 14 17 12 15 8 11 7 6 10 9
3 2 1 0 5 4 33 32 30 35 31 34 27 24 25 28 29 26 18 21 19 20 23 22 15 16 13 14 17 12 9 8 11 7 6 10
4 3 2 1 0 5 34 33 32 30 35 31 26 27 24 25 28 29 21 22 18 19 20 23 12 15 16 13 14 17 10 9 8 11 7 6
5 4 3 2 1 0 31 34 33 32 30 35 29 26 27 24 25 28 22 23 21 18 19 20 17 12 15 16 13 14 6 10 9 8 11 7
11 7 10 9 8 6 1 5 4 3 2 0 30 32 34 33 35 31 24 29 27 28 25 26 18 21 23 22 19 20 12 14 13 15 17 16
6 11 7 10 9 8 0 1 5 4 3 2 31 30 32 34 33 35 26 24 29 27 28 25 20 23 18 21 22 19 16 12 14 13 15 17
8 6 11 7 10 9 2 0 1 5 4 3 35 31 30 32 34 33 25 26 24 29 27 28 19 18 20 23 21 22 17 16 12 14 13 15
9 8 6 11 7 10 3 2 0 1 5 4 33 35 31 30 32 34 28 25 26 24 29 27 22 20 19 18 23 21 15 17 16 12 14 13
10 9 8 6 11 7 4 3 2 0 1 5 34 33 35 31 30 32 27 28 25 26 24 29 21 19 22 20 18 23 13 15 17 16 12 14
7 10 9 8 6 11 5 4 3 2 0 1 32 34 33 35 31 30 29 27 28 25 26 24 23 22 21 19 20 18 14 13 15 17 16 12
16 17 14 15 12 13 6 8 10 9 11 7 2 5 4 3 0 1 30 33 34 35 31 32 24 29 28 27 26 25 18 21 19 23 22 20
13 16 17 14 15 12 7 6 8 10 9 11 1 2 5 4 3 0 32 30 33 34 35 31 25 24 29 28 27 26 20 18 23 22 21 19
12 13 16 17 14 15 11 7 6 8 10 9 0 1 2 5 4 3 31 32 30 33 34 35 26 25 24 29 28 27 19 20 22 21 18 23
15 12 13 16 17 14 9 11 7 6 8 10 3 0 1 2 5 4 35 31 32 30 33 34 27 26 25 24 29 28 23 19 21 18 20 22
14 15 12 13 16 17 10 9 11 7 6 8 4 3 0 1 2 5 34 35 31 32 30 33 28 27 26 25 24 29 22 23 18 20 19 21
17 14 15 12 13 16 8 10 9 11 7 6 5 4 3 0 1 2 33 34 35 31 32 30 29 28 27 26 25 24 21 22 20 19 23 18
20 23 22 21 18 19 12 17 15 16 13 14 6 9 10 11 7 8 3 5 4 0 2 1 30 34 35 31 32 33 24 28 29 26 27 25
19 20 23 18 22 21 14 12 17 15 16 13 8 6 9 10 11 7 1 3 5 4 0 2 33 30 34 35 31 32 25 24 28 29 26 27
21 19 20 22 23 18 13 14 12 17 15 16 7 8 6 9 10 11 2 1 3 5 4 0 32 33 30 34 35 31 27 25 24 28 29 26
18 21 19 23 20 22 16 13 14 12 17 15 11 7 8 6 9 10 0 2 1 3 5 4 31 32 33 30 34 35 26 27 25 24 28 29
22 18 21 20 19 23 15 16 13 14 12 17 10 11 7 8 6 9 4 0 2 1 3 5 35 31 32 33 30 34 29 26 27 25 24 28
23 22 18 19 21 20 17 15 16 13 14 12 9 10 11 7 8 6 5 4 0 2 1 3 34 35 31 32 33 30 28 29 26 27 25 24
26 29 24 27 28 25 18 23 20 19 21 22 12 17 16 15 14 13 6 10 11 7 8 9 4 5 0 3 2 1 30 35 31 33 32 34
25 26 29 24 27 28 21 18 23 20 22 19 13 12 17 16 15 14 9 6 10 11 7 8 1 4 5 0 3 2 34 30 35 31 33 32
28 25 26 29 24 27 22 21 18 23 19 20 14 13 12 17 16 15 8 9 6 10 11 7 2 1 4 5 0 3 32 34 30 35 31 33
27 28 25 26 29 24 19 22 21 18 20 23 15 14 13 12 17 16 7 8 9 6 10 11 3 2 1 4 5 0 33 32 34 30 35 31
24 27 28 25 26 29 20 19 22 21 23 18 16 15 14 13 12 17 11 7 8 9 6 10 0 3 2 1 4 5 31 33 32 34 30 35
29 24 27 28 25 26 23 20 19 22 18 21 17 16 15 14 13 12 10 11 7 8 9 6 5 0 3 2 1 4 35 31 33 32 34 30
31 30 34 33 32 35 24 26 25 27 29 28 18 23 22 20 21 19 12 16 17 14 15 13 6 11 7 9 8 10 5 0 4 3 2 1
35 31 30 34 33 32 28 24 26 25 27 29 23 21 19 22 20 18 13 12 16 17 14 15 10 6 11 7 9 8 1 5 0 4 3 2
32 35 31 30 34 33 29 28 24 26 25 27 21 20 18 19 22 23 15 13 12 16 17 14 8 10 6 11 7 9 2 1 5 0 4 3
33 32 35 31 30 34 27 29 28 24 26 25 20 22 23 18 19 21 14 15 13 12 16 17 9 8 10 6 11 7 3 2 1 5 0 4
34 33 32 35 31 30 25 27 29 28 24 26 22 19 21 23 18 20 17 14 15 13 12 16 7 9 8 10 6 11 4 3 2 1 5 0
30 34 33 32 35 31 26 25 27 29 28 24 19 18 20 21 23 22 16 17 14 15 13 12 11 7 9 8 10 6 0 4 3 2 1 5
|
Далее получаем матрицу P
P = (pi,j), pni+j,k = cnj+i,k
pascal
for i := 0 to n - 1 do begin
for j := 0 to n - 1 do begin
for k := 0 to n*n - 1 do begin
P[n*i+j, k] := C[n*j+i, k];
end;
end;
end;
|
Эта матрица будет совершенным латинским квадратом:
Совершенный латинский квадрат 36-го порядка
0 5 4 3 2 1
11 7 10 9 8 6
16 17 14 15 12 13
20 23 22 21 18 19
26 29 24 27 28 25
31 30 34 33 32 35 |
35 31 34 33 32 30
1 5 4 3 2 0
6 8 10 9 11 7
12 17 15 16 13 14
18 23 20 19 21 22
24 26 25 27 29 28 |
28 29 26 27 24 25
30 32 34 33 35 31
2 5 4 3 0 1
6 9 10 11 7 8
12 17 16 15 14 13
18 23 22 20 21 19 |
23 20 22 21 18 19
24 29 27 28 25 26
30 33 34 35 31 32
3 5 4 0 2 1
6 10 11 7 8 9
12 16 17 14 15 13 |
14 17 12 15 16 13
18 21 23 22 19 20
24 29 28 27 26 25
30 34 35 31 32 33
4 5 0 3 2 1
6 11 7 9 8 10 |
7 6 10 9 8 11
12 14 13 15 17 16
18 21 19 23 22 20
24 28 29 26 27 25
30 35 31 33 32 34
5 0 4 3 2 1
|
1 0 5 4 3 2
6 11 7 10 9 8
13 16 17 14 15 12
19 20 23 18 22 21
25 26 29 24 27 28
35 31 30 34 33 32 |
30 35 31 34 33 32
0 1 5 4 3 2
7 6 8 10 9 11
14 12 17 15 16 13
21 18 23 20 22 19
28 24 26 25 27 29 |
25 28 29 26 27 24
31 30 32 34 33 35
1 2 5 4 3 0
8 6 9 10 11 7
13 12 17 16 15 14
23 21 19 22 20 18 |
20 19 23 22 21 18
26 24 29 27 28 25
32 30 33 34 35 31
1 3 5 4 0 2
9 6 10 11 7 8
13 12 16 17 14 15 |
13 14 17 12 15 16
20 23 18 21 22 19
25 24 29 28 27 26
33 30 34 35 31 32
1 4 5 0 3 2
10 6 11 7 9 8 |
11 7 6 10 9 8
16 12 14 13 15 17
20 18 23 22 21 19
25 24 28 29 26 27
34 30 35 31 33 32
1 5 0 4 3 2
|
2 1 0 5 4 3
8 6 11 7 10 9
12 13 16 17 14 15
21 19 20 22 23 18
28 25 26 29 24 27
32 35 31 30 34 33 |
32 30 35 31 34 33
2 0 1 5 4 3
11 7 6 8 10 9
13 14 12 17 15 16
22 21 18 23 19 20
29 28 24 26 25 27 |
24 25 28 29 26 27
35 31 30 32 34 33
0 1 2 5 4 3
7 8 6 9 10 11
14 13 12 17 16 15
21 20 18 19 22 23 |
19 18 20 23 22 21
25 26 24 29 27 28
31 32 30 33 34 35
2 1 3 5 4 0
8 9 6 10 11 7
15 13 12 16 17 14 |
16 13 14 17 12 15
19 18 20 23 21 22
26 25 24 29 28 27
32 33 30 34 35 31
2 1 4 5 0 3
8 10 6 11 7 9 |
8 11 7 6 10 9
17 16 12 14 13 15
19 20 22 21 18 23
27 25 24 28 29 26
32 34 30 35 31 33
2 1 5 0 4 3
|
3 2 1 0 5 4
9 8 6 11 7 10
15 12 13 16 17 14
18 21 19 23 20 22
27 28 25 26 29 24
33 32 35 31 30 34 |
33 32 30 35 31 34
3 2 0 1 5 4
9 11 7 6 8 10
16 13 14 12 17 15
19 22 21 18 20 23
27 29 28 24 26 25 |
27 24 25 28 29 26
33 35 31 30 32 34
3 0 1 2 5 4
11 7 8 6 9 10
15 14 13 12 17 16
20 22 23 18 19 21 |
18 21 19 20 23 22
28 25 26 24 29 27
35 31 32 30 33 34
0 2 1 3 5 4
7 8 9 6 10 11
14 15 13 12 16 17 |
15 16 13 14 17 12
22 20 19 18 23 21
27 26 25 24 29 28
31 32 33 30 34 35
3 2 1 4 5 0
9 8 10 6 11 7 |
9 8 11 7 6 10
15 17 16 12 14 13
23 19 21 18 20 22
26 27 25 24 28 29
33 32 34 30 35 31
3 2 1 5 0 4
|
4 3 2 1 0 5
10 9 8 6 11 7
14 15 12 13 16 17
22 18 21 20 19 23
24 27 28 25 26 29
34 33 32 35 31 30 |
34 33 32 30 35 31
4 3 2 0 1 5
10 9 11 7 6 8
15 16 13 14 12 17
20 19 22 21 23 18
25 27 29 28 24 26 |
26 27 24 25 28 29
34 33 35 31 30 32
4 3 0 1 2 5
10 11 7 8 6 9
16 15 14 13 12 17
22 19 21 23 18 20 |
21 22 18 19 20 23
27 28 25 26 24 29
34 35 31 32 30 33
4 0 2 1 3 5
11 7 8 9 6 10
17 14 15 13 12 16 |
12 15 16 13 14 17
21 19 22 20 18 23
28 27 26 25 24 29
35 31 32 33 30 34
0 3 2 1 4 5
7 9 8 10 6 11 |
10 9 8 11 7 6
13 15 17 16 12 14
22 23 18 20 19 21
29 26 27 25 24 28
31 33 32 34 30 35
4 3 2 1 5 0
|
5 4 3 2 1 0
7 10 9 8 6 11
17 14 15 12 13 16
23 22 18 19 21 20
29 24 27 28 25 26
30 34 33 32 35 31 |
31 34 33 32 30 35
5 4 3 2 0 1
8 10 9 11 7 6
17 15 16 13 14 12
23 20 19 22 18 21
26 25 27 29 28 24 |
29 26 27 24 25 28
32 34 33 35 31 30
5 4 3 0 1 2
9 10 11 7 8 6
17 16 15 14 13 12
19 18 20 21 23 22 |
22 23 21 18 19 20
29 27 28 25 26 24
33 34 35 31 32 30
5 4 0 2 1 3
10 11 7 8 9 6
16 17 14 15 13 12 |
17 12 15 16 13 14
23 22 21 19 20 18
29 28 27 26 25 24
34 35 31 32 33 30
5 0 3 2 1 4
11 7 9 8 10 6 |
6 10 9 8 11 7
14 13 15 17 16 12
21 22 20 19 23 18
28 29 26 27 25 24
35 31 33 32 34 30
0 4 3 2 1 5
| |
В приложении исходники описанного алгоритма и приложение
для построения совершенного латинского квадрата. Задайте параметр n и получите
квадрат порядка n2.
1↑K.Heinrich, K.Kim and V.K.Prasanna Kumar, Perfect latin squares, Discrete Applied Mathematics
37138 ( 1992) 281- 286.
|