Construction d'un carré gréco-latin orthogonal-diagonal

Considérons une grille de Nx Néléments uniques. Chaque élément a une lettre (de A à la Ne lettre, inclus) et un nombre (de 1 à N, inclus). Par conséquent, chaque paire chiffre / lettre se trouve dans la grille exactement une fois.

Votre travail consiste à organiser une grille telle que:

Chaque ligne, colonne et diagonale (y compris l'habillage) contient chaque lettre et chiffre exactement une fois.

En enveloppant, je veux dire que

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

est une diagonale, avec toutes les diagonales similaires qui frappent les bords.

Un exemple de 5x5grille est:

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

Votre tâche consiste à écrire un programme qui accepte un nombre N, et à imprimer une grille Nx Ncomme décrit ci-dessus. Votre programme devrait fonctionner pour tout 0 < N <= 26. Si une grille particulière n'est pas possible, vous devez imprimer Impossible.

Le codage en dur de la réponse Nn'est pas autorisé. Un programme est codé en dur s'il calcule la grille de manière différente (selon moi) pour tout N > 26(ou s'il ne parvient pas à calculer). (Ceci est destiné à empêcher le précalcul, y compris les grilles invalides précalculées ou les décalages pour des grilles données).

C'est un problème de code le plus rapide, et votre score est la somme des temps nécessaires pour exécuter votre programme sur tous les possibles Nsur mon ordinateur. Dans votre réponse, veuillez exécuter votre programme sur tout N(je n'ai donc à le chronométrer qu'une seule fois). Si aucun programme ne peut le calculer en moins de 60 secondes, le gagnant est la réponse qui peut calculer la grille avec la plus grande Nen 60 secondes. Si plusieurs programmes ont le même maximum N, le bris d'égalité est la solution la plus rapide.

(J'ai une machine Windows 8 correctement alimentée, et tous les compilateurs ou interprètes nécessaires doivent être disponibles gratuitement).

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

Comment ça fonctionne?

La mise en œuvre naïve consisterait à parcourir tous les arrangements possibles de lettres et de chiffres dans une grille NxN et à en rechercher un qui est également un carré latin orthogonal-diagonal (ODLS) (et donc, pour certains, il suffirait de parcourir tous les configurations et retour impossible). Un tel algorithme ne répondrait pas à ce défi en raison d'une complexité temporelle absurde. Il y a donc trois simplifications et justifications majeures (preuves partielles et aperçu de pourquoi cela fonctionne) aux constructions ODLS utilisées dans mon implémentation:

La première est la notion selon laquelle il suffit de générer un carré latin diagonal valide (une grille NxN telle que chaque ligne, colonne, diagonale enveloppée contient chaque élément d'un ensemble de N éléments distincts exactement une fois) des N premières lettres du alphabet. Si nous pouvons construire un tel carré latin diagonal (DLS), un ODLS peut être construit en utilisant le DLS avec un échange d'éléments approprié et un retournement. Justification:

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 deuxième simplification est la notion que si nous trouvions une configuration (SC) appropriée d'un élément (une grille NxN telle que chaque ligne, colonne, diagonale enveloppée contient cet élément exactement une fois), alors un DLS pourrait être construit en remplaçant l'élément et déplacer le SC. Justification:

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 dernière simplification est la suivante - tous les DLS de N premiers, à l'exception de N = 2 ou N = 3, peuvent être construits, et si N peut être factorisé en deux nombres dont le DLS approprié peut être construit, alors un DLS de ce N peut être construit. Je suppose que l'inverse est également valable. (En d'autres termes, nous ne pouvons construire qu'un DLS pour N qui n'est pas divisible par 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 

Une image de ce que je voulais dire avec le DLS plus petit - plus grand

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)