Budowa prostopadłościennego kwadratu grecko-łacińskiego

Rozważ siatkę Nx Nunikalnych elementów. Każdy element ma literę (od A do Nth, włącznie) i liczbę (od 1 do Nwłącznie). Dlatego każda para cyfr / liter znajduje się w siatce dokładnie raz.

Twoim zadaniem jest takie ułożenie siatki, aby:

Każdy rząd, kolumna i przekątna (w tym zawijanie) zawiera dokładnie jedną literę i cyfrę.

Mówiąc o opakowaniu, mam na myśli to

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

jest przekątną, wraz ze wszystkimi podobnymi przekątnymi, które uderzają o krawędzie.

Przykładowa 5x5siatka to:

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

Twoim zadaniem jest napisanie programu, który akceptuje liczbę N, i wydrukowanie siatki Nx Nzgodnie z powyższym opisem. Twój program powinien działać dla każdego 0 < N <= 26. Jeśli określona siatka nie jest możliwa, należy wydrukować Impossible.

Twarde kodowanie odpowiedzi na dowolne Njest niedozwolone. Program jest zakodowany na stałe, jeśli oblicza siatkę w inny sposób (według mnie) dla dowolnego N > 26(lub jeśli nie oblicza). (Ma to na celu zapobieganie wstępnemu obliczeniu, w tym wstępnie obliczonym nieprawidłowym siatkom lub przesunięciom dla danych siatek).

Jest to problem z najszybszym kodem, a twój wynik to suma czasu potrzebnego do uruchomienia twojego programu na wszystkich możliwych Nkomputerach. W odpowiedzi proszę o uruchomienie całego programu N(więc muszę go tylko raz ustalić). Jeśli żaden program nie jest w stanie go obliczyć w czasie krótszym niż 60 sekund, zwycięzca jest odpowiedzią, która może obliczyć tabelę z największą Nw 60 sekund. Jeśli wiele programów ma takie same maksimum N, rozstrzygnięcie jest najszybszym rozwiązaniem.

(Mam przyzwoicie zasilaną maszynę z Windows 8 i wszelkie potrzebne kompilatory lub tłumacze muszą być dla niej swobodnie dostępne).

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

Jak to działa?

Naiwną implementacją byłoby przejrzenie wszystkich możliwych układów liter i cyfr w siatce NxN i poszukiwanie takiego, który jest również prostopadłościennym przekątnym łacińskim kwadratem (ODLS) (a zatem dla niektórych musiałby po prostu przejść przez wszystkie konfiguracje i zwrot niemożliwe). Taki algorytm nie pasowałby do tego wyzwania z powodu absurdalnej złożoności czasu. Istnieją więc trzy główne uproszczenia i uzasadnienia (częściowe dowody i spostrzeżenia, dlaczego to działa) konstrukcji ODLS zastosowanych w mojej implementacji:

Pierwszym jest założenie, że wystarczy wygenerować prawidłowy przekątny łaciński kwadrat (siatka NxN taka, że ​​każdy wiersz, kolumna, zawinięta diagonalnie zawiera każdy element zbioru N odrębnych elementów dokładnie raz) pierwszych N liter alfabet. Jeśli możemy zbudować taki przekątny kwadrat łaciński (DLS), wówczas można zbudować ODLS za pomocą DLS z odpowiednią wymianą elementów i przerzucaniem. Usprawiedliwienie:

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.

Drugim uproszczeniem jest założenie, że jeśli znaleźliśmy odpowiednią konfigurację (SC) jednego elementu (siatka NxN, tak że każdy rząd, kolumna, zawinięta diagonalnie zawiera ten element dokładnie jeden raz), wówczas można zbudować DLS poprzez zastąpienie elementu i przesunięcie SC. Usprawiedliwienie:

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.

Ostatnie uproszczenie jest następujące - wszystkie DLS pierwszej N, z wyjątkiem N = 2 lub N = 3, mogą być skonstruowane, a jeśli N może być podzielony na dwie liczby, których odpowiedni DLS może być skonstruowany, to DLS tej N może być zbudowanym. Przypuszczam, że tak samo jest w przypadku rozmowy. (Innymi słowy, możemy zbudować DLS tylko dla N, którego nie można podzielić przez 2 lub 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 

Obraz tego, co miałem na myśli z mniejszym - większym DLS

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)