Лати́нский квадра́т — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу). Ниже приводятся два примера:

Латинские квадраты существуют для любого n.

Любой латинский квадрат является таблицей умножения (таблицей Кэли) квазигруппы.

Название «латинский квадрат» берёт начало от Леонарда Эйлера, который использовал латинские буквы вместо цифр в таблице.

Ортогональные латинские квадраты

Два латинских квадрата называются ортогональными, если различны все упорядоченные пары символов (a,b), где a — символ в некоторой клетке первого латинского квадрата, а b — символ в той же клетке второго латинского квадрата. Пример пары ортогональных латинских квадратов:

Легко видеть, что в соответствующем квадрате из пар все пары различны:

Ортогональные латинские квадраты существуют для любого порядка n кроме 2 и 6. Для n являющихся степенью простого числа есть набор n-1 попарно ортогональных латинских квадратов. Такой набор можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n.

Если в каждой диагонали латинского квадрата все элементы различны, такой латинский квадрат называется диагональным. Пары ортогональных диагональных латинских квадратов существуют для всех порядков, кроме 2, 3 и 6. Пример пары диагональных ортогональных латинских квадратов 5-го порядка:

Квадрат из пар элементов двух ортогональных латинских квадратов называется греко-латинский квадратом. Подобные квадраты часто используются для построения магических квадратов.^[1]

Использование латинских квадратов для планирования экспериментов

Предположим, что нужно провести несколько экспериментов, зависящих от 3 параметров 1≤a,b,c≤n, так чтобы для каждой пары параметров были опробованы все n² вариантов. Тогда нужно взять любой латинский квадрат порядка n и провести n² экспериментов с параметрами a = номер строки, b = номер столбца, c = значение в клетке латинского квадрата.

Задача о заполнении латинского квадрата

Пусть дана таблица n × n, в которой некоторые ячейки пусты, а в некоторых стоят числа от 1 до n. Задача о заполнении латинского квадрата формулируется так: существует ли способ вписать числа в пустые ячейки так, чтобы полученная таблица стала латинским квадратом?

Задача о заполнении латинского квадрата NP-полна. Однако, если заполнены несколько верхних строк, то квадрат всегда можно дополнить до латинского.

Примечания