Свежачок
Головоломки6 минут на чтениеРедакция СвежачкаОпубликовано:

Что такое латинский квадрат и чем он отличается от судоку

Латинский квадрат — сетка, где числа не повторяются в строках и столбцах. Показываем на примере 4×4, как это работает, и объясняем, какое правило добавляет судоку.

Судоку 9×9 на бумаге под лупой, выделен блок 3×3

Латинский квадрат — это таблица N×N, где каждая строка и каждый столбец заполнены одними и теми же символами без повторов: по одному разу в каждой строке и в каждом столбце. Судоку устроено так же, но с одним лишним условием — блоками. Поэтому любое решённое судоку будет латинским квадратом, а вот латинский квадрат судоку не всегда. Ниже разберём определение на простом примере, покажем квадрат 4×4, который «ломается» на блоках, и способ собрать свой квадрат за минуту.

Что такое латинский квадрат

Берём сетку из N строк и N столбцов и набор из N разных символов — цифр, букв или цветов. Правило всего одно: в каждой строке и в каждом столбце каждый символ встречается ровно один раз. Число N называют порядком квадрата.

Самый маленький содержательный случай — порядок 3:

1 2 3
2 3 1
3 1 2

Проверьте любую строку и любой столбец: везде по одной единице, двойке и тройке. Это и есть латинский квадрат. Ничего про блоки, диагонали или подсказки в правиле нет — только строки и столбцы.

Название появилось из-за букв. Леонард Эйлер в XVIII веке изучал такие таблицы, заполняя их латинскими буквами A, B, C вместо привычных цифр, и за ними закрепилось имя «латинские квадраты». Математики занимаются ими до сих пор: например, квадратов порядка 5 существует 161 280 — уже для сетки 5×5 перебор вариантов даёт сотни тысяч результатов.

Чем судоку отличается от латинского квадрата

Классическое судоку — это латинский квадрат 9×9 с двумя дополнениями:

  • сетку делят на девять блоков 3×3, и в каждом блоке цифры 1–9 тоже не повторяются;
  • часть клеток заранее заполнена, а головоломка составлена так, что у задачи есть ровно одно решение.

Получается отношение «частный случай»: судоко — это латинский квадрат, доведённый до головоломки. Если убрать из судоку блоки и подсказки, останется чистый латинский квадрат. Если добавить к латинскому квадрату новые условия — диагонали, области с суммами, соседние клетки — получатся другие варианты судоку, о них подробнее в статье про виды судоку.

Практическое следствие разницы: техники решения у них общие. Умение находить одиночки и пары в строках и столбцах пригодится в обоих случаях, просто в судоку те же приёмы дополнительно работают внутри блоков 3×3.

Латинский квадрат 4×4 с выделенным блоком 2×2, где цифры повторяются

Пример: латинский квадрат 4×4, который не судоку

Судоку бывает не только 9×9 — для тренировки решают и сетки 4×4 с блоками 2×2. Возьмём латинский квадрат порядка 4:

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

По правилу латинского квадрата всё честно: в каждой строке и в каждом столбце цифры 1–4 встречаются по одному разу. Но теперь проверим блоки 2×2, как потребовало бы судоку. Левый верхний блок состоит из цифр 1, 2, 2, 1 — единица и двойка продублировались. То же самое в остальных трёх блоках.

При этом квадрат можно починить одной перестановкой: поменяем местами вторую и третью строки.

1 2 3 4
3 4 1 2
2 1 4 3
4 3 2 1

Строки и столбцы по-прежнему без повторов, а блоки теперь собраны правильно: в каждом собран полный набор 1–4. Перед нами сразу и латинский квадрат, и решённое судоку 4×4. На этом примере видна суть отличия: судоку требует всего, что требует латинский квадрат, плюс следит за блоками.

Как составить латинский квадрат

Собрать квадрат любого порядка можно «циклическим сдвигом»:

  1. Впишите в первую строку все символы по порядку, например 1 2 3 4.
  2. Каждую следующую строку сдвиньте на одну клетку влево: уходящие в начало символы переходят в конец строки.
  3. Повторяйте, пока не заполните всю сетку.

Для порядка 4 получится так:

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Каждый столбец повторяет первую строку сверху вниз, поэтому повторов нигде нет. Тот же принцип удобно увидеть на цветных плитках.

Руки выкладывают цветные плитки строками со сдвигом

Из одного такого базового квадрата легко получить множество других: строки можно переставлять в любом порядке, столбцы тоже, а цифры разрешается переименовать целиком — например, заменить все единицы четвёрками и наоборот. Латинское правило при этом не нарушается. Для судоку таких свобод太多 нет: перестановка строк может собрать или сломать блоки, как в примере выше, поэтому генераторы судоку после каждой перестановки проверяют ещё и блоки.

Зачем латинские квадраты вне головоломок

Правило «каждый символ по разу в строке и столбце» полезно там, где нужно равномерно распределить варианты по двум условиям сразу:

  • в экспериментах: поля удобрений или сорта растений раскладывают по сетке, чтобы каждый вариант встретился по одному разу в каждой строке и каждом столбце — так исключают влияние двух посторонних факторов;
  • в расписаниях турниров и смен: участникам и дням недели соответствуют строки и столбцы квадрата;
  • в кодах и шифрах: латинские квадраты помогают строить таблицы замен.

Есть и знаменитая нерешённая вовремя задача: Эйлер спрашивал, можно ли построить пару «накладывающихся» латинских квадратов порядка 6 — легенду о 36 офицерах. Ответ «нельзя» доказали только в 1901 году.

От квадрата к судоку

Латинский квадрат — каркас, из которого выросла привычная головоломка: судоку появилось как латинский квадрат с блоками и подсказками. Если хотите применить разницу на практике, начните с правил судоку и решите пару сеток онлайн, а когда классика станет тесной, попробуйте диагональное судоку, где к строкам, столбцам и блокам добавляются две диагонали. А приём «каждая цифра по разу в строке и столбце» останется тем же самым в любой из этих сеток.

Ещё немного полезного

Все статьи →