Construção de um quadrado greco-latino ortogonal-diagonal

Considere uma grade de Nx Nelementos únicos. Cada elemento possui uma letra (de A à Nquinta letra, inclusive) e um número (de 1 a N, inclusive). Portanto, cada par de número / letra está na grade exatamente uma vez.

Seu trabalho é organizar uma grade de modo que:

Cada linha, coluna e diagonal (incluindo quebra automática) contém cada letra e número exatamente uma vez.

Ao envolver, quero dizer que

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

é uma diagonal, juntamente com todas as diagonais semelhantes que atingem as bordas.

Uma 5x5grade de exemplo é:

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

Sua tarefa é escrever um programa que aceite um número Ne imprimir uma grade Nx Nconforme descrito acima. Seu programa deve funcionar para qualquer um 0 < N <= 26. Se uma grade específica não for possível, você deverá imprimir Impossible.

A resposta codificada para qualquer Nnão é permitida. Um programa é codificado permanentemente se calcula a grade de maneira diferente (conforme julgado por mim) para qualquer N > 26(ou se não conseguir calcular). (Isso visa impedir o pré-cálculo, incluindo grades inválidas pré-calculadas ou compensações para determinadas grades).

Esse é um problema de código mais rápido e sua pontuação é a soma dos tempos necessários para executar seu programa em todos os possíveis Nno meu computador. Em sua resposta, faça com que seu programa seja executado em todos N(portanto, só preciso cronometrar uma vez). Se nenhum programa puder computá-lo em menos de 60 segundos, o vencedor é a resposta que pode calcular a grade com a maior Nem 60 segundos. Se vários programas tiverem o mesmo máximo N, o desempatador é a solução mais rápida.

(Eu tenho uma máquina Windows 8 com alimentação decente e todos os compiladores ou intérpretes necessários devem estar disponíveis gratuitamente para ela).

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")

Como funciona?

A implementação ingênua seria examinar todos os arranjos possíveis de letras e números em uma grade NxN e procurar um que também seja um quadrado latino ortogonal-diagonal (ODLS) (e, portanto, para alguns, seria necessário apenas configurações e retorno impossível). Esse algoritmo não se adequaria a esse desafio devido à complexidade absurda do tempo. Portanto, existem três grandes simplificações e justificativas (provas parciais e insights sobre por que ele funciona) para construções ODLS usadas em minha implementação:

A primeira é a noção de que precisamos gerar apenas um quadrado latino diagonal válido (uma grade NxN de modo que cada linha, coluna, diagonal empacotada contenha cada elemento de um conjunto de N elementos distintos exatamente uma vez) das primeiras N letras do alfabeto. Se podemos construir um quadrado latino diagonal (DLS), um ODLS pode ser construído usando o DLS com troca de elementos apropriada e inversão. Justificação:

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.

A segunda simplificação é a noção de que, se encontrarmos uma configuração adequada (SC) de um elemento (uma grade NxN de modo que cada linha, coluna, diagonal agrupada contenha esse elemento exatamente uma vez), um DLS poderá ser construído substituindo o elemento e mudando o SC. Justificação:

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.

A última simplificação é a seguinte - todos os DLS do N principal, exceto N = 2 ou N = 3, podem ser construídos, e se N pode ser fatorado em dois números cujo DLS apropriado pode ser construído, então um DLS desse N pode ser construído. Suponho que o inverso também vale. (Em outras palavras, só podemos construir um DLS para N que não seja divisível por 2 ou 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 

Uma imagem do que eu quis dizer com o DLS menor - maior

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)