Латинский квадрат

Наряду с магическим квадратом, о котором можно прочитать в соответствующей главе этого раздела, широкую славу и известность среди прочих математических «головоломок» приобрел знаменитый латинский квадрат, который представляет собой табличку с равным количеством столбцов и строк, каждая ячейка которой включает в себя определенный символ (цифру, букву, изображение и пр.). Особенность латинского квадрата заключается в том, что в каждой строке и в каждом столбце по одному разу обязательно используются все символы.

Название «латинский квадрат» этой «головоломке» было дано выдающимся математиком Леонардом Эйлером, который, посвятив много времени изучению алгоритмов создания магических квадратов, заменил цифры в таблице латинскими или греческими буквами.

Два латинских квадрата одного порядка называют ортогональными, если после наложения каждая возможная упорядоченная пара символов встречается ровно один раз. Ортогональной является далеко не любая пара латинских квадратов. Пары взаимно ортогональных латинских квадратов существуют для всех порядков n, кроме n = 2 и n = 6; этот результат был окончательно установлен в 1959–1960 годах работами Бозе, Шрикханде и Паркера.

В качестве одного из самых ярких примеров латинского квадрата можно привести популярную японскую головоломку «судоку», название которой переводится, как «цифра, стоящая отдельно». Это квадрат с девятью строками и девятью столбцами, включающий в себя девять более мелких квадратов 3 × 3, некоторые клетки которого уже заполнены числами. Задачей игрока является заполнить оставшиеся ячейки цифрами таким образом, чтобы в каждой строке, каждом столбце и каждом мини-квадратике цифра от 1 до 9 была использована лишь единожды.