Латинські квадрати та їх використання. Науковий форум dxdy

Якщо уважно придивитися до чисел від 1 до 16, які у клітинах квадрата на рис. 1, можна помітити таку закономірність: сума чисел у кожному горизонтальному ряду, у кожному вертикальному ряду і з кожної з діагоналей одна й та сама. Такий квадрат і всі квадрати, що мають аналогічну властивість, отримали назву магічних.

Завдання складання та описи магічних квадратів цікавили математиків з найдавніших часів. Однак повного описувсіх можливих магічних квадратів не отримано й досі. Магічних квадратів немає. На рис. 2 зображено єдиний магічний квадрат. Єдиний тому, що інші магічні квадрати виходять із нього або поворотом навколо центру, або відбитком щодо однієї з його осей симетрії.

Зі збільшенням розмірів (числа клітин) квадрата швидко зростає кількість можливих магічних квадратів. Так, наприклад, різних магічних квадратів вже 880, а для розміру їхня кількість наближається до чверті мільйона. Серед них є квадрати, які мають цікавими властивостями. Наприклад, у квадраті на рис. 3 рівні між собою не тільки суми чисел у рядках, стовпцях та діагоналях, а й суми п'ятрок чисел за «розламаними» діагоналями, пов'язаними на малюнку кольоровими лініями.

Латинським квадратом називається квадрат клітин, у яких написані числа , причому отже у кожному рядку і кожному стовпці зустрічаються ці цифри за одним разу. На рис. 4 зображено два такі латинські квадрати. Вони мають цікаву особливість: якщо один квадрат накласти на інший, то всі пари чисел виявляються різними. Такі пари латинських квадратівназиваються ортогональними. Завдання відшукання ортогональних латинських квадратів вперше поставив Л. Ейлер, причому в такому цікавому формулюванні: «Серед 36 офіцерів порівну уланів, драгунів, гусарів, кірасиров, кавалергардів і гренадерів і, крім того, порівну генералів, полковників, ручників, майорів, , причому кожен рід військ представлений офіцерами всіх шести рангів. Чи можна побудувати цих офіцерів у карі так, щоб у будь-якій колоні та будь-якій шерензі зустрічалися офіцери всіх рангів?»

Ейлер не зміг знайти вирішення цього завдання. 1901 р. було доведено, що такого рішення не існує. У той же час Ейлер довів, що ортогональні пари латинських квадратів існують для всіх непарних значень і таких парних значень, які діляться на 4. Розв'язання задачі Ейлера для 25 офіцерів зображено на рис. 5. Чин офіцера символізує кольоровий кружок у кутку кожної з клітин. Тут особливо добре видно зв'язок між завданням Ейлера і латинськими квадратами: роди військ відповідають числам одного латинського квадрата, а чини (кольорові точки) – числам ортогонального йому латинського квадрата. Ейлер висунув гіпотезу, що з інших значень , тобто. якщо число при розподілі на 4 дає у залишку 2, ортогональних квадратів немає. У 1901 р. було доведено, що ортогональних квадратів розміром немає, і це посилювало впевненість у справедливості гіпотези Ейлера. Однак у 1959 р. з допомогою ЕОМ було знайдено спочатку ортогональні квадрати, потім. А потім було показано, що для будь-якого, крім 6, існують ортогональні квадрати розміром .

Гравюра А. Дюрера "Меланхолія"

Часто відтворюється магічний квадрат, присутній на знаменитій гравюрі А. Дюрера Меланхолія.

Цікаво, що середні числа в останньому рядку зображають рік 1514 року, в якому була створена ця гравюра». Д. Оре

Магічні та латинські квадрати – близькі родичі. Нехай ми маємо два ортогональні латинські квадрати. Заповнимо клітини нового квадрата тих же розмірів наступним чином. Поставимо туди число , де число в такій клітині першого квадрата, а число в такій же клітині другого квадрата. Неважко зрозуміти, що в отриманому квадраті суми чисел у рядках та стовпцях (але не обов'язково на діагоналях) будуть однакові.

Теорія латинських квадратів знайшла численні застосування як у математиці, і у її додатках. Наведемо такий приклад. Нехай ми хочемо випробувати 4 сорти пшениці на врожайність у цій місцевості, причому врахувати вплив ступеня розрідженості посівів та вплив двох видів добрив. Для цього розіб'ємо квадратну ділянку землі на 16 ділянок (рис. 6). Перший сорт пшениці посадимо на ділянках, що відповідають нижній горизонтальній смузі, наступний сорт – на чотирьох ділянках, що відповідають наступній смузі, і т.д. (на малюнку сорт позначений кольором). При цьому максимальна густота посівів нехай буде на тих ділянках, які відповідають лівому вертикальному стовпчику малюнка, і зменшується під час переходу вправо (на рисунку відповідає зменшення інтенсивності кольору). Цифри ж, що стоять у клітинах малюнка, нехай означають: перша – кількість кілограмів добрива першого виду, що вноситься на цю ділянку, а друга – кількість добрива другого виду, що вноситься. Ці числа на 1 менше чиселв ортогональних латинських квадратах із рис. 4. Неважко зрозуміти, що при цьому реалізовані всі можливі пари поєднань як сорту, і густоти посіву, так і інших компонентів: сорти та добрив першого виду, добрив першого та другого видів, густини та добрив другого виду.

Використання ортогональних латинських квадратів допомагає врахувати все можливі варіантив експериментах у сільському господарстві, фізики, хімії, техніки.

Дизайн із включенням рандомізованих блоків дозволяє ізолювати один спотворюючий фактор. Латинський квадрат дає можливість ізолювати вже як мінімум дві змінні, що загрожують. внутрішньої валідностідослідження.

Латинський квадрат – це давня математична головоломка; його складання є окремим випадком розв'язання магічних квадратів. У загальному виглядіфігура є рівносторонньою матрицею, заповненою латинськими літерамитаким чином, що в кожному рядку та в кожному стовпці таблиці буква алфавіту зустрічається точно один раз (рис. 9.8).

Рис. 9.8.

За допомогою латинського квадрата можна блокувати не лише рядки, а й стовпці. У дослідженні це може виглядати так: припустимо, у нас є потрібна умова (X) і дві змінні (Вта С), вплив яких потрібно поставити під контроль. Це можна зробити, поставивши як горизонтальні, так і вертикальні блоки. Рішення виглядає так, як показано на рис. 9.9. Завдання полягає у складанні загальної таблицінезалежних змінних таким чином, щоб комбінації у рядках та стовпцях не повторювалися. Для трьох змінних буде дев'ять комбінацій.

Зрозуміло, замість трьох рівнів незалежної змінної можна використовувати три різні змінні: рішення від цього не зміниться. Для експерименту з латинським квадратом формулюються три нульові гіпотези:

• - рівність середніх значень груп з різними рівнямиумови (X);
• - рівність середніх значень груп із різними рівнями фактора У(Рядки);
• - рівність середніх значень груп із різними рівнями чинника З (стовпці).

Слід зазначити деякі недоліки латинського квадрата. По-перше, теоретично дослідник може включити будь-яке число рівнів незалежної змінної. Тим не менш, на практиці рідко використовуються квадрати, що включають більше десяти градацій умови. У той же час при рівні 4 і менше присутнє дуже мало ступенів свободи, що збільшує помилку. Крім того, якщо між умовою, рядками та стовпцями існують ефекти взаємодії, результат виявиться спотвореним. Однак перевірка моделі на взаємодію можлива лише за достатньої величини сторони квадрата. По-друге, кількість рівнів незалежної змінної, рядків і стовпців має бути однаковим, що не завжди можливе. Нарешті, провести рандомізацію для цього плану досить складно.

Рис. 9.9.

Латинський квадрат – це базова фігура для досліджень із багатовимірним блокуванням. На його основі можна побудувати і більше складні планинаприклад, греко-латинський квадраті гіпер-греко-латинський квадрат.

Незважаючи на складність, аналіз ефекту впливу результатів експерименту з використанням латинського квадрата виконується приблизно за таким же алгоритмом, як і аналіз у дослідженні із застосуванням рандомізованих блоків.

Вище представлено невелику частину розроблених теоретично експериментів планів. Використовуючи їх як основу та комбінуючи один з одним, можна створити практично необмежену кількістьнайрізноманітніших досліджень, які, однак, вимагатимуть більш складних процедур оцінки ефекту впливу та контролю фонових факторів.

Може виникнути питання: навіщо приділяти таку кількість часу строгому експерименту, якщо можливості застосування його в соціології обмежені? З одного боку, соціальна взаємодія у всіх своїх проявах справді є складно контрольованим феноменом, і в багатьох випадках соціолог не може проводити рандомізацію, а також впливати на незалежну змінну. З іншого боку, проблеми експериментування пов'язані як з характером об'єкта, а й слабкою зацікавленістю соціологічного співтовариства. Експеримент є досить складним методомвикористання якого пов'язане з кропіткою роботою з контролю, ізоляції шуканих змінних, а також із застосуванням складних процедур вимірювання ефекту тестування. Враховуючи загальний дескриптивний характер сучасної соціологіїі найчастіше щодо невисокий рівень рефлексії щодо валідності каузальних аргументів, експериментальні дослідження становлять не надто велику часткув загальної сукупностіробіт, що випускаються.

Даний факт не означає, що ніша експерименту в суспільних наукахзавжди буде обмеженою. Озираючись довкола, ми можемо помітити, що в інших областях соціального знаннятеорія експериментування розвивається куди швидшими темпами. Не секрет, що соціальна психологіявже довгий часпрацює як експериментальна наука і не мислить себе поза даного методу. Разом з тим, можна спостерігати таке динамічно напрямок, що розвиваєтьсяяк експериментальна економіка. Словникова стаття Вернона Сміта «Експериментальні методи економіки» починається словами: «Історично предмет і метод економіки передбачав неекспериментальний характер науки (подібно до астрономії та метеорології)» . Розкриваючи сучасний станНаука, автор показує, що починаючи з 1980-х років економіка все більше стає експериментальною наукою.

Придивимося до порівняльної політології. Сто років тому у посланні до Американської асоціації політичної наукиїї тодішній керівник Лоуренс Новелл заявляв: «Ми обмежені відсутністю можливості експериментування... Політичні дослідженняє обсерваційною, а чи не експериментальної наукою». Книга "The Oxford Handbook of Experimental Political Science", що вийшла в 2007 р., вказує, що ситуація змінюється стрімким чином у міру того, як дослідники політики приділяють все більший вплив каузальним аргументам та емпіричному вивченню свого предмета. Достатньо перерахувати численні роботи з таких тем, як мобілізація, голосування, парламентаризм, бюрократія, міжнародні відносини, переговори, зовнішня політика, створення коаліцій, політична культура, «Експорт демократії», електоральні системи, право. Практично всі ці області, начебто, залишають вченому можливість лише пасивного спостереженнята реєстрації фактів, але рандомізовані експерименти тут проводяться й дуже успішно.

Не заперечуючи об'єктивних труднощів використання суворого експерименту в соціології, можна припустити, що підвищення інтересу до порівняльним дослідженнямсприятиме і зростання кількості експериментів. Крім того, розвиток перспективних областеймікросоціології (наприклад, вивчення повсякденності) також може сприяти розвитку теорії та практики польового експериментування.

Найбільш очевидним полем впровадження експериментальних дослідженьпредставляється область віртуальних технологій.

Соціологічний експеримент зазвичай проводиться у лабораторії чи «реальних» умовах, при цьому вивчаються невеликі групи. Однак соціологія не цікавиться індивідом, а як пояснювальні конструкції оперує аргументами макрорівня, підтвердження яких вимагає безлічі спостережень. Мережі дають таку можливість. Наприклад, група молодих вчених із Колумбійського університету вивчала вплив соціальних факторівна функціонування музичного ринку. Для цього вони створили веб-сайт, на який виклали аудіозаписи 48 невідомих інді-музикантів для вільного скачування. Всі відвідувачі сторінки випадково призначалися до груп, які відрізнялися способом подання інформації на сайті ( випадковий порядокпісень проти ранжованого за кількістю скачувань і т. д.). З'ясувалося, що вибір користувачів, які мали соціальний вплив, Виявлявся куди менш передбачуваним, ніж тих, хто не бачив рейтингів, рекомендацій, кількості «лайків» і т.д., причому ця залежність зворотна пропорційна рівню соціального впливу.

У книзі «Підстави соціальної теорії» Дж. Коулман писав, що навіть якщо вчений будує каузальні аргументи на макрорівні (наприклад, як моделі соціальної взаємодіївпливають на силу норм), належне пояснення вимагає визначення мікропідстав цих процесів. Як підкреслював Коулман, перехід від мікро- до макрорівня є основною перешкодою на шляху інтелектуального розвитку соціологічної теоріїоскільки вимагає вивчення динамічних процесівформування та розвитку соціальних процесів, які складно отримати за допомогою традиційних соціологічних методик(Опитування та спостережень). Однак використання експериментального методу(зокрема, в інтернет-дослідженнях) дозволяє не лише побачити результат, а й відтворити схему переходів «макро-мікро», «мікро-мікро» та «макро-мікро». Фактично у розпорядженні дослідника є потужний інструмент, який, з одного боку, дозволяє працювати з великими масивами даних, а з іншого - фіксувати взаємодію індивідів per se.

Ще одна причина, через яку експеримент вартий уваги, більш прагматична. Як неодноразово зазначалося, тоді, коли експериментальний дизайн неможливий (а це стосовно, наприклад, до всієї історичної соціології), соціальний вчений намагається створити щось схоже на експериментальну ситуацію. Разом з тим складний характерпричинно-наслідкових відносин та необхідність контролю факторів вимагають використання методів, що симулюють експеримент. У такому разі експеримент є ідеально-типовим дослідженням, за канонами якого вчений працює і до суворості якого прагне наблизитися. Власне, кількісна та якісна стратегія, на думку Ч. Рагіна, є різними варіантамивідповіді на запитання про те, чи можливо в соціальному дослідженнівідтворення логіки експерименту .

Представлені вище плани є своєрідними шаблонами, за лекалами яких соціологи працюють і з об'єктами, щодо яких експеримент принципово неможливий. По суті, таке каузальне дослідження моделюватиметься і аналізуватиметься з використанням схожих, але, зрозуміло, складніших методик і технік. Тому у процесі вивчення гол. 10, присвяченій квазіекспериментальному дизайну, рекомендується співвідносити описувані плани з тим, що вже відомо, шукати відмінності та можливі загрози внутрішньої та зовнішньої валідності. Це полегшить розуміння «механіки» порівняльного квазіекспериментального дослідження.

• У. Кохран і Р. Кокс наводять приклади латинських квадратів до 12x12.

Повне вирівнювання

Для того щоб уникнути систематичного змішування, що виникає при неоднорідному перенесенні в схемі реверсивного зрівнювання, можна використовувати всі можливі послідовності рівнів, замість двох. Така схема з повним вирівнюванням для трирівневого експерименту виглядає так:

Так, якби в дослідженні Готтсданкера і Уей було використано лише три рівні незалежної змінної (наприклад 50, 100 і 200 мс), різним випробуваним - чи групам випробуваних - було б пред'явлено такі шість послідовностей: 50, 100, 200 мс; 50, 200 та 100 мс; 100, 50 та 200 мс; 100, 200 та 50 мс; 200, 50 та 100 мс; 200, 100 та 50 мс. Ми не ілюструємо повне вирівнювання для більшого числарівнів незалежної змінної (який зазвичай зустрічається в багаторівневих експериментах) з тієї причини, що таблиця виявилася б занадто громіздкою. Наприклад, для всіх п'яти рівнів у дослідженні Готтсданкера та Уей знадобилося 120 послідовностей. Так що якби навіть тільки один випробуваний проводився через одну послідовність, то число випробуваних виявилося б рівним 120. Число послідовностей, необхідних для повного зрівнювання, обчислюється як n-факторіал, де n - число рівнів. Для шести рівнів n-факторіал знаходиться наступною серією множень:

6Х5Х4ХЗХ2Х1 = 720.

Оскільки крос-індивідуальне зрівняння було введено для скорочення числа випробовуваних у порівнянні з їх числом у міжгруповій схемі, повне позиційне зрівняння використовується вкрай рідко. Нижченаведена схема дозволяє скоротити кількість піддослідних, уникаючи припущення про однорідне перенесення, необхідному для схеми реверсивного зрівнювання.

Якщо ми не хочемо використовувати всі можливі послідовності, то природно прийти до ідеї про випадковий вибір з усієї їхньої множини. Іноді це робиться. Однак у випадково вибраному наборі послідовностей мало ймовірно, що кожен рівень опиниться в кожній позиції рівне числоразів. Тому небажані наслідки неоднорідного перенесення, як і раніше, існуватимуть.

Виходом буде випадковий вибір серед «квадратів», у яких кожен рівень з'являється. одинраз на кожній позиції. Кожен такий квадрат є повною експериментальною схемою. Він називається латинським квадратом. Наведемо приклад одного з 8640 таких квадратів для шести рівнів незалежної змінної:

Оскільки в латинському квадраті кожен рівень виявляється у кожній позиції послідовності, природно, потрібно стільки груп випробуваних, скільки рівнів незалежної змінної. Якби Готтсданкер і Уей використовували (як це їм і слід було зробити) латинський квадрат замість реверсивного зрівнювання, їх випробувані мали б розбитись на п'ять груп відповідно до п'яти рівнів незалежної змінної. Значить, у їхньому досвіді мали б взяти участь п'ять чи десять піддослідних замість восьми, як це було насправді (адже вісім на п'ять не ділиться).

Дослідники зазвичай запроваджують обмеження на латинський квадрат. Воно полягає у вимогі, щоб кожному рівню один раз безпосередньо передувавкожен інший рівень. Такий квадрат називають збалансованим квадратом. У наведеному вище латинському квадраті цієї умови не дотримувалося. Наприклад, рівню Б тільки один раз передували рівні А і Д, але три рази Е і жодного разу В і Г. Метод отримання збалансованих квадратів наводиться у роботі Уагенаара (1969). Ось приклад:

Якби всі ефекти перенесення пов'язані з безпосередньо попереднім рівнем, збалансований квадрат був дуже ефективний. На жаль, немає способу перевірити, чи це насправді так. Розглянемо тепер систематичні змішання (впливи послідовності), які можуть виникати навіть за повного зрівнювання.

Латинський квадрат n-го порядку - таблиця L=(l ij)розмірів n × n, заповнена nелементами множини Mтаким чином, що в кожному рядку і в кожному стовпці таблиці кожен елемент Mтрапляється точно один раз. Приклад латинського квадрата 3-го порядку:

Вперше латинські квадрати (4-го порядку) були опубліковані в книзі «Шамс аль Маариф» («Книга про Сонце Гнозису»), написаній Ахмадом аль-Буні в Єгипті приблизно 1200 року.

Пари ортогональних латинських квадратів вперше були згадані Жаком Озанамом у 1725 році. У книзі, що є збірником завдань з фізики та математики, наведено таке завдання:

Це завдання має 6912 рішень (якщо додатково вимагати, щоб і діагоналі квадрата задовольняли тій самій умові, то число рішень зменшиться в 6 разів і дорівнюватиме 1152).

Важливою віхою історія досліджень латинських квадратів стала робота Ейлера . Він займався в ній методами побудови магічних квадратів і запропонував метод, що базується на парі ортогональних латинських квадратів. Досліджуючи такі пари, Ейлер з'ясував, що проблема їх побудови поділяється на три випадки залежно від залишку від поділу числа nна 4. Він запропонував способи побудови пар ортогональних квадратів для n, що діляться на 4 та для непарних n. Очевидно, що при n= 2 таких пар немає. Йому не вдалося побудувати пари ортогональних латинських квадратів для n= 6, 10 і він висловив гіпотезу про те, що не існує пар ортогональних квадратів для n = 4t+2. Для n= 6 він сформулював «завдання про 36 офіцерів»:

У 1920-1930 роки стали інтенсивно вивчатися неасоціативні алгебраїчні структури, що призвело, зокрема, до створення теорії квазігруп, тісно пов'язаної з вивченням латинських квадратів, оскільки між латинськими квадратами та таблицями Келі квазігруп існує взаємно-однозначна відповідність.

Точна формула для числа L(n) латинських квадратів n-го порядку невідома. Найкращі оцінкидля L(n) дає формула

Кожному латинському квадрату можна поставити у відповідність нормалізований (або редукований) латинський квадрат, у якого перший рядок і перший стовпець заповнені відповідно до порядку, заданого на множині M. Приклад нормалізованого латинського квадрата:

Число R(n)нормалізованих латинських квадратів n-го порядку (послідовність A000315 в OEIS) n! (n-1)!разів менше, ніж L(n)(Послідовність A002860 в OEIS).

Два латинські квадрати називають ізотопними, якщо один з них може бути отриманий з іншого в результаті ізотопії - композиції з перестановки рядків, перестановки стовпців та заміни елементів множини Mпо підстановці із симетричної групи S(M).

Латинський квадрат можна розглядати як ортогональний масив. Змінюючи порядок елементів у кожній упорядкованій трійці цього масиву, можна отримати 6 латинських квадратів, які називаються парастрофами. Зокрема, парастроф є латинський квадрат, отриманий в результаті транспонування.

Композиція ізотопії та парастрофії називається ізотрофією. Це ще одне ставлення до еквівалентності, його класи називаються головними класами. Кожен головний класмістить 1, 2, 3 чи 6 ізотопічних класів. У разі збігу вихідного латинського квадрата та ізострофного йому говорять про автострофію. Зі зростанням nБагато латинські квадрати мають очевидну групу автострофій.

Два латинські квадрати L=(l ij)і K=(k ij) n-го порядку називаються ортогональними, якщо всі упорядковані пари (l ij, k ij)різні. Приклад двох ортогональних латинських квадратів та відповідні їм упорядковані пари:

Ейлер називав такі квадрати "повними". На його честь у науковій літературіїх раніше називали «ейлеровими» або «греко-латинськими» (оскільки Ейлер використовував літери грецького алфавіту для квадрата, ортогонального латинському).

Ортогональні латинські квадрати існують для будь-якого n, Не рівного 2 і 6.

Латинський квадрат L n-го порядку має ортогональний йому квадрат тоді і лише тоді, коли в Lіснує nнепересічних трансверсалей.

Особливий інтересу зв'язку з численними додатками викликають безліч із кількох попарно ортогональних латинських квадратів n-го порядку. Максимально можлива потужність N(n)такої множини дорівнює n-1, у цьому випадку множина називається повним.

Якщо n≡ 1 (mod 4) або n≡ 2 (mod 4) та вільна від квадрата частина числа nмістить хоча б один простий множник p≡ 3 (mod 4), то для таких nповної множини попарно ортогональних латинських квадратів немає.

Відомі нижні оцінки числа N(n)при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Побудова ортогональних квадратів – складне комбінаторне завдання. Для її вирішення застосовуються як алгебраїчні конструкції, так і комбінаторні (трансверсалі, ортогональні масиви, дизайни, блок-схеми, трійки Штейнера та ін.) Існує кілька підходів до вирішення цього завдання, їх можна поділити на дві групи. До першої групи відносяться способи, засновані на виборі базового латинського квадрата, до якого знаходяться ізотопні ортогональні латинські квадрати. Наприклад, п'ять попарно ортогональних латинських квадратів 12-го порядку було знайдено в результаті побудови чотирьох ортоморфізмів абелевої групи, що є прямим добутком циклічних груп порядків 6 і 2.

До другої групи належать методи, що використовують для побудови ортогональних латинських квадратів комбінаторні об'єкти (включаючи латинські квадрати) менших порядків. Наприклад, два латинські квадрати 22-го порядку були побудовані Bose та Shrikhande на основі двох дизайнів 15-го та 7-го порядку.

Латинський квадрат називається діагональним, якщо на додаток до вимог унікальності елементів у рядках та стовпцях, властивим для латинського квадрата, додаються вимоги унікальності елементів на головній та побічній діагоналях. Аналітична оцінкачисла діагональних латинських квадратів невідома, їх кількість для розмірностей N<10 было определено в 2016 г. в проекте добровольных распределенных вычислений [email protected](послідовність A274171 OEIS і послідовність A274806 OEIS). Для діагональних латинських квадратів, як і для просто латинських, можлива побудова ортогональних пар, частина з яких (порядку 9 та 10) була знайдена у проекті добровільних розподілених обчислень A287695 у OEIS). Відкритою математичною проблемою є існування трійки попарно-ортогональних діагональних латинських квадратів порядку 10 (на даний момент найкращим наближенням до її вирішення є трійка квадратів, в якій дві пари квадратів ортогональні, а третя частково ортогональна в 74 осередках).

Квадрат, в якому кожен елемент множини Mу кожному рядку та у кожному стовпці зустрічається не більше одного разу, називається частковим.

Завдання розпізнавання того, чи частковий квадрат може бути доповнений до латинського, є NP-повною .

Введено поняття критичної множини, що відповідає частковому квадрату, який однозначно може бути доповнений до латинського, причому ніяке його підмножина умові однозначності не задовольняє. Потужність C(n)критичної множини для квадратів розмірів n × nвідома для n < 7:

Крім задачі знаходження формули для величини L(n), є велика кількість невирішених завдань щодо латинських квадратів. Низка таких завдань була сформульована на конференції Loops’03:

Латинські квадрати знаходять широке застосування в алгебрі, комбінаториці, статистиці, криптографії, теорії кодів та багатьох інших областях.

Існує низка ігор, у яких використовуються латинські квадрати. Найбільш відома з них судоку. У ній потрібно частковий квадрат доповнити до латинського квадрата 9-го порядку, що має додаткову властивість: всі дев'ять його підквадратів містять по одному разу всі натуральні числа від 1 до 9.

Популярні також завдання побудови латинських квадратів і на їх основі магічних квадратів, що мають додаткові властивості (наприклад, діагональні квадрати).

Почала писати оглядову статтю про методи побудови магічних квадратів. Штудую матеріали на цю тему у всіх джерелах. Ось у книзі Чебракова знаходжу "Метод латинських квадратів" (Ю. В. Чебраков. Магічні квадрати. Терія чисел, алгебра, комбінаторний аналіз. - С.-Петербург, 1995; стор.96-97).
Цитата з книги: "Перший латинський квадрат будують наступним чином: а) довільно заповнюють нижній горизонтальний ряд квадратної таблиці n * n цілими числами від 0 до n-1, стежачи лише за тим, щоб остання клітина горизонтального ряду була заповнена числом k ="; б) решта горизонтальних рядів таблиці заповнюють знизу вгору так, щоб кожен наступний ряд виходив з попередньої циклічної перестановки - перше число переноситься в кінець рядка. Другий латинський квадрат виходить із першого шляхом його повороту на дев'яносто градусів".
Ну як будується перший латинський квадрат, зрозуміло. У книзі дана ілюстрація побудови. Ось перший латинський квадрат, зображений на ілюстрації:

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

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

11 9 25 2 18
19 15 7 23 1
5 17 13 6 24
22 3 16 14 10
8 21 4 20 12

12 10 21 4 18
20 11 9 23 2
1 19 13 7 25
24 3 17 15 6
8 22 5 16 14

3 2 5 0 1 4 6
6 3 2 5 0 1 4
4 6 3 2 5 0 1
1 4 6 3 2 5 0
0 1 4 6 3 2 5
5 0 1 4 6 3 2
2 5 0 1 4 6 3