(Pomimo ponad 60 pytań oznaczonych jako szachy , nie mamy prostego wyzwania dla n-królowych.)

W szachach układanka N-Queens jest opisana w następujący sposób: Biorąc pod uwagę n x nszachownicę i nkrólowe, ułóż królowe na szachownicy, aby żadne dwie królowe nie zagrażały sobie nawzajem. Poniżej znajduje się przykładowe rozwiązanie n = 8pożyczone z Wikipedii.

Lub w renderowaniu ASCII:

xxxQxxxx
xxxxxxQx
xxQxxxxx
xxxxxxxQ
xQxxxxxx
xxxxQxxx
Qxxxxxxx
xxxxxQxx

Wyzwaniem będzie przyjęcie ni wyprowadzenie reprezentacji ASCII rozwiązania nukładanki -Queens. Ponieważ istnieje więcej niż jedno możliwe rozwiązanie (np. Przynajmniej obrót lub odbicie), twój kod musi tylko wygenerować dowolne prawidłowe rozwiązanie.

Wejście

Pojedyncza dodatnia nze n >= 4 w dowolnym, wygodnym formacie . (n = 2 i n = 3 nie mają rozwiązań, a n = 1 jest banalne, więc są wykluczone)

Wynik

Wynikowa reprezentacja ASCII rozwiązania układanki N-królowych, jak opisano powyżej. Możesz wybrać dowolne dwie różne wartości ASCII, które będą reprezentować puste spacje i królowe. Ponownie, można go wyprowadzić w dowolnym odpowiednim formacie (pojedynczy ciąg, lista ciągów, tablica znaków itp.).

Zasady

• Wiodące lub końcowe znaki nowej linii lub białe znaki są opcjonalne, a także białe znaki między znakami, o ile same znaki są poprawnie ustawione w linii.
• Możesz albo użyć algorytmu do obliczenia możliwych pozycji, albo użyć jawnego rozwiązania typu „krok po schodach”, w zależności od tego, który kod jest bardziej golfowy.
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
• Jeśli to możliwe, dołącz link do internetowego środowiska testowego, aby inni mogli wypróbować Twój kod!
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Przykłady

n=4
xQxx
xxxQ
Qxxx
xxQx

n=7
xxQxxxx
xxxxxxQ
xQxxxxx
xxxQxxx
xxxxxQx
Qxxxxxx
xxxxQxx

n=10
xxxxQxxxxx
xxxxxxxxxQ
xxxQxxxxxx
xxxxxxxxQx
xxQxxxxxxx
xxxxxxxQxx
xQxxxxxxxx
xxxxxxQxxx
Qxxxxxxxxx
xxxxxQxxxx

MATL , 33 32 27 bajtów

`x,GZ@]1Z?tt!P!,w&TXds]h1>a

Wypróbuj online!

Półstabilna siła, podejście nie deterministyczne:

1. Wygeneruj losową permutację pozycji wierszy
2. Wygeneruj losową permutację pozycji kolumn
3. Sprawdź, czy żadna królowa nie ma przekątnej ani anty-przekątnej
4. Powtórzyć w razie potrzeby.

Uzyskane rozwiązanie jest losowe. Jeśli uruchomisz kod ponownie, możesz uzyskać inną prawidłową konfigurację. Czas działania jest również losowy, ale najdłuższy przypadek testowy ( n = 10) kończy się w TIO przez około 30 sekund.

C, 114 bajtów

Q(n,o,y){o=n%2;n-=o;for(y=0;y<n+o;++y)printf("%*c\n",y<n?o+n-(n+y%(n/2)*2+(n%6?y<n/2?n/2-1:2-n/2:y<n/2))%n:0,81);}

Bezpośrednio drukuje rozwiązanie w czasie O (1).

Mathematica, 103 108 110 117 bajty

-5 bajtów dla DuplicateFreeQ->E!=##&@@@

-7 bajtów dla ReplacePart[Array[],]->SparseArray[]

SparseArray[Thread@#&@@Select[Permutations@Range@#~Tuples~2,And@@(E!=##&@@@{#-#2,+##})&@@#&]->1,{#,#}]&

Zwróć tablicę 2D. Obliczenie zajmuje 2,76s, f[6]a dla 135s f[7]. (W aktualnej wersji, -staje 0i Qdo 1.

Algorytm jest podobny do odpowiedzi MATL, ale tutaj kod jest całkowicie brutalny.

C - 222 bajty

v,i,j,k,l,s,a[99];main(){for(scanf("%d",&s);*a-s;v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!printf(2+"\n\n%c"-(!l<<!j)," #Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]);}

Kod nie jest mój, ale pochodzi z IOCCC . Mam nadzieję, że nie łamię żadnych zasad. Wyświetla również wszystkie rozwiązania dla N od 4 do 99. Później spróbuję uzyskać link TIO.

Galaretka , 24 21 bajtów

,JŒc€IF€An/PC
ẊÇ¿=þRG

Wypróbuj online!

Zakładając, że każda królowa jest umieszczona w osobnych rzędach, musimy tylko znaleźć indeksy kolumn, aby umieścić każdą królową, aby uniknąć konfliktów, które można znaleźć, generując losową permutację [1, 2, ..., n] i testując ją.

Wyjaśnienie

,JŒc€IF€An/PC  Helper. Input: permutation of [1, 2, ..., n]
 J             Enumerate indices, obtains [1, 2, ..., n]
,              Join
  Œc€          Find all pairs in each
     I         Calculate the difference of each pair
      F€       Flatten each
        A      Absolute value
               (We now have the distance in column between each queen and
                the distance in rows between each queen. If they are unequal,
                the queens do not conflict with each other)
         n/    Reduce using not-equals
           P   Product, returns 1 only if they are all unequal
            C  Complement
               Returns 1 when there is a conflict, else 0

ẊÇ¿=þRG  Main.  Input: n
Ẋ        Shuffle (When given an integer, it will shuffle [1, 2, ..., n])
 Ç¿      While the helper returns 1, continue shuffling
     R   Range, gets [1, 2, ..., n]
   =þ    Equality table (Generates the board as a matrix)
      G  Pretty-print the matrix

Python 3, 204 189 bajtów

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
 if len(set((x*z+c[x],z)for x in r for z in[1,-1]))==n+n:[print(*(b[x:]+b[:x]))for x in c];break

Brutalna siła przeszukuje wszystkie permutacje. Mógłbym usunąć * i wydrukować listę, ale wyglądają okropnie.

Wynik:

10
Q . . . . . . . . .
. . Q . . . . . . .
. . . . . Q . . . .
. . . . . . . Q . .
. . . . . . . . . Q
. . . . Q . . . . .
. . . . . . . . Q .
. Q . . . . . . . .
. . . Q . . . . . .
. . . . . . Q . . .

Nieznacznie nie golfista:

import itertools as p
n=int(input())
r=range(n)
b='.'*(n-1)+'Q'
for c in p.permutations(r):
    if len(set( (x*z+c[x],z) for x in r for z in[1,-1] )) == n+n:
        [print(*(b[x:] + b[:x])) for x in c]
        break

Befunge, 122 bajty

&::2%-v>2*00g++00g%00g\-\00g\`*4>8#4*#<,#-:#1_$55+"Q",,:#v_@
/2p00:<^%g01\+*+1*!!%6g00-2g01\**!!%6g00-g012!:`\g01:::-1<p01

Wypróbuj online!

Jest to mniej więcej oparte na rozwiązaniu C firmy orlp .

Wyjaśnienie

Odczytaj liczbę królowych, q , od stdin i oblicz dwie zmienne do późniejszego użycia: n = q - q%2i hn = n/2
Uruchom główną pętlę, iterując r , liczbę wierszy, od q do 0, zmniejszając na początku pętli, więc pierwsze r to q minus 1.
Obliczyć przesunięcie królowej w każdym rzędzie za pomocą następującego wzoru:

offset = (n - (
  (hn <= r) * (2 - hn) * !!(n % 6) + 
  (hn > r) * ((hn - 2) * !!(n % 6) + 1) + 
  (y % hn * 2) + n
) % n) * (n > r)

Wyjściowe znaki spacji przesunięcia, aby wciąć pozycję królowej dla bieżącego wiersza, oraz dodatkowe miejsce tylko dlatego, że ułatwia to pętlę wyjściową.
Wyjście Qdla królowej, a następnie nowa linia, aby przejść do następnego rzędu.
Sprawdź, czy r wynosi zero, w którym to przypadku dotarliśmy do końca planszy i możemy wyjść, w przeciwnym razie powtórzymy ponownie główną pętlę.

Haskell , 145 bajtów

Oczywiste podejście brutalnej siły:

b=1>0
t[]=b
t(q:r)=all(/=q)r&&foldr(\(a,b)->(abs(q-b)/=a&&))b(zip[1..]r)&&t r
q n|y<-[1..n]=(\q->(' '<$[1..q])++"Q")<$>[x|x<-mapM(\_->y)y,t x]!!0

Wypróbuj online!

Siatkówka , 136 bajtów

.+
$* 
 
$_;$`Q¶
( +)\1( ?);
:$1;
:( +);\1\1
$1$1
:((   )+);( *)
 $1$1% $3$3
: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3
( +)%\1?

Wypróbuj online! Doskonała odpowiedź C dla portu @ orlp. Wyjaśnienie:

.+
$* 

Konwertuj na unary, używając spacji (po spacji jest spacja *).

$_;$`Q¶

Utwórz Nwiersze ze Nspacjami, a ;następnie 0..N-1spacjami, a następnie a Q. Pozostałe etapy dotyczą wszystkich rzędów.

( +)\1( ?);
:$1;

Liczba całkowita dzielona Nprzez 2. (Również zawiń wynik, :;aby ułatwić zakotwiczenie wzorów).

:( +);\1\1
$1$1

Jeśli indeks pętli jest równy N/2*2, po prostu zostaw tyle spacji.

:((   )+);( *)
 $1$1% $3$3

Jeśli N/2jest wielokrotnością 3, weź podwój indeks pętli plus jeden, modulo N/2*2+1.

: ( +);( \1)?( *)
 $1 $1%$#2$* $#2$* $#2$* $1$3$3

W przeciwnym razie weź podwój indeks pętli plus (N/2-1)plus dodatkowe 3 w dolnej połowie planszy, modulo N/2*2.

( +)%\1?

Właściwie wykonaj operację modulo.

Węgiel drzewny , 44 bajty

Ｎθ≔÷θ²ηＥθ◧Q⊕⎇⁼ι⊗ηι⎇﹪η³﹪⁺⁺⊗ι⊖η׳¬‹ιη⊗η﹪⊕⊗ι⊕⊗η

Wypróbuj online! Link jest do pełnej wersji kodu. Kolejny port doskonałej odpowiedzi w języku C @ orlp.

APL (Dyalog Unicode) , 18 bajtów ^SBCS

Pełne monitowanie programu o nstandardowe wejście. Drukuje rozdzielone spacjami rozwiązanie na standardowe wyjście, używając ·pustych kwadratów i ⍟królowych.

⎕CY'dfns'
⊃queens⎕

Wypróbuj online!

⎕CY'dfns' C op r W „dfns” biblioteka

⎕ uzyskać dane wejściowe ze standardowego wejścia

queens znajdź wszystkie naprawdę unikalne rozwiązania Queens (bez odbić i rotacji)

⊃ wybierz pierwsze rozwiązanie

J , 49 bajtów

i.=/0({(1-.@e.,)@(([:(=#\){.|@-}.)\."1)#])!A.&i.]

Wypróbuj online!

Brutalna siła, testując wszystkie permutacje długości n .