(Trotz mehr als 60 Fragen mit dem Tag Schach haben wir keine einfache Herausforderung für N-Damen.)

Im Schach wird das N-Queens-Puzzle folgendermaßen beschrieben: Ordnen Sie die Königinnen bei gegebenem n x nSchachbrett und nKöniginnen so auf dem Schachbrett an, dass sich keine zwei Königinnen gegenseitig bedrohen. Unten finden Sie eine Beispiellösung für n = 8, von Wikipedia ausgeliehen.

Oder beim ASCII-Rendering:

xxxQxxxx
xxxxxxQx
xxQxxxxx
xxxxxxxQ
xQxxxxxx
xxxxQxxx
Qxxxxxxx
xxxxxQxx

Die Herausforderung hierbei wird darin bestehen, neine ASCII-Darstellung einer Lösung für das n-Queens-Rätsel einzugeben und auszugeben . Da es mehr als eine mögliche Lösung gibt (z. B. mindestens eine Rotation oder Reflexion), muss Ihr Code nur eine gültige Lösung ausgeben.

Eingang

Eine einzelne positive ganze Zahl nmit n >= 4 in jedem geeigneten Format . (n = 2 und n = 3 haben keine Lösungen, und n = 1 ist trivial, so dass diese ausgeschlossen sind)

Ausgabe

Die resultierende ASCII-Darstellung einer Lösung des oben beschriebenen N-Königinnen-Puzzles. Sie können zwei unterschiedliche ASCII-Werte auswählen, um Leerzeichen und Königinnen darzustellen. Dies kann wiederum in jedem geeigneten Format (einzelne Zeichenfolge, eine Liste von Zeichenfolgen, ein Zeichenfeld usw.) ausgegeben werden.

Regeln

• Führende oder nachfolgende Zeilenumbrüche oder Leerzeichen sind ebenso optional wie Leerzeichen zwischen Zeichen, sofern die Zeichen selbst korrekt ausgerichtet sind.
• Sie können entweder einen Algorithmus verwenden, um die möglichen Positionen zu berechnen, oder den expliziten "Treppenstufen" -Lösungsstil verwenden, je nachdem, welcher für Ihren Code Golfspieler ist.
• Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
• Fügen Sie nach Möglichkeit einen Link zu einer Online-Testumgebung hinzu, damit andere Benutzer Ihren Code ausprobieren können!
• Standardlücken sind verboten.
• Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

Beispiele

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 Bytes

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

Probieren Sie es online!

Semi-Brute-Force, nicht deterministischer Ansatz:

1. Generieren Sie eine zufällige Permutation der Zeilenpositionen
2. Generieren Sie eine zufällige Permutation der Spaltenpositionen
3. Stellen Sie sicher, dass keine Königinnen eine Diagonale oder Antidiagonale teilen
4. Bei Bedarf wiederholen.

Die erhaltene Lösung ist zufällig. Wenn Sie den Code erneut ausführen, erhalten Sie möglicherweise eine andere gültige Konfiguration. Die Laufzeit ist ebenfalls zufällig, aber der längste Testfall ( n = 10) wird in TIO die meiste Zeit in etwa 30 Sekunden beendet.

C 114 Bytes

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);}

Druckt direkt eine Lösung in O (1) Zeit.

Mathematica, 103 108 110 117 Bytes

-5 Bytes für DuplicateFreeQ->E!=##&@@@

-7 Bytes für ReplacePart[Array[],]->SparseArray[]

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

Rückgabe eines 2D-Arrays. Die Berechnung dauert 2,76 s und die Berechnung f[6]135 s f[7]. (In der aktuellen Version -wird 0und Qbis 1.

Der Algorithmus ähnelt der MATL-Antwort, aber hier ist der Code völlig brachial.

C - 222 Bytes

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]);}

Der Code ist nicht von mir, sondern vom IOCCC . Ich hoffe, ich verstoße nicht gegen Regeln. Außerdem werden hier alle Lösungen für N zwischen 4 und 99 angezeigt. Ich werde später versuchen, einen TIO-Link zu erhalten.

Jelly , 24 21 Bytes

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

Probieren Sie es online!

Angenommen, jede Dame wird in separaten Zeilen platziert, müssen wir nur die Spaltenindizes finden, in denen jede Dame platziert wird, um Konflikte zu vermeiden, die durch Generieren einer zufälligen Permutation [1, 2, ..., n]und Testen derselben ermittelt werden.

Erläuterung

,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 Bytes

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

Brute-Force-Suche durch alle Permutationen. Ich könnte das * entfernen und das Listenverständnis ausdrucken, aber sie sehen schrecklich aus.

Ausgabe:

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

Leicht ungolfed:

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 Bytes

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

Probieren Sie es online!

Dies basiert mehr oder weniger auf der C-Lösung von orlp .

Erläuterung

Lesen Sie die Anzahl der Damen, q , von stdin und berechnen Sie zwei Variablen für die spätere Verwendung: n = q - q%2und hn = n/2
Starten Sie die Hauptschleife, indem Sie r , die Zeilennummer, von q bis 0 durchlaufen und am Anfang der Schleife dekrementieren, also das erste r ist q minus 1.
Berechnen Sie den Versatz der Dame in jeder Zeile mit der folgenden Formel:

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

Geben Sie versetzte Leerzeichen aus, um die Position der Dame für die aktuelle Zeile einzurücken, plus ein zusätzliches Leerzeichen, nur weil dies die Ausgabeschleife vereinfacht.
Geben Sie das Qfür die Dame aus, gefolgt von einer neuen Zeile, um zur nächsten Zeile zu gelangen.
Testen Sie, ob r Null ist. In diesem Fall haben wir das Ende des Boards erreicht und können es verlassen. Andernfalls wiederholen wir die Hauptschleife erneut.

Haskell , 145 Bytes

Der offensichtliche Brute-Force-Ansatz:

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

Probieren Sie es online!

Netzhaut , 136 Bytes

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

Probieren Sie es online! Port of @ orlps ausgezeichnete C-Antwort. Erläuterung:

.+
$* 

Mit Leerzeichen in Unary konvertieren (nach dem steht ein Leerzeichen *).

$_;$`Q¶

Erstellen Sie NZeilen mit NLeerzeichen, a ;, dann 0..N-1Leerzeichen und dann a Q. Die verbleibenden Stufen gelten für alle Zeilen.

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

Ganzzahlige Division Ndurch 2. (Wickeln Sie das Ergebnis auch ein :;, um das Verankern von Mustern zu vereinfachen.)

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

Wenn der Schleifenindex gleich ist N/2*2, lassen Sie einfach so viele Leerzeichen.

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

Wenn N/2es ein Vielfaches von 3 ist, dann nimm den doppelten Schleifenindex plus eins, Modulo N/2*2+1.

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

Ansonsten verdoppeln Sie den Loop-Index plus (N/2-1)plus 3 in der unteren Hälfte des Boards, Modulo N/2*2.

( +)%\1?

Führen Sie die Modulo-Operation tatsächlich durch.

Kohle , 44 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Ein weiterer Port von @ orlps exzellenter C-Antwort.

APL (Dyalog Unicode) , 18 Byte ^SBCS

Vollständige Programmabfrage nvon stdin. Gibt eine durch Leerzeichen getrennte Lösung ·für leere Felder und ⍟für Damen aus.

⎕CY'dfns'
⊃queens⎕

Probieren Sie es online!

⎕CY'dfns' C op y die "DFNS" library

⎕ Holen Sie sich die Eingabe von stdin

queens Finde alle wirklich einzigartigen Queens-Lösungen (keine Reflexionen oder Rotationen)

⊃ Wähle die erste Lösung

J , 49 Bytes

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

Probieren Sie es online!

Brute Force durch Testen aller Permutationen der Länge n .