Zadanie

Biorąc pod uwagę wejście N, wygeneruj i wyślij siatkę NxN, w której każdy wiersz, kolumna i dwie przekątne zawierają liczby od 1 do N(lub od 0 do N-1, jeśli jest to łatwiejsze).

Wkład

Dane wejściowe to dodatnia liczba całkowita N. Reprezentuje liczbę kolumn i wierszy w siatce. W przypadku tego problemu można założyć N, że będzie to rozsądny rozmiar 4 ≤ N ≤ 8lub ( 1 ≤ N ≤ 8jeśli skorzystasz z bonusu poniżej).

Wydajność

Wyjściem będzie siatka N× N. W siatce każdy wiersz zawiera tylko liczby od 1 do N, każda kolumna zawiera tylko liczby od 1 do N, a dwie przekątne długości N(jedna od (0,0)do (N-1,N-1)i jedna od (0,N-1)do (N-1, 0)) zawierają tylko liczby od 1 do N. Możesz użyć cyfr od 0 do N−1. Dla każdego Nistnieje wiele możliwych rozwiązań, wystarczy wydrukować tylko pierwsze znalezione. Nie musisz drukować spacji między liczbami.

Ograniczenia

Twój kod powinien być w stanie powtarzalnie generować wyniki dla N >= 7. Oznacza to, że jeśli jesteś w stanie uruchomić i za N = 7każdym razem uzyskać rozwiązanie z kodu, jesteś dobry. Jeśli chodzi o limit bezwzględny, Twój kod powinien być w stanie rozwiązać N = 7w ciągu mniej niż 10 minut za każdym razem, gdy go uruchomisz (tj. Jeśli zależysz od liczb losowych, w najgorszym przypadku kod powinien nadal kończyć się w mniej niż 10 minut N = 7) .

Przykłady

• Wkład: 4

  Jedno możliwe wyjście:

  1 2 3 4
  3 4 1 2
  4 3 2 1
  2 1 4 3
  

• Wkład: 5

  Jedno możliwe wyjście:

  1 2 3 4 5
  5 3 1 2 4
  2 5 4 3 1
  4 1 2 5 3
  3 4 5 1 2
  

• Wkład: 8

  Jedno możliwe wyjście:

  1 2 3 4 5 6 7 8
  2 3 1 5 4 8 6 7
  4 1 2 3 7 5 8 6
  6 4 7 8 1 2 3 5
  7 5 8 2 6 3 4 1
  5 8 4 6 2 7 1 3
  8 7 6 1 3 4 5 2
  3 6 5 7 8 1 2 4
  

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach, z jednym wyjątkiem. W przypadku danych wejściowych N = 2, 3nie ma poprawnych rozwiązań. Jeśli Twój kod może to obsłużyć (uruchomić do końca bez wypisywania czegokolwiek w tych przypadkach lub wypisać pusty ciąg znaków), a mimo to obsługuje N = 1(dane wyjściowe 1dla niego), zmniejsz o 20% liczbę bajtów.

Python 3, 275 260 bajtów * 0,8 = 220 208 bajtów

Podejście rekurencyjne / wycofywanie. Rjest funkcją rekurencyjną, ljest kolumną, wjest linią, Kjest następnym wpisem.

Zdecydowałem się umieścić go w tablicy 1d i ładnie wydrukować na końcu, aby uprościć indeksy.

r=range
n=(int)(input())
def R(A,I):
 l=I%n;w=I//n
 if I==n*n:[print(A[i*n:i*n+n])for i in r(n)];exit()
 for K in r(n):
  if all([all([A[i*n+l]!=K,w!=l or A[i+n*i]!=K,w!=n-1-l or A[n*i+n-i-1]!=K])for i in r(w)]+[A[w*n+i]!=K for i in r(l)]):R(A+[K],I+1)
R([],0)

Wersja bez golfa:

def Recurse(A,I,n):
 column=I%n
 row=I//n
 if I==n*n:
     [print(*A[i*n:i*n+n])for i in range(n)] # output
     exit() #end recursion
 for K in range(n):
    # try every possibility. Test if they satisfy the constraints:
    # if so, move the index on. If none of them do, we'll return None.
    # if a child returns None, we'll move onto the next potential child:
    # if all of them fail it will backtrack to the next level.
    if all([
        all([
            A[i*n+column]!=K, # column constraint
            row!=column or A[i+n*i]!=K, # diagonal constraint
            row!=n-1-column or A[n*i+n-i-1]!=K # antidiagonal constraint
            ]) for i in range(row)
        ]+[
            A[row*n+i]!=K for i in range(column) # row constraint
            ]):
        Recurse(A+[K],I+1,n)

Recurse([],0,(int)(input()))

Funciton , niekonkurencyjny

AKTUALIZACJA! Ogromna poprawa wydajności! n = 7 kończy się teraz w mniej niż 10 minut! Zobacz wyjaśnienie na dole!

To była dobra zabawa pisać. To jest solute brute-force dla tego problemu napisanego w Funciton. Niektóre faktoidy:

• Akceptuje liczbę całkowitą na STDIN. Obce białe spacje psują go, w tym nowa linia po liczbie całkowitej.
• Używa liczb od 0 do n - 1 (nie od 1 do n ).
• Wypełnia siatkę „do tyłu”, więc otrzymujesz rozwiązanie, w którym czytany jest dolny wiersz, 3 2 1 0a nie górny 0 1 2 3.
• Poprawnie wyprowadza 0(jedyne rozwiązanie) dla n = 1.
• Pusty wynik dla n = 2 i n = 3.
• Po skompilowaniu do pliku exe zajmuje około 8¼ minuty dla n = 7 (było około godziny przed poprawą wydajności). Bez kompilacji (przy użyciu interpretera) zajmuje to około 1,5 razy dłużej, więc warto skorzystać z kompilatora.
• Jako osobisty kamień milowy, po raz pierwszy napisałem cały program Funciton bez uprzedniego napisania programu w języku pseudokodu. Najpierw jednak napisałem to w rzeczywistym języku C #.
• (Jednak nie po raz pierwszy dokonałem zmiany, aby znacznie poprawić wydajność czegoś w Funciton. Za pierwszym razem zrobiłem to w funkcji silni. Zamiana kolejności operandów mnożenia zrobiła ogromną różnicę z powodu jak działa algorytm mnożenia . Na wszelki wypadek.)

Bez ceregieli:

            ┌────────────────────────────────────┐           ┌─────────────────┐
            │                                  ┌─┴─╖ ╓───╖ ┌─┴─╖   ┌──────┐    │
            │                    ┌─────────────┤ · ╟─╢ Ӂ ╟─┤ · ╟───┤      │    │
            │                    │             ╘═╤═╝ ╙─┬─╜ ╘═╤═╝ ┌─┴─╖    │    │
            │                    │               └─────┴─────┘   │ ♯ ║    │    │
            │                  ┌─┴─╖                             ╘═╤═╝    │    │
            │     ┌────────────┤ · ╟───────────────────────────────┴───┐  │    │
          ┌─┴─╖ ┌─┴─╖   ┌────╖ ╘═╤═╝ ┌──────────┐         ┌────────┐ ┌─┴─╖│    │
          │ ♭ ║ │ × ╟───┤ >> ╟───┴───┘        ┌─┴─╖       │ ┌────╖ └─┤ · ╟┴┐   │
          ╘═╤═╝ ╘═╤═╝   ╘══╤═╝          ┌─────┤ · ╟───────┴─┤ << ╟─┐ ╘═╤═╝ │   │
    ┌───────┴─────┘ ┌────╖ │            │     ╘═╤═╝         ╘══╤═╝ │   │   │   │
    │     ┌─────────┤ >> ╟─┘            │       └───────┐      │   │   │   │   │
    │     │         ╘══╤═╝            ┌─┴─╖   ╔═══╗   ┌─┴─╖ ┌┐ │   │ ┌─┴─╖ │   │
    │     │           ┌┴┐     ┌───────┤ ♫ ║ ┌─╢ 0 ║ ┌─┤ · ╟─┤├─┤   ├─┤ Ӝ ║ │   │
    │     │   ╔═══╗   └┬┘     │       ╘═╤═╝ │ ╚═╤═╝ │ ╘═╤═╝ └┘ │   │ ╘═╤═╝ │   │
    │     │   ║ 1 ╟───┬┘    ┌─┴─╖       └───┘ ┌─┴─╖ │   │      │   │   │ ┌─┴─╖ │
    │     │   ╚═══╝ ┌─┴─╖   │ ɓ ╟─────────────┤ ? ╟─┘   │    ┌─┴─╖ │   ├─┤ · ╟─┴─┐
    │     ├─────────┤ · ╟─┐ ╘═╤═╝             ╘═╤═╝   ┌─┴────┤ + ╟─┘   │ ╘═╤═╝   │
  ┌─┴─╖ ┌─┴─╖       ╘═╤═╝ │ ╔═╧═╕ ╔═══╗ ┌───╖ ┌─┴─╖ ┌─┴─╖    ╘═══╝     │   │     │
┌─┤ · ╟─┤ · ╟───┐     └┐  └─╢   ├─╢ 0 ╟─┤ ⌑ ╟─┤ ? ╟─┤ · ╟──────────────┘   │     │
│ ╘═╤═╝ ╘═╤═╝   └───┐ ┌┴┐   ╚═╤═╛ ╚═╤═╝ ╘═══╝ ╘═╤═╝ ╘═╤═╝                  │     │
│   │   ┌─┴─╖ ┌───╖ │ └┬┘   ┌─┴─╖ ┌─┘           │     │                    │     │
│ ┌─┴───┤ · ╟─┤ Җ ╟─┘  └────┤ ? ╟─┴─┐   ┌─────────────┘                    │     │
│ │     ╘═╤═╝ ╘═╤═╝         ╘═╤═╝   │   │╔════╗╔════╗                      │     │
│ │       │  ┌──┴─╖ ┌┐   ┌┐ ┌─┴─╖ ┌─┴─╖ │║ 10 ║║ 32 ║    ┌─────────────────┘     │
│ │       │  │ << ╟─┤├─┬─┤├─┤ · ╟─┤ · ╟─┘╚══╤═╝╚╤═══╝ ┌──┴──┐                    │
│ │       │  ╘══╤═╝ └┘ │ └┘ ╘═╤═╝ ╘═╤═╝     │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖                  │
│ │     ┌─┴─╖ ┌─┴─╖  ┌─┴─╖  ┌─┴─╖ ╔═╧═╕     └─┤ ? ╟─┤ · ╟─┤ % ║                  │
│ └─────┤ · ╟─┤ · ╟──┤ Ӂ ╟──┤ ɱ ╟─╢   ├───┐   ╘═╤═╝ ╘═╤═╝ ╘═╤═╝                  │
│       ╘═╤═╝ ╘═╤═╝  ╘═╤═╝  ╘═══╝ ╚═╤═╛ ┌─┴─╖ ┌─┴─╖   │     └────────────────────┘
│         └─────┤      │            └───┤ ‼ ╟─┤ ‼ ║   │        ┌──────┐
│               │      │                ╘═══╝ ╘═╤═╝   │        │ ┌────┴────╖
│               │      │                      ┌─┴─╖   │        │ │ str→int ║
│               │      └──────────────────────┤ · ╟───┴─┐      │ ╘════╤════╝
│               │          ┌─────────╖        ╘═╤═╝     │    ╔═╧═╗ ┌──┴──┐
│               └──────────┤ int→str ╟──────────┘       │    ║   ║ │ ┌───┴───┐
│                          ╘═════════╝                  │    ╚═══╝ │ │ ┌───╖ │
└───────────────────────────────────────────────────────┘          │ └─┤ × ╟─┘
           ┌──────────────┐                                  ╔═══╗ │   ╘═╤═╝
╔════╗     │ ╓───╖ ┌───╖  │                              ┌───╢ 0 ║ │   ┌─┴─╖ ╔═══╗
║ −1 ║     └─╢ Ӝ ╟─┤ × ╟──┴──────┐                       │   ╚═╤═╝ └───┤ Ӂ ╟─╢ 0 ║
╚═╤══╝       ╙───╜ ╘═╤═╝         │                       │   ┌─┴─╖     ╘═╤═╝ ╚═══╝
┌─┴──╖ ┌┐ ┌───╖ ┌┐ ┌─┴──╖ ╔════╗ │                       │ ┌─┤   ╟───────┴───────┐
│ << ╟─┤├─┤ ÷ ╟─┤├─┤ << ║ ║ −1 ║ │                       │ │ └─┬─╜ ┌─┐ ┌─────┐   │
╘═╤══╝ └┘ ╘═╤═╝ └┘ ╘═╤══╝ ╚═╤══╝ │                       │ │   └───┴─┘ │   ┌─┴─╖ │
  │         └─┘      └──────┘    │                       │ └───────────┘ ┌─┤ ? ╟─┘
  └──────────────────────────────┘         ╓───╖         └───────────────┘ ╘═╤═╝
                               ┌───────────╢ Җ ╟────────────┐                │
      ┌────────────────────────┴───┐       ╙───╜            │
      │                          ┌─┴────────────────────┐ ┌─┴─╖
    ┌─┴─╖                      ┌─┴─╖                  ┌─┴─┤ · ╟──────────────────┐
    │ ♯ ║ ┌────────────────────┤ · ╟───────┐          │   ╘═╤═╝                  │
    ╘═╤═╝ │                    ╘═╤═╝       │          │     │              ┌───╖ │
┌─────┴───┘    ┌─────────────────┴─┐   ┌───┴───┐    ┌─┴─╖ ┌─┴─╖          ┌─┤ × ╟─┴─┐
│              │                 ┌─┴─╖ │   ┌───┴────┤ · ╟─┤ · ╟──────────┤ ╘═╤═╝   │
│              │ ┌───╖ ┌───╖  ┌──┤ · ╟─┘ ┌─┴─┐      ╘═╤═╝ ╘═╤═╝        ┌─┴─╖ │     │
│         ┌────┴─┤ ♭ ╟─┤ × ╟──┘  ╘═╤═╝   │ ┌─┴─╖ ┌───╖└┐ ┌──┴─╖      ┌─┤ · ╟─┘     │
│         │      ╘═══╝ ╘═╤═╝ ┌───╖ │     │ │ × ╟─┤ Ӝ ╟─┴─┤ ÷% ╟─┐    │ ╘═╤═╝ ┌───╖ │
│   ┌─────┴───┐     ┌────┴───┤ Ӝ ╟─┴─┐   │ ╘═╤═╝ ╘═╤═╝   ╘══╤═╝ │    │   └───┤ Ӝ ╟─┘
│ ┌─┴─╖ ┌───╖ │     │ ┌────╖ ╘═╤═╝   │   └───┘   ┌─┴─╖      │   │    └────┐  ╘═╤═╝
│ │ × ╟─┤ Ӝ ╟─┘     └─┤ << ╟───┘   ┌─┴─╖ ┌───────┤ · ╟───┐  │ ┌─┴─╖ ┌───╖ │    │
│ ╘═╤═╝ ╘═╤═╝         ╘══╤═╝   ┌───┤ + ║ │       ╘═╤═╝   ├──┴─┤ · ╟─┤ × ╟─┘    │
└───┤     └────┐ ╔═══╗ ┌─┴─╖ ┌─┴─╖ ╘═╤═╝ │ ╔═══╗ ┌─┴─╖ ┌─┴─╖  ╘═╤═╝ ╘═╤═╝      │
  ┌─┴─╖ ┌────╖ │ ║ 0 ╟─┤ ? ╟─┤ = ║  ┌┴┐  │ ║ 0 ╟─┤ ? ╟─┤ = ║    │     │ ┌────╖ │
  │ × ╟─┤ << ╟─┘ ╚═══╝ ╘═╤═╝ ╘═╤═╝  └┬┘  │ ╚═══╝ ╘═╤═╝ ╘═╤═╝    │     └─┤ << ╟─┘
  ╘═╤═╝ ╘═╤══╝ ┌┐     ┌┐ │     │     └───┘       ┌─┴─╖   ├──────┘       ╘═╤══╝
    │     └────┤├──┬──┤├─┘     ├─────────────────┤ · ╟───┘                │
    │          └┘┌─┴─╖└┘       │     ┌┐   ┌┐     ╘═╤═╝ ┌┐   ┌┐            │
    └────────────┤ · ╟─────────┘   ┌─┤├─┬─┤├─┐     └───┤├─┬─┤├────────────┘
                 ╘═╤═╝             │ └┘ │ └┘ │         └┘ │ └┘
                   └───────────────┘    │    └────────────┘

Objaśnienie pierwszej wersji

Pierwsza wersja zajęła około godziny n = 7. Poniżej wyjaśniono głównie, jak działała ta wolna wersja. Na dole wyjaśnię, jakie zmiany wprowadziłem, aby uzyskać mniej niż 10 minut.

Wycieczka na kawałki

Ten program potrzebuje bitów. Potrzebuje wielu bitów i potrzebuje ich we wszystkich właściwych miejscach. Doświadczeni programiści Funciton już wiedzą, że jeśli potrzebujesz n bitów, możesz użyć wzoru

które w Funcitonie można wyrazić jako

Podczas optymalizacji wydajności przyszło mi do głowy, że mogę obliczyć tę samą wartość znacznie szybciej, korzystając z tego wzoru:

Mam nadzieję, że wybaczysz mi, że nie zaktualizowałem odpowiednio całej grafiki równania w tym poście.

Powiedzmy, że nie chcesz ciągłego bloku bitów; tak naprawdę chcesz n bitów w regularnych odstępach co k -ty bit, tak jak poniżej:

                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

Wzór na to jest dość prosty, gdy się zorientujesz:

W kodzie funkcja Ӝprzyjmuje wartości n i k i oblicza tę formułę.

Śledzenie używanych numerów

Na końcowej siatce jest n ² liczb, a każda liczba może być dowolną z n możliwych wartości. Aby śledzić, które liczby są dozwolone w każdej komórce, zachowujemy liczbę składającą się z n ³ bitów, w których ustawiony jest bit wskazujący, że określona wartość jest pobierana. Początkowo liczba ta wynosi oczywiście 0.

Algorytm rozpoczyna się w prawym dolnym rogu. Po „odgadnięciu” pierwszą liczbą jest 0, musimy śledzić fakt, że 0 nie jest już dozwolone w żadnej komórce wzdłuż tego samego wiersza, kolumny i przekątnej:

LSB                               (example n=5)
 ↓
 10000 00000 00000 00000 10000
 00000 10000 00000 00000 10000
 00000 00000 10000 00000 10000
 00000 00000 00000 10000 10000
 10000 10000 10000 10000 10000
                             ↑
                            MSB

W tym celu obliczamy następujące cztery wartości:

• Bieżący wiersz: Potrzebujemy n bitów co n- ty bit (jeden na komórkę), a następnie przesuwamy go do bieżącego wiersza r , pamiętając, że każdy wiersz zawiera n ² bitów:

  

• Bieżąca kolumna: Potrzebujemy n bitów co n ²-ty bit (jeden na wiersz), a następnie przesuwamy ją do bieżącej kolumny c , pamiętając, że każda kolumna zawiera n bitów:

  

• Przekątna do przodu: Potrzebujemy n bitów co ... (czy zwracałeś uwagę? Szybko, wymyśl to!) ... n ( n +1) -ty bit (dobra robota!), Ale tylko jeśli faktycznie jesteśmy na przekątna do przodu:

  

• Przekątna do tyłu: tutaj dwie rzeczy. Po pierwsze, skąd wiemy, czy jesteśmy na przekątnej do tyłu? Matematycznie warunkiem jest c = ( n - 1) - r , co jest takie samo jak c = n + (- r - 1). Hej, czy to ci coś przypomina? Zgadza się, to uzupełnienie dwóch, więc zamiast dekrementacji możemy użyć bitowej negacji (bardzo wydajnej w Funcitonie). Po drugie, powyższy wzór zakłada, że ​​chcemy ustawić najmniej znaczący bit, ale tak nie jest w przypadku przekątnej wstecznej, więc musimy go przesunąć w górę o ... wiesz? ... Zgadza się, n ( n - 1).

  

  Jest to również jedyny przypadek, w którym potencjalnie dzielimy przez 0, jeśli n = 1. Jednak Funciton to nie obchodzi. 0 ÷ 0 to tylko 0, nie wiesz?

W kodzie funkcja Җ(dolna) przyjmuje n, a indeks (na podstawie którego oblicza r i c przez dzielenie i resztę), oblicza te cztery wartości i ors je razem.

Algorytm brutalnej siły

Algorytm siły brutalnej jest implementowany przez Ӂ(funkcja u góry). Zajmuje n (rozmiar siatki), indeks (gdzie na siatce obecnie umieszczamy liczbę) i pobierane (liczba z n ³ bitami mówi nam, które liczby możemy nadal umieścić w każdej komórce).

Ta funkcja zwraca sekwencję ciągów. Każdy ciąg jest pełnym rozwiązaniem dla siatki. To kompletny solver; zwróci wszystkie rozwiązania, jeśli na to pozwolisz, ale zwróci je jako sekwencję leniwą.

• Jeśli indeks osiągnął wartość 0, pomyślnie wypełniliśmy całą siatkę, więc zwracamy sekwencję zawierającą pusty ciąg (pojedyncze rozwiązanie, które nie obejmuje żadnej komórki). Jest pusty ciąg 0i używamy funkcji biblioteki, ⌑aby przekształcić go w sekwencję jednoelementową.

• Sprawdzanie opisane w poniższej poprawie wydajności ma miejsce tutaj.

• Jeśli indeks nie osiągnął jeszcze 0, zmniejszamy go o 1, aby uzyskać indeks, pod którym teraz musimy umieścić liczbę (nazwij to IX ).

  Używamy ♫do generowania leniwej sekwencji zawierającej wartości od 0 do n - 1.

  Następnie używamy ɓ(monadic bind) z lambda, która wykonuje następujące czynności w kolejności:

  • Najpierw spójrz na odpowiedni bit , aby podjąć decyzję, czy numer jest ważny tutaj, czy nie. Możemy umieścić liczbę i wtedy i tylko wtedy , gdy pobrana & (1 << ( n × ix ) << i ) nie jest jeszcze ustawiona. Jeśli jest ustawiony, wróć 0(pusta sekwencja).
  • Służy Җdo obliczania bitów odpowiadających bieżącemu rzędowi, kolumnie i przekątnej. Przesuń go o i, a następnie orna zabrane .
  • Wywołaj rekurencyjnie, Ӂaby pobrać wszystkie rozwiązania dla pozostałych komórek, przekazując mu nowe zajęte i zmniejszone ix . Zwraca sekwencję niekompletnych ciągów; każdy ciąg ma znaki ix (siatka wypełniona do indeksu ix ).
  • Użyj ɱ(map), aby przejrzeć znalezione w ten sposób rozwiązania, i użyj, ‼aby połączyć i do końca każdego z nich. Dodaj nowy wiersz, jeśli indeks jest wielokrotnością n , w przeciwnym razie spacją.

Generowanie wyniku

Główne wywołania programu Ӂ(brutalny forcer) z n , indeks = n ² (pamiętaj, że wypełniamy siatkę do tyłu) i przyjmowane = 0 (początkowo nic nie jest pobierane). Jeśli wynikiem tego jest pusta sekwencja (nie znaleziono rozwiązania), wypisz pusty ciąg. W przeciwnym razie wypisz pierwszy ciąg w sekwencji. Zauważ, że oznacza to, że będzie oceniał tylko pierwszy element sekwencji, dlatego solver nie kontynuuje działania, dopóki nie znajdzie wszystkich rozwiązań.

Poprawa wydajności

(Dla tych, którzy już przeczytali starą wersję objaśnienia: program nie generuje już sekwencji sekwencji, którą należy osobno przekształcić w ciąg wyjściowy; po prostu generuje sekwencję ciągów bezpośrednio. Odpowiednio zredagowałem wyjaśnienie Ale to nie była główna poprawa. Oto nadchodzi.)

Na moim komputerze skompilowane exe pierwszej wersji zajęło prawie dokładnie 1 godzinę na rozwiązanie n = 7. Nie było to w podanym limicie czasu 10 minut, więc nie odpoczywałem. (Właściwie powodem, dla którego nie odpoczywałem, było to, że wpadłem na pomysł, jak to znacznie przyspieszyć.)

Algorytm opisany powyżej zatrzymuje swoje wyszukiwanie i cofa się za każdym razem, że napotyka na komórkę, w którym wszystkie bity w podjętej liczby są ustawione, wskazując, że nic nie można umieścić w tej komórce.

Jednak algorytm będzie nadal bezskutecznie wypełniał siatkę do komórki, w której ustawiono wszystkie te bity. Byłoby znacznie szybciej, gdyby mógł zatrzymać się, gdy jakakolwiek komórka, która ma być wypełniona, ma już ustawione wszystkie bity, co już wskazuje, że nigdy nie możemy rozwiązać reszty siatki bez względu na to, jakie liczby wstawimy to. Ale jak sprawnie sprawdzić, czy jakakolwiek komórka ma ustawione n bitów bez przechodzenia przez wszystkie?

Sztuczka zaczyna się od dodania jednego bitu na komórkę do pobranej liczby. Zamiast tego, co pokazano powyżej, wygląda to tak:

LSB                               (example n=5)
 ↓
 10000 0 00000 0 00000 0 00000 0 10000 0
 00000 0 10000 0 00000 0 00000 0 10000 0
 00000 0 00000 0 10000 0 00000 0 10000 0
 00000 0 00000 0 00000 0 10000 0 10000 0
 10000 0 10000 0 10000 0 10000 0 10000 0
                                       ↑
                                      MSB

Zamiast n ³, w tej liczbie jest teraz n ² ( n + 1) bitów. Funkcja wypełniająca bieżący wiersz / kolumnę / przekątną została odpowiednio zmieniona (w rzeczywistości całkowicie przepisana, jeśli mam być szczera). Ta funkcja będzie jednak nadal wypełniać tylko n bitów na komórkę, więc dodatkowy bit, który właśnie dodaliśmy, zawsze będzie 0.

Powiedzmy, że jesteśmy w połowie obliczeń, właśnie umieściliśmy 1w środkowej komórce, a pobrana liczba wygląda mniej więcej tak:

                 current
LSB              column           (example n=5)
 ↓                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0
 00011 0 11110 0 01101 0 11101 0 11100 0
 11111 0 11110 0[11101 0]11100 0 11100 0    ← current row
 11111 0 11111 0 11111 0 11111 0 11111 0
 11111 0 11111 0 11111 0 11111 0 11111 0
                                       ↑
                                      MSB

Jak widać, lewa górna komórka (indeks 0) i środkowa lewa komórka (indeks 10) są teraz niemożliwe. Jak najskuteczniej to ustalić?

Rozważ liczbę, w której ustawiony jest zerowy bit każdej komórki, ale tylko do bieżącego indeksu. Taka liczba jest łatwa do obliczenia za pomocą znanej formuły:

Co uzyskalibyśmy, gdyby dodać te dwie liczby razem?

LSB                                               LSB
 ↓                                                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0           10000 0 10000 0 10000 0 10000 0 10000 0        ╓───╖
 00011 0 11110 0 01101 0 11101 0 11100 0     ║     10000 0 10000 0 10000 0 10000 0 10000 0            ║
 11111 0 11110 0 11101 0 11100 0 11100 0  ═══╬═══  10000 0 10000 0 00000 0 00000 0 00000 0  ═════   ╓─╜
 11111 0 11111 0 11111 0 11111 0 11111 0     ║     00000 0 00000 0 00000 0 00000 0 00000 0  ═════   ╨
 11111 0 11111 0 11111 0 11111 0 11111 0           00000 0 00000 0 00000 0 00000 0 00000 0          o
                                       ↑                                                 ↑
                                      MSB                                               MSB

Wynik to:

             OMG
              ↓
        00000[1]01010 0 11101 0 00010 0 00011 0
        10011 0 00001 0 11101 0 00011 0 00010 0
═════   00000[1]00001 0 00011 0 11100 0 11100 0
═════   11111 0 11111 0 11111 0 11111 0 11111 0
        11111 0 11111 0 11111 0 11111 0 11111 0

Jak widać, dodatek przepełnia dodatkowy bit, który dodaliśmy, ale tylko wtedy, gdy wszystkie bity dla tej komórki są ustawione! Dlatego wszystko, co pozostało do zrobienia, to maskowanie tych bitów (ta sama formuła jak powyżej, ale << n ) i sprawdzenie, czy wynikiem jest 0:

00000[1]01010 0 11101 0 00010 0 00011 0    ╓╖    00000 1 00000 1 00000 1 00000 1 00000 1         ╓─╖ ╓───╖
10011 0 00001 0 11101 0 00011 0 00010 0   ╓╜╙╖   00000 1 00000 1 00000 1 00000 1 00000 1        ╓╜ ╙╖    ║
00000[1]00001 0 00011 0 11100 0 11100 0   ╙╥╥╜   00000 1 00000 1 00000 0 00000 0 00000 0  ═════ ║   ║  ╓─╜
11111 0 11111 0 11111 0 11111 0 11111 0   ╓╜╙╥╜  00000 0 00000 0 00000 0 00000 0 00000 0  ═════ ╙╖ ╓╜  ╨
11111 0 11111 0 11111 0 11111 0 11111 0   ╙──╨─  00000 0 00000 0 00000 0 00000 0 00000 0         ╙─╜   o

Jeśli nie jest zero, siatka jest niemożliwa i możemy się zatrzymać.

• Zrzut ekranu przedstawiający rozwiązanie i czas działania dla n = 4 do 7.

Haskell, 790 * 0,80 = 632 bajty

import Data.List
import Control.Monad
import Data.Array
s r=let{h as bs=[(a,b)|a<-as,b<-bs];(&)m k=(\(Just x)->x)$lookup k m;j=Just;n=Nothing;c=[1..r];q=delete;u=h[1..r]c;o=[(s,[u |u<-[h[1..r][c]|c<-c]++[h[r]c|r<-[1..r]]++[zip[1..r][1..r],zip[1..r][r,r-1..1]],s`elem`u])|s<-u];k=foldr(>=>)j;a p d g0=k[t p d2|d2<-q d(g0!p)]g0;t p d g0|not(d`elem`(g0!p))=j g0|[]<-v=n|[d2]<-v=k[t s2 d2|s2<-[(s,delete s$nub(concat(o&s)))|s<-u]&p]g1|True=k[l[s|s<-u,not(d`elem`v)]|u<-o&p]g1 where{v=q d(g0!p);g1=g0//[(p,v)];l[]_=n;l[d3]g=a d3 d g;l _ r=j r};w g0|and[case g0!s of{[_]->True;_->False}|s<-u]=j g0|True=msum[a s' d g0>>=w|d<-g0!s']where(_,s')=minimumBy(\(a,_)(b,_)->compare a b)[(l,s)|s<-u,let v=g0!s;l=length v,l>1]}in fmap(fmap(\[x]->x))$w$array((1,1),(r,r))[((i,j),[1..r])|i<-[1..r],j<-[1..r]]

Zauważyłem, że ten problem jest bardzo podobny do sudoku. Pamiętam stary solver sudoku, który napisałem w Haskell na podstawie tego drugiego w Pythonie. To jest mój pierwszy post lub próba gry w golfa.

Spełnia to bonus, ponieważ wraca Nothingdo n=2,3i Just <result>po n>=4, gdzie <result>jest tablica 2D wartości całkowitych.

Zobacz tutaj dla tłumacza online. Ten kod jest w rzeczywistości dłuższy niż kod pocztowy, ponieważ tłumacz online ma bardziej rygorystyczne wymagania co do tego, co tworzy kompletny program (zasady mówią, że przesłanie może być funkcją). To przesłanie przyjmuje dane wejściowe jako argument funkcji.

Pyth, 41 bajtów

#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K

#                                      ;   # while(True)
 Km.SQQ                                    # K = random QxQ 2d list
       I                               ;   # if ...
        .A                                 # all of...
          m                          Q     # map(range(Q))...
                +                          # concat
                 .TK                       # transpose K
                    .Tm,@@Kdd@@Kt-Qdd      # diagonals of K
                      m             d      # map(range(d))
                       ,                   # 2-elem list of...
                        @@Kdd              # K[n][n]
                             @@Kt-Qd       # and K[len(K)-n-1][n]
                    .T                     # transpose
           qQl{d                           # subarrays have no dups...
                                      B;   # ... then, break
                                        K  # output final result

Brute force ftw!

Ponieważ to w zasadzie próbuje losowych przetasowań, dopóki nie zadziała (cóż, ciągle próbuje n * [shuffle(range(n))]), zajmuje to naprawdę bardzo długo. Oto kilka testów, które pokazują, jak długo to trwa:

llama@llama:~$ time echo 4 | pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')               
[[2, 1, 0, 3], [0, 3, 2, 1], [3, 0, 1, 2], [1, 2, 3, 0]]
echo 4  0.00s user 0.00s system 0% cpu 0.001 total
pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')  0.38s user 0.00s system 96% cpu 0.397 total

To tylko 4x4 i działa w niecałe pół sekundy. Właściwie oszukuję, ponieważ jest to najlepszy z kilku prób - większość z nich zajmuje sekundę lub dwie.

Muszę jeszcze ustalić czas na 5x5 (raz skończył się, ale to było w REPL i nie mierzyłem go).

Pamiętaj, że reguła dotycząca limitu czasu została zredagowana w pytaniu dopiero po opublikowaniu tej odpowiedzi.

SWI-Prolog, 326 * 0,80 = 260,8 bajtów

:-use_module(library(clpfd)).
a(N):-l(N,R),m(l(N),R),append(R,V),V ins 1..N,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),m(m(all_distinct),[R,C,[D,E]]),m(label,R),m(p,R).
l(L,M):-length(M,L).
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
p([H|T]):-write(H),T=[],nl;write(' '),p(T).
m(A,B):-maplist(A,B).

Edycja: zapisano 16 bajtów dzięki @Mat

Stosowanie

Zadzwoń a(5).po tłumacza N=5. Zwraca wartość falsedla N=2lub N=3.

Ponieważ wykorzystuje bibliotekę CLPFD, nie jest to czysta brutalność. Ten program może znaleźć rozwiązanie na N=20około 15 sekund na moim komputerze.

Niegolfowane + objaśnienia:

Zasadniczo działa to jak solver Sudoku, z tym wyjątkiem, że ograniczenia bloków są zastępowane ograniczeniami przekątnymi.

:-use_module(library(clpfd)).      % Import Constraints library

a(N):-
    l(N,R),                        % R is a list of length N
    maplist(l(N),R),               % R contains sublists, each of length N
    append(R,V),                   
    V ins 1..N,                    % Each value in the matrix is between 1 and N
    maplist(all_distinct,R),       % Values must be different on each row
    transpose(R,C),
    maplist(all_distinct,C),       % Values must be different on each column
    d(0,R,D),
    maplist(reverse,R,S),          
    d(0,S,E),
    all_distinct(D),               % Values must be different on the diagonal
    all_distinct(E),               % Values must be different on the "anti"-diagonal
    maplist(label,R),              % Affects actual values to each element
    maplist(p,R).                  % Prints each row

l(L,M):-length(M,L).               % True if L is the length of M

d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)). % True if the third argument is the diagonal of the second argument

p([H|T]):-write(H),T=[],nl;write(' '),p(T).  % Prints a row separated by spaces and followed by a new line

CJam, 87 bajtów - bonus 20% = 69,6 bajtów

qi__"@I/l
ŤˏūȻ
܀ᅀ൹৽჈͚
㑢鴑慚菥洠㬝᚜
"N/=:i0+\,m!f=`1LL](4e<=

Twarde kody odpowiedzi. Zawiera niektóre niedrukowalne. Działa N = 1przez N = 8.

Zasadniczo każda linia tego tajemniczego ciągu zawiera indeksy na liście permutacji range(N), zakodowane jako znaki Unicode.

=:i0+\,m!f=indeksuje do listy permutacji, dodając najpierw 0 na końcu listy indeksów, reprezentujących dolny wiersz 0 1 2 ... N-1. Ponieważ N < 4wynikowa tablica 2D jest nonsensowna.

`1LL]tworzy listę [N, pretty output, 1, "", ""]. Następnie (4e<=wyskakuje pierwszy element z tej listy Ni pobiera min(N, 4) % 4element th z reszty. Bo N >= 4to jest wynik, w przeciwnym razie jest to wynik specjalnych przypadków dla pierwszych trzech przypadków.

Wypróbuj tutaj .

C ++, 672 * 0,80 645 * 0,80 = 516 bajtów

#include <iostream>
int **b,**x,**y,*d,*a,n;
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];
int f(int c,int r) {int i=0,p=c-1;if(r>=n)return 1;if(c == n + 1)return f(1,r+1);R(i)int m=r==i,s=r+i==n-1;if(!b[r][i]&&!x[r][p]&&!(m&&d[p])&&!(s&&a[p])&&!y[i][p]){b[r][i]=c;x[r][p]=1;y[i][p]=1;if(m)d[p]=1;if(s)a[p]=1;if(f(c+1,r))return 1;b[r][i]=0;x[r][p]=0;y[i][p]=0;if(m)d[p]=0;if(s)a[p]=0;}}return 0;}
int main(){std::cin>>n;int i=0,j=0;b=new int*[n];x=new int*[n];y=new int*[n];E(d);E(a);R(i)E(b[i]);E(x[i]);E(y[i]); d[i]=0;a[i]=0;R(j)b[i][j]=0;x[i][j]=0;y[i][j]=0;}}if(f(1,0)){R(i)R(j)std::cout<<b[i][j];}std::cout<<std::endl;}}}

Wypróbuj online tutaj

Ponieważ już opublikowano kilka odpowiedzi, pomyślałem, że opublikuję wersję kodu w golfa, której użyłem do wygenerowania danych wyjściowych dla przykładów. Po raz pierwszy odpowiadam na golfa kodowego , więc wszelkie opinie są mile widziane. :)

Niegolfowane + objaśnienia:

Zasadniczo kod wymusza brutalne rozwiązanie. Zaczyna się w pierwszym rzędzie od 0. Zaczyna się w pierwszym miejscu, jeśli to miejsce przejdzie wszystkie kontrole, przechodzi do następnej liczby. Jeśli wypełnia wiersz, przechodzi do następnego rzędu. Jeśli zrobione są wszystkie wiersze, oznacza to, że znaleziono rozwiązanie. Jeśli miejsce nie przejdzie wszystkich testów, przechodzi do następnego miejsca. Jeśli zrobi to wiersz, to cofa się, ponieważ liczba w jednym z poprzednich wierszy uniemożliwia rozwiązanie.

#include <iostream>

// global variables to save bytes on passing these are function arguments
int **b, // this will store the state of the board
    **x, // if x[i][j] is true, row i of b contains the number j
    **y, // if y[i][j] is true, column i of b contains the number j
    *d,  // if d[i] the main diagonal of b contains i
    *a,  // if a[i] the antidiagonal of a contains i
    n;

// preprocessor to save bytes on repeated statements
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];

// Recursively looks for a solution 
// c - the current number to insert in row r
// r - the current row to fill
int f (int c, int r) {
        int i=0,p=c-1;
        if (r >= n) return 1;             // we are done
        if (c == n + 1) return f(1,r+1);  // this row is full, move to the next row
        R(i)                              // go through the positions in this row,
                                                                            // trying to fill them with c
                int m=r==i, s=r+i==n-1;   // check if this position (r,i) is on ones
                                                                            // of the diagonals
                // if this spot isn't filled, and the row (r), column (i) and diagonals
                // (if it's on the diagonal) doesn't contain the number, fill the spot
                if (!b[r][i] && !x[r][p] && !(m&&d[p]) && !(s&&a[p]) && !y[i][p]) {
                        // fill the spot, and indicate that this row, column and diagonals 
                        // contain this number, c
                        b[r][i]=c; x[r][p]=1; y[i][p]=1;
                        if (m) d[p]=1; if (s)a[p]=1;

                        // move onto to the next number, if you find a solution, stop
                        if (f(c+1,r)) return 1;

                        // with this number in this spot, a solution is impossible, clear
                        // its, and clear the checks
                        b[r][i]=0; x[r][p]=0; y[i][p]=0;
                        if (m) d[p]=0; if (s) a[p]=0;
                }
        }

        return 0; // a solution wasn't found
}

int main() {
        std::cin >> n; // get n from STDIN

        // initialization 
        int i=0,j=0;
        b=new int*[n]; x=new int*[n]; y=new int*[n];
        E(d); E(a);
        R(i)
                E(b[i]); E(x[i]); E(y[i]); // initialization the inner arrays of b, x, y
                d[i]=0; a[i]=0;

                R(j)
                        b[i][j]=0; x[i][j]=0; y[i][j]=0; // ensure each point is initialized as 0
                }
        }

        // find a solution starting at the top-left corner and print it if it finds one
        if (f(1,0)) {
                R(i)
                        R(j)
                                std::cout<<b[i][j];
                        }
                        std::cout<<std::endl;
                }
        }
}

Clojure, (215 + 258) * 0,8 = 378,4 (174 + 255) * 0,8 = 343,2

Podzielony na dwie części: liczenie błędów Si anonimową funkcję, która dokonuje faktycznej optymalizacji poprzez wyszukiwanie Tabu .

Aktualizacja: krótsza S(liczy odrębne wartości w grupach), mniej optymalny stan początkowy (bez losowania).

(defn S[I n](count(mapcat set(vals(apply merge-with concat(flatten(for[R[(range n)]i R j R v[[(I(+(* n i)j))]]][{[1 i]v}{[2 j]v}(if(= i j){3 v})(if(=(- n 1 i)j){4 v})])))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(for[R[(range %)]i R j R]i))P #{}](let[[s I](last(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(=(*(+(* % 2)2)%)s)(partition % I)(recur I(conj P I))))))

Jednordzeniowe testy porównawcze (w milisekundach) dla 4, 5, 6 i 7 uruchomionych 3 razy:

[[  131.855337   132.96267    138.745981]
 [ 1069.187325  1071.189488  1077.339372]
 [ 9114.736987  9206.65368   9322.656693]
 [36546.309408 36836.567267 36928.346312]]

Oryginalny:

(defn S[I n](apply +(flatten(for[p(concat(partition n I)(for[p(apply map vector(partition n(range(count I))))](map I p))[(take-nth(inc n)I)][(rest(butlast(take-nth(dec n)I)))])](remove #{1}(vals(frequencies p)))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(flatten(map shuffle(repeat %(range %)))))P #{}](let[[s I](first(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(= s 0)(partition % I)(recur I(conj P I))))))

Chciałbym, aby Sbył krótszy, ale ponieważ liczy tylko wystąpienia więcej niż jednej partycji /, kryterium zatrzymania jest proste (= s 0).

Wiele cykli procesora jest marnowanych na nieprzydatne swapy, na przykład nie poprawia wyniku, jeśli zamieniasz 2się nimi 2, i nie musisz zamieniać liczb między wierszami, ponieważ wszystkie mają na początku różne wartości.

Testy porównawcze z Intel 6700K (w milisekundach):

(defn S[I n]( ... )
(def F #( ... ))

(defmacro mytime[expr]
  `(let [start# (. System (nanoTime)) ret# ~expr]
     (/ (double (- (. System (nanoTime)) start#)) 1000000.0)))

(pprint(vec(for[n[4 5 6 7]](vec(sort(repeatedly 5 #(mytime (F n)))))))

[[  43.445902   45.895107   47.277399   57.681634    62.594037]
 [ 222.964582  225.467034  240.532683  330.237721   593.686911]
 [2285.417473 2531.331068 3002.597908 6361.591714  8331.809410]
 [3569.62372  4779.062486 5725.905756 7444.941763 14120.796615]]

Wielowątkowy z pmap:

[[   8.881905  16.343714   18.87262  18.9717890   22.194430]
 [  90.963870 109.719332  163.00299  245.824443  385.365561]
 [ 355.872233 356.439256 1534.31059 2593.482767 3664.221550]
 [1307.727115 1554.00260 2068.35932 3626.878526 4029.543011]]