Construyendo un cuadrado greco-latino ortogonal-diagonal

Considere una cuadrícula de Nx Nelementos únicos. Cada elemento tiene una letra (de A a la Nletra, inclusive) y un número (de 1 a N, inclusive). Por lo tanto, cada par número / letra está en la cuadrícula exactamente una vez.

Su trabajo es organizar una cuadrícula de manera que:

Cada fila, columna y diagonal (incluida la envoltura) contiene cada letra y número exactamente una vez.

Al envolver, quiero decir que

* * * # *
* * # * * 
* # * * *
# * * * *
* * * * #

es una diagonal, junto con todas las diagonales similares que golpean los bordes.

Un ejemplo de 5x5cuadrícula es:

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

Su tarea es escribir un programa que acepte un número Ne imprimir una cuadrícula Nx Ncomo se describió anteriormente. Su programa debería funcionar para cualquiera 0 < N <= 26. Si no es posible una cuadrícula en particular, debe imprimir Impossible.

Codificar la respuesta para cualquiera Nno está permitido. Un programa está codificado si calcula la cuadrícula de manera diferente (según mi criterio) para cualquiera N > 26(o si no puede calcular). (Esto está destinado a evitar el precalculado, incluidas las cuadrículas inválidas precalculadas o las compensaciones para cuadrículas determinadas).

Este es un problema de código más rápido, y su puntaje es la suma de los tiempos necesarios para ejecutar su programa en todo lo posible Nen mi computadora. En su respuesta, haga que su programa se ejecute en todos N(así que solo tengo que cronometrarlo una vez). Si ningún programa puede calcularlo en menos de 60 segundos, entonces el ganador es la respuesta que puede calcular la cuadrícula con la mayor Nen 60 segundos. Si varios programas tienen el mismo máximo N, entonces el desempate es la solución más rápida.

(Tengo una máquina con Windows 8 decente, y todos los compiladores o intérpretes necesarios deben estar disponibles de forma gratuita).

Python 3

letters = []
numbers = []
for n in range(1,27): 
    if n%2==0 or n%3==0:
        offsets=False
    else:
        offsets = [x for x in range(0,n,2)]
        offsets.extend([x for x in range(1,n,2)])
    letters.append(chr(96+n))
    numbers.append(n)
    if offsets :
        for y in range(n):
            for x in range(n):
                let=letters[(x+offsets[y])%n]
                num=numbers[(offsets[y]-x)%n]
                print (let+str(num), end= "  " if num<10 else " ")
            print("\n")     
    else: 
        print("Impossible\n")

¿Cómo funciona?

La implementación ingenua sería mirar a través de todos los arreglos posibles de letras y números en una cuadrícula NxN y buscar uno que también sea un Cuadrado Latino Ortogonal-Diagonal (ODLS) (y, por lo tanto, para algunos solo tendría que pasar por todos configuraciones y retorno imposibles). Tal algoritmo no sería adecuado para este desafío debido a la absurda complejidad del tiempo. Por lo tanto, existen tres simplificaciones y justificaciones principales (pruebas parciales e información sobre por qué funciona) para las construcciones ODLS utilizadas en mi implementación:

La primera es la noción de que solo necesitamos generar un Diagonal Latin Square válido (una cuadrícula NxN tal que cada fila, columna, diagonal envuelta contenga cada elemento de un conjunto de N elementos distintos exactamente una vez) de las primeras N letras de la alfabeto. Si podemos construir un Cuadrado Latino Diagonal (DLS), entonces se puede construir un ODLS usando el DLS con el intercambio apropiado de elementos y volteo. Justificación:

Let us first look at an example using the example grid
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
Every ODLS can be separated into two DLS (by definition), so
we can separate the grid above into two DLS, one containing letters, the other - numbers
a b c d e
c d e a b
e a b c d
b c d e a
d e a b c
and
1 2 3 4 5 
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4 
3 4 5 1 2
If we transform the number DLS by the mapping 1-->e, 2-->d, 3-->c, 4-->b, 5-->a,
1 2 3 4 5 --> e d c b a
4 5 1 2 3 --> b a e d c
2 3 4 5 1 --> d c b a e
5 1 2 3 4 --> a e d c b
3 4 5 1 2 --> c b a e d
Now if we put the transformed number grid next to the original letter grid,
Original  | Transformed
a b c d e | e d c b a
c d e a b | b a e d c
e a b c d | d c b a e
b c d e a | a e d c b
d e a b c | c b a e d
It can be clearly seen that the number grid is a horizontal flip of
the letter grid withminor letter to number substitutions.
Now this works because flipping guarantees that no two pairs occur more than once,
and each DLS  satisfies the requirements of the ODLS.

La segunda simplificación es la noción de que si encontramos una configuración adecuada (SC) de un elemento (una cuadrícula NxN de manera que cada fila, columna, diagonal envuelta contenga ese elemento exactamente una vez), se podría construir un DLS reemplazando el elemento y cambiando el SC. Justificación:

If "_" is an empty space and "a" the element then a valid SC of a 7x7 grid is
a _ _ _ _ _ _
_ _ a _ _ _ _
_ _ _ _ a _ _
_ _ _ _ _ _ a
_ a _ _ _ _ _ 
_ _ _ a _ _ _
_ _ _ _ _ a _
or
a _ _ _ _ _ _
_ _ _ a _ _ _
_ _ _ _ _ _ a
_ _ a _ _ _ _
_ _ _ _ _ a _ 
_ a _ _ _ _ _
_ _ _ _ a _ _
(the second one can actually be obtained from the first one via rotation)
now say we took the second SC, shifted it one unit to the right and 
replaced all "a" with "b"
a _ _ _ _ _ _       _ a _ _ _ _ _       _ b _ _ _ _ _
_ _ _ a _ _ _       _ _ _ _ a _ _       _ _ _ _ b _ _
_ _ _ _ _ _ a       a _ _ _ _ _ _       b _ _ _ _ _ _
_ _ a _ _ _ _  -->  _ _ _ a _ _ _  -->  _ _ _ b _ _ _
_ _ _ _ _ a _       _ _ _ _ _ _ a       _ _ _ _ _ _ b
_ a _ _ _ _ _       _ _ a _ _ _ _       _ _ b _ _ _ _
_ _ _ _ a _ _       _ _ _ _ _ a _       _ _ _ _ _ b _
Now if we overlaid the SC of "a" with the SC of "b" we get
a b _ _ _ _ _
_ _ _ a b _ _
b _ _ _ _ _ a
_ _ a b _ _ _
_ _ _ _ _ a b 
_ a b _ _ _ _
_ _ _ _ a b _
If we repeated these steps for the other five letters, we would arrive at a DLS
a b c d e f g
e f g a b c d
b c d e f g a
f g a b c d e
c d e f g a b 
g a b c d e f
d e f g a b c
This is a DLS, since each SC follows the general requirements of a DLS 
and shifting ensured that each element has its own cell.
Another thing to note is that each row contains the string "abcdefg" that is offset 
by some cells. This leads to another simplification: we only need to find the 
offsets of the string in every row and we are finished.

La última simplificación es la siguiente: todos los DLS de N primo, excepto N = 2 o N = 3, pueden construirse, y si N puede factorizarse en dos números cuyo DLS apropiado puede construirse, entonces un DLS de ese N puede ser construido Supongo que lo contrario también es válido. (En otras palabras, solo podemos construir un DLS para N que no sea divisible por 2 o 3)

Pretty obvious why 2x2 or 3x3 cant be made. For any other prime this can be done
by assigning a each consecutive row a shift that is by two bigger than the previous, 
for N=5 and N=7 this looks like (with elements other than "a" ommited)
N=5
a _ _ _ _ offset = 0
_ _ a _ _ offset = 2
_ _ _ _ a offset = 4
_ a _ _ _ offset = 6 = 1 (mod 5)
_ _ _ a _ offset = 8 = 3 (mod 5)
N=7
a _ _ _ _ _ _ offset = 0
_ _ a _ _ _ _ offset = 2
_ _ _ _ a _ _ offset = 4
_ _ _ _ _ _ a offset = 6
_ a _ _ _ _ _ offset = 8 = 1 (mod 7)
_ _ _ a _ _ _ offset = 10 = 3 (mod 7)
_ _ _ _ _ a _ offset = 12 = 5 (mod 7
(Why this works on all prime N (actually all N that are not divisible
by 3 or 2) can probably be proven via some kind of induction but i will
omit that, this is just what my code uses and it works)
Now, the first composite number that is not
divisible by 2 or 3 is 25 (it also occurs in the range our program must test)
Let A denote the DLS of N = 5
a b c d e 
d e a b c 
b c d e a 
e a b c d 
c d e a b
Let F be the DLS A where each letter is substituted by the letter five postions after it 
a-->f, b-->g etc. So F is 
f g h i j 
j e f g h 
g h i j f 
j f g h i 
h i j f g
Let K be the DLS a where each letter is substituted by the letter ten postions after it
a-->k, b--> l etc.
Let P be defined likewise (so a-->p, b-->q etc)
Let U be defined likewise (so a-->u, b-->v etc)
Now, since the DLS A could be constructed, then by substituting a --> A, b--> F etc.
we get a DLS of N=5*5 (A has five rows and five columns and each is filled with a 
grid of five rows and five columns)
A F K P U
P U A F K
F K P U A
U A F K P
K P U A F
Now since smaller DLS in the big DLS satisfies the 
conditions of a DLS and the big one also satisfies the DLS conditions,
then the resulting grid is also a DLS 

Una imagen de lo que quise decir con el DLS más pequeño y más grande

Now this kind of thing works for all constructible N and can be proven similiarly.

I have a strong sense that the converse (if some N isnt constructible
(2 and 3) then no multiple of that N is constructible) is also true but have a hard time 
proving it (test data up to N=30 (took a veeery long time to calculate) confirm it though)