Рассмотрим сетку из N
x N
уникальных элементов. Каждый элемент имеет букву (от А до N
ой буквы включительно) и цифру (от 1 до N
включительно). Следовательно, каждая пара цифра / буква находится в сетке ровно один раз.
Ваша задача состоит в том, чтобы устроить сетку так, чтобы:
Каждая строка, столбец и диагональ (включая перенос) содержат каждую букву и цифру ровно один раз.
Под оберткой я подразумеваю, что
* * * # *
* * # * *
* # * * *
# * * * *
* * * * #
является диагональю, наряду со всеми подобными диагоналями, которые ударяют края.
Пример 5x5
сетки:
A1 B2 C3 D4 E5
C4 D5 E1 A2 B3
E2 A3 B4 C5 D1
B5 C1 D2 E3 A4
D3 E4 A5 B1 C2
Ваша задача - написать программу, которая принимает число N
, и распечатать сетку N
х, N
как описано выше. Ваша программа должна работать для любого 0 < N <= 26
. Если конкретная сетка невозможна, то вам следует распечатать Impossible
.
Жесткое кодирование ответа N
не допускается. Программа жестко запрограммирована, если она рассчитывает сетку по-разному (как мне кажется) для любого N > 26
(или если она не может рассчитать). (Это предназначено для предотвращения предварительного расчета, включая предварительно рассчитанные недействительные сетки или смещения для заданных сеток).
Это самая быстрая проблема с кодом, и ваш счет - это сумма времени, затраченного на выполнение вашей программы на всем N
моем компьютере. В своем ответе, пожалуйста, запустите вашу программу для всех N
(так что мне нужно всего лишь один раз рассчитать время). Если ни одна программа не может вычислить его менее чем за 60 секунд, то победителем является ответ, который может рассчитать сетку с наибольшим значением N
за 60 секунд. Если несколько программ имеют одинаковый максимум N
, то средство разрешения конфликтов является самым быстрым решением.
(У меня достаточно приличный компьютер с Windows 8, и любые необходимые компиляторы или интерпретаторы должны быть в свободном доступе для него).
источник
Ответы:
Python 3
Как это работает?
Наивная реализация состояла бы в том, чтобы просмотреть все возможные расположения букв и цифр в сетке NxN и найти тот, который также является ортогонально-диагональным латинским квадратом (ODLS) (и, таким образом, для некоторых он просто должен пройти через все Конфигурации и вернуть невозможно). Такой алгоритм не подходит для этой задачи из-за абсурдной временной сложности. Итак, есть три основных упрощения и обоснования (частичное доказательство и понимание того, почему это работает) для конструкций ODLS, используемых в моей реализации:
Во-первых, это понятие, что нам нужно только создать действительный диагональный латинский квадрат (сетка NxN такая, что каждая строка, столбец, обернутая диагональ содержит каждый элемент из набора из N различных элементов ровно один раз) из первых N букв алфавит. Если мы можем построить такой диагональный латинский квадрат (DLS), тогда можно построить ODLS, используя DLS с соответствующим обменом элементами и переключением. Обоснование:
Второе упрощение заключается в том, что, если мы нашли подходящую конфигурацию (SC) одного элемента (сетка NxN, в которой каждая строка, столбец, диагональ обернутая содержит этот элемент ровно один раз), то DLS можно построить, заменив элемент и сдвигая СЦ. Обоснование:
Последнее упрощение заключается в следующем: все DLS простого N, за исключением N = 2 или N = 3, могут быть построены, и если N можно разложить на два числа, для которых можно построить соответствующий DLS, то DLS этого N может быть построенным. Я предполагаю, что обратное также верно. (Другими словами, мы можем построить только DLS для N, который не делится на 2 или 3)
Изображение того, что я имел в виду с меньшим - большим DLS
источник