Konstruktion eines orthogonal-diagonalen griechisch-lateinischen Quadrats

Betrachten Sie ein Raster aus Nx Neindeutigen Elementen. Jedes Element hat einen Buchstaben (von A bis Neinschließlich th) und eine Zahl (von 1 bis Neinschließlich). Daher befindet sich jedes Zahlen- / Buchstabenpaar genau einmal im Raster.

Ihre Aufgabe ist es, ein Raster so anzuordnen, dass:

Jede Zeile, Spalte und Diagonale (einschließlich Umbruch) enthält jeden Buchstaben und jede Zahl genau einmal.

Mit Wickeln meine ich das

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

ist eine Diagonale, zusammen mit allen ähnlichen Diagonalen, die die Kanten treffen.

Ein Beispielraster 5x5ist:

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

Ihre Aufgabe ist es, ein Programm zu schreiben, das eine Zahl akzeptiert N, und ein Nx- NRaster wie oben beschrieben zu drucken . Ihr Programm sollte für jeden funktionieren 0 < N <= 26. Wenn ein bestimmtes Raster nicht möglich ist, sollten Sie drucken Impossible.

Das Hardcodieren der Antwort für eine Nist nicht erlaubt. Ein Programm ist fest codiert, wenn es das Raster auf unterschiedliche Weise (wie von mir beurteilt) für eines N > 26berechnet (oder wenn es nicht berechnet werden kann). (Dies soll eine Vorberechnung verhindern, einschließlich vorberechneter ungültiger Gitter oder Offsets für bestimmte Gitter).

Dies ist ein Problem mit dem schnellsten Code, und Ihre Punktzahl ist die Summe der Zeiten, die benötigt wurden, um Ihr Programm auf allen möglichen NComputern auf meinem Computer auszuführen . Bitte lassen Sie in Ihrer Antwort Ihr Programm über alle laufen N(ich muss es also nur einmal zeitlich festlegen). Wenn kein Programm es in weniger als 60 Sekunden berechnen kann, ist der Gewinner die Antwort, die das Raster mit dem größten Nin 60 Sekunden berechnen kann . Wenn mehrere Programme das gleiche Maximum haben N, ist der Tiebreaker die schnellste Lösung.

(Ich habe einen Windows 8-Computer mit anständiger Stromversorgung, und alle erforderlichen Compiler oder Interpreter müssen dafür frei verfügbar sein.)

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

Wie es funktioniert?

Die naive Implementierung würde darin bestehen, alle möglichen Anordnungen von Buchstaben und Zahlen in einem NxN-Raster zu durchsuchen und nach einem zu suchen, das auch ein orthogonal-diagonales lateinisches Quadrat (ODLS) ist (und daher müsste es für einige nur alle durchlaufen Konfigurationen und Rückgabe unmöglich). Ein solcher Algorithmus würde dieser Herausforderung aufgrund der absurden Zeitkomplexität nicht gerecht. Es gibt also drei wesentliche Vereinfachungen und Begründungen (teilweise Beweise und Einsichten, warum es funktioniert) für ODLS-Konstruktionen, die in meiner Implementierung verwendet werden:

Die erste ist die Vorstellung, dass wir nur ein gültiges diagonales lateinisches Quadrat (ein NxN-Gitter, so dass jede Zeile, Spalte, umschlossene Diagonale jedes Element einer Menge von N verschiedenen Elementen genau einmal enthält) der ersten N Buchstaben der Alphabet. Wenn wir ein solches diagonales lateinisches Quadrat (DLS) konstruieren können, kann ein ODLS unter Verwendung des DLS mit geeignetem Austausch von Elementen und Umdrehen konstruiert werden. Rechtfertigung:

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.

Die zweite Vereinfachung ist die Vorstellung, dass, wenn wir eine geeignete Konfiguration (SC) eines Elements gefunden hätten (ein NxN-Gitter, so dass jede Zeile, Spalte, umschlossene Diagonale dieses Element genau einmal enthält), ein DLS durch Ersetzen des Elements konstruiert werden könnte und Verschieben des SC. Rechtfertigung:

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.

Die letzte Vereinfachung lautet wie folgt: Alle DLS der Primzahl N mit Ausnahme von N = 2 oder N = 3 können konstruiert werden, und wenn N in zwei Zahlen zerlegt werden kann, deren geeignete DLS konstruiert werden kann, kann eine DLS dieser N konstruiert werden gebaut werden. Ich vermute, dass das Gegenteil auch gilt. (Mit anderen Worten, wir können nur einen DLS für N konstruieren, der nicht durch 2 oder 3 teilbar ist.)

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 

Ein Bild von dem, was ich mit dem kleineren - größeren DLS gemeint habe

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)