Si vous ne savez pas ce qu'est une reine aux échecs, peu importe; c'est juste un nom :)

Votre entrée sera un carré de largeur et de hauteur arbitraires contenant une certaine quantité de reines. La carte d'entrée ressemblera à ceci (cette carte a une largeur et une hauteur de 8):

...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q..

Il y a 8 reines sur ce tableau. S'il y avait, disons, 7, 1 ou 10 ici, le tableau ne serait pas valide.

Ici, nous utilisons un .pour un espace vide et un Qpour une reine. Vous pouvez également utiliser à la place n'importe quel caractère non blanc.

Cette entrée peut être vérifiée comme valide et vous devez imprimer (ou renvoyer) une valeur véridique (si elle n'était pas valide, vous devez imprimer (ou renvoyer) une valeur falsifiée). Elle est valable car aucune reine n'est dans la même ligne, colonne, diagonale ou anti-diagonale qu'une autre .

Exemples (ne pas afficher les éléments entre parenthèses):

...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q..

1

...Q.
Q....
.Q...
....Q
..Q..

0

Q.
Q.

0

..Q
...
.Q.

0 (this is 0 because there are only 2 queens on a 3x3 board)


..Q.
Q...
...Q
.Q..

1

Q

1 (this is valid, because the board is only 1x1, so there's no queen that can take another)

Permettez-moi de souligner qu'une entrée n'est valide que si aucune reine n'est dans la même ligne, colonne, diagonale ou anti-diagonale qu'une autre .

Règles

• Vous ne recevrez jamais une entrée vide
• Si l'entrée contient moins de reines que la racine carrée de la zone du tableau, elle n'est pas valide.
• Notez qu'il n'y a pas de solutions valides pour une carte 2x2 ou 3x3, mais il existe une solution pour toutes les autres cartes carrées de taille , où la largeur et la hauteur sont un nombre naturel.
• L'entrée peut être dans n'importe quel format raisonnable, selon les règles PPCG
• L'entrée sera toujours un sqaure
• J'ai utilisé 1 et 0 dans les exemples, mais vous pouvez utiliser n'importe quelle valeur vraie ou fausse (comme Why yes, sir, that is indeed the caseet Why no, sir, that is not the case)

Comme il s'agit de code-golf , le code le plus court gagne!

Escargots , 14 octets

&
o.,\Q!(z.,\Q

Essayez-le en ligne!

Rien de tel qu'un langage de correspondance de motifs 2D pour un problème de décision 2D. :)

Explication

Le &sur la première ligne est une option de mode de correspondance qui nécessite que le motif sur la deuxième ligne corresponde à toutes les positions possibles dans l'entrée. Si tel est le cas, le programme s'imprime 1, sinon il s'imprime 0.

Quant au motif lui-même, notez qu'il y a un implicite )à la fin.

o       ,, Move in any orthogonal direction (up, down, left or right).
.,\Q    ,, Make sure that there's a Q somewhere in that direction from the
        ,, starting position of the match.
!(      ,, After finding the Q, make sure that the following part _doesn't_ match:
  z     ,,   Move in any orthogonal or diagonal direction.
  .,\Q  ,,   Try to find another Q in a straight line.
)

Il est plus facile de comprendre pourquoi cela fonctionne en partant de l'anticipation négative: en veillant à ce qu'il n'y en ait pas Qen ligne droite par rapport à l'autre que Qnous avons déjà trouvé, nous nous assurons qu'il n'y a pas plus de N reines (sinon, il y aurait être deux dans une rangée, et il ne serait pas possible de trouver ces reines sans en trouver une autre). Ensuite, la première partie, en s'assurant qu'il y a une reine accessible dans une direction orthogonale à partir de n'importe quelle position, s'assure qu'il y a exactement N reines. S'il en manquait un, il y aurait une rangée et une colonne sans reine. À partir de l'intersection de celles-ci, il ne serait pas possible de trouver une reine en allant uniquement dans une direction orthogonale.

Gelée , 17 ou 15 octets

ỴµUŒD;ŒD;ZVṀ;V=1Ṃ

Essayez-le en ligne!

Utilise ‘une reine et ¹un espace vide. (C'est principalement une conséquence de l'interdiction de prendre l'entrée en tant que tableau, car elle force l'entrée à être des chaînes; la conversion de chaînes en entiers est difficile dans Jelly, la méthode la plus simple étant l'évaluation, et il s'avère qu'au lieu de 1 et 0, en utilisant "add 1" ( ‘) et "add 0" ( ¹) permettent d'omettre plusieurs instructions de somme et de carte, car nous pouvons compter les reines dans une liste en l'évaluant.) Les valeurs truey et falsey sont normales de Jelly 1et 0.

EDIT: La question a été modifiée depuis que j'ai écrit cette réponse pour permettre de prendre l'entrée comme une matrice. Cela permet de supprimer le début Ỵµ, économisant 2 octets. Il permet également probablement de changer le format d'entrée en quelque chose de plus normal, en utilisant Spour additionner plutôt que Vpour évaluer, mais je ne pense pas que cela économise des octets et j'aime un peu ce format génial.

Explication

ỴµUŒD;ŒD;ZVṀ;V=1Ṃ
Ỵ                    Split on newlines.
 µ                   Set this value as the default for missing arguments.
     ;  ;            Concatenate the following three values:
  UŒD                - the antidiagonals;
      ŒD             - the diagonals;
         Z           - and the columns.
          V          Evaluate (i.e. count the queens on) all of those.
           Ṁ         Take the largest value among the results.
            ;V       Append the evaluation (i.e. queen count) of {each row}.
              =1     Compare each value to 1.
                Ṃ    Take the minimum (i.e. most falsey) result.

L'idée de base est donc de s'assurer qu'il y a au plus une reine sur chaque antidiagonale, diagonale et colonne; et exactement une reine sur chaque rangée. Ces conditions sont suffisamment réunies pour exiger qu'il y ait au plus une reine sur chacun des quatre types de ligne, et un nombre de reines égal à la longueur du côté de la planche.

Soit dit en passant, Jelly pourrait probablement faire avec un intégré pour les antidiagonales, mais AFAICT il ne semble pas en avoir, donc je dois me contenter de réfléchir la planche et de prendre ensuite les diagonales.

Une autre note intéressante est que le passage =1Ṃà E(tous égaux) donne un vérificateur de n -queens généralisé , qui acceptera également un tableau n × n où chaque ligne, colonne, diagonale et antidiagonale ne contient pas plus de k reines, et le tableau contient exactement kn reines. Restreindre k à 1 équivaut en fait à deux octets.

Octave, 57 70 67 51 52 octets

Enregistré 1 octet en utilisant flipau lieu de rot90grâce à @LuisMendo, mais a trouvé un bug sur le cas 1x1

@(A)all(sum([A A' (d=@spdiags)(A) d(flip(A))],1)==1)

Prend l'entrée comme une matrice binaire avec 1 représentant une reine et 0 représentant un espace vide.

Crée une fonction anonyme qui concatène d'abord la matrice d'entrée et sa transposition.

spdiagscrée une matrice avec le même nombre de lignes que l'argument, avec les diagonales transformées en colonnes (complétées par un zéro si nécessaire), donc concaténez spdiagsla matrice d'entrée pour obtenir les diagonales et spdiagsla matrice inversée horizontalement pour obtenir les antidiagonales.

Prenez maintenant la somme de chaque colonne de la matrice concaténée et assurez-vous que chaque colonne est exactement 1.

Exemple de run sur ideone .

MATL , 38 34 octets

4 octets de moins grâce à @beaker !

sG!sGt&n_w&:&XdsGP5M&Xdsv2<GnGzU=*

L'entrée est un tableau 2D de zéros et de uns, utilisant des points-virgules comme séparateurs de lignes.

Cela produit un vecteur de colonne de uns comme véridique, et un vecteur de colonne contenant au moins un zéro comme fausse.

Essayez-le en ligne! Le code de pied de page est une ifbranche pour démontrer la véracité ou la fausseté.

Ou vérifiez tous les cas de test .

Explication

s      % Input binary matrix implicitly. Sum of columns. Gives a row vector
G!     % Paste input again. Transpose
s      % Sum of columns (rows in the original matrix). Gives a row vector
G      % Paste input again
t&n    % Duplicate. Push number of rows and number of columns (will be equal)
_w     % Negate, flip
&:     % Binary range. Gives [-n -n+1 ... n] for input of size n×n
&Xd    % Get diagonals -n through n. This gives all diagonals as colums
s      % Sum of each column (diagonals of original matrix). Gives a row vector
GP     % Paste input again. Flip vertically
5M     % Push [-n -n+1 ... n] again
&Xd    % Get diagonals -n through n (anti-diagonals of original matrix)
s      % Sum of each column. Gives a row vector
v      % Concatenate everything into a column vector
2<     % True for elements that are less than 2
Gn     % Paste input again. Number of elements
Gz     % Paste input again. Number of nonzeros (i.e. of queens)
U      % Square
=      % True if equal
*      % Mutiply, element-wise

J , 37 octets

(+/&,=#)*1=[:>./+//.,+//.&|.,+/,+/&|:

Train de fonctions anonyme qui prend comme argument la matrice booléenne.

Essayez-le en ligne!

( +/la somme &du ,ravel =est égale #au décompte des rangées)

* et (lit. fois)

1on =est égal [:au >./maximum de

+/les sommes en /.diagonale ,et (lit. caténalisé à)

+/les sommes en /.diagonale &de |.l'inverse ,et

+/les sommes à travers ,et

+/les sommes &de |:la transposition

SnakeEx , 67 octets

m:({q<>}({q<R>}[{q<RF>}{n<RF>}].)*{e<>}<R>)%{4}
e:.$
q:_*Q_*$
n:_+$

Utilise _à la place de. dans l'entrée. Renvoie 1 correspondance ou plus pour véridique, 0 correspondance pour falsey. Vous pouvez trouver un interprète en ligne sur le lien dans l'en-tête.

Explication

SnakeEx est un langage du défi de correspondance de motifs 2-D . Il définit des "serpents" qui se déplacent autour des trucs correspondant à la grille. Les serpents peuvent engendrer d'autres serpents, ce qui rend le langage assez puissant.

Regardons ce programme de bas en haut.

n:_+$

Cela définit un serpent nqui correspond à un ou plusieurs traits de soulignement, puis au bord de la grille. Notez que cela peut être dans l'une des 8 directions cardinales - la direction est déterminée lorsque le serpent apparaît.

q:_*Q_*$

Similaire à nci-dessus, cela définit qcomme un serpent qui correspond à n'importe quel nombre de traits de soulignement, un seul Q, n'importe quel nombre de traits de soulignement et le bord de la grille. En d'autres termes, une ligne / colonne / diagonale qui n'a qu'une seule reine.

e:.$

e est un serpent qui correspond à un caractère et au bord de la grille.

m:({q<>}({q<R>}[{q<RF>}{n<RF>}].)*{e<>}<R>)%{4}

Le serpent principal m utilise ces blocs de construction pour vérifier l'ensemble du plateau. Conceptuellement, il court sur les bords extérieurs de la grille, engendrant d'autres serpents pour vérifier que toutes les colonnes et lignes ont exactement une reine et que toutes les diagonales ont au plus une reine. Si l'un des serpents engendrés ne correspond pas, la correspondance entière échoue. Décomposons-le.

• ( )%{4}exécute ce qui est à l'intérieur des parenthèses 4 fois, une fois de chaque côté. (Dans ce qui suit, il est utile d'imaginer un côté particulier - disons, le bord supérieur de la grille, en partant du coin supérieur gauche et en se déplaçant vers la droite.)
• {q<>}engendre un qserpent dans la même direction que le serpent principal se déplace. Cela vérifie que le bord actuel répond à la règle "exactement une reine". Notez que les serpents engendrés ne déplacent pas le pointeur de correspondance du serpent principal, nous sommes donc toujours au début du bord.
• ( )* correspond à 0 ou plus de ce qui est à l'intérieur des parenthèses.
• {q<R>}engendre un qserpent tourné vers la droite de la direction du serpent principal. (Par exemple, si le serpent principal se déplace vers la droite le long du bord supérieur, ce serpent se déplace vers le bas.) Ceci vérifie chaque colonne / ligne.
• [ ] correspond à l'une des options à l'intérieur des crochets:
  • {q<RF>}engendre un qserpent tourné à 45 degrés vers la droite (c'est-à-dire vers la droite Ret vers l' For) à partir de la direction du serpent principal. Le qserpent correspond si la diagonale contient exactement une reine.
  • {n<RF>}engendre un nserpent à la place. Le nserpent correspond si la diagonale ne contient pas de reines.
• . correspond à n'importe quel caractère, déplaçant le pointeur de correspondance vers l'avant.
• Après avoir vérifié autant d'horizontales et de diagonales que possible, nous vérifions que nous sommes au bord en se reproduisant {e<>}.
• Enfin, <R>tourne le serpent principal à droite, prêt à correspondre au bord suivant.

Trucs bizarres

• Il n'y a rien dans le programme pour s'assurer que l'appariement commence dans un coin extérieur. En fait, les cas de test véridiques produisent plusieurs correspondances, dont certaines commencent à l'intérieur quelque part. Malgré cela, aucun des cas de falsey que j'ai essayés n'a généré de faux positifs.
• Si je lis bien la spécification de langue , j'aurais dû pouvoir utiliser X(branche dans toutes les directions diagonales) à la place de RF. Malheureusement, l'interprète en ligne a déclaré qu'il s'agissait d'une erreur de syntaxe. J'ai aussi essayé *(branchement dans toutes les directions), mais ça a suspendu l'interprète.
• Théoriquement, quelque chose comme cela _*Q?_*$devrait fonctionner pour faire correspondre "au plus une reine" dans les diagonales, mais cela a également suspendu l'interprète. Je suppose que la possibilité de correspondances vides pose des problèmes.

Rubis, 120 octets

Fonction Lambda basée sur la spécification d'origine qui nécessitait une entrée sous forme de chaîne.

->s{t=k=0
a=[]
s.bytes{|i|i>65&&(a.map{|j|t&&=((k-j)**4).imag!=0};a<<k)
k=i<11?k.real+1:k+?i.to_c}
t&&~a.size**2>s.size}

convertit les Q en nombres complexes et les soustrait les uns des autres. Si la différence entre les coordonnées de deux reines est horizontale, verticale ou diagonale, l'élever à la 4e puissance donnera un nombre réel et l'arrangement n'est pas valide.

Non testé dans le programme de test

f=->s{                                 #Take input as string argument.
  t=k=0                                #k=coordinate of character. t=0 (truthy in ruby.)
  a=[]                                 #Empty array for storing coordinates.
  s.bytes{                             #Iterate through all characters as bytes.
    |i|i>65&&(                         #If alphabetical, compare the current value of k to the contents of a
      a.map{|j|t&&=((k-j)**4).imag!=0} #If k-j is horizontal, vertical or diagonal, (k-j)**4 will be real and t will be false
      a<<k)                            #Add the new value of k to the end of a.
    k=i<11?k.real+1:k+?i.to_c          #If not a newline, increment the imaginary part of k. If a newline, set imaginary to 0 and increment real
  }                                    #s.size should be a*a + a newlines. ~a.size = -1-a.size, so ~a.size**2 = (a.size+1)**2
t&&~a.size**2>s.size}                  #compare a.size with s.size and AND the result with t. Return value. 


p f["...Q....
......Q.
..Q.....
.......Q
.Q......
....Q...
Q.......
.....Q.."]

p f["...Q.
Q....
.Q...
....Q
..Q.."]

p f["Q.
Q."]

p f["..Q
...
.Q."]

p f["..Q.
Q...
...Q
.Q.."]

p f["Q"]

Python 3 , 232 200 155 octets

d=1
f=input()
Q=[]
for i in f:d=[0,d][i.count('Q')==1];Q+=[(len(Q),i.index('Q'))]
print[0,d][sum(k[1]==i[1]or sum(k)==sum(i)for k in Q for i in Q)==len(Q)]

Essayez-le en ligne!

-32 octets grâce à @beaker constatant un changement dans les spécifications d'entrée; J'ai changé la langue de Python 3 en 2, ce qui me permet d'utiliserinput entrée comme un tableau de chaînes ou un tableau de tableaux de caractères.

-45 octets grâce à @Leaky Nun

JavaScript (ES6), 115 octets

a=>!a.some((b,i)=>b.some((q,j)=>q&&h[i]|v[j]|d[i+j]|e[i-j]|!(h[i]=v[j]=d[i+j]=e[i-j]=1))|!h[i],h=[],v=[],d=[],e=[])

Non golfé:

function queens(arr) {
    horiz = [];
    vert = [];
    diag = [];
    anti = [];
    for (i = 0; i < arr.length; i++) {
        for (j = 0; j < arr.length; j++) {
            if (arr[i][j]) { // if there is a queen...
                if (horiz[i]) return false; // not already on the same row
                if (vert[j]) return false; // or column
                if (diag[i + j]) return false; // or diagonal
                if (anti[i - j]) return false; // or antidiagonal
                horiz[i] = vert[j] = diag[i + j] = anti[i - j] = true; // mark it
            }
        }
        if (!horiz[i]) return false; // fail if no queen in this row
    }
    return true;
}

Rubis, 155 octets

->x{(y=x.map{|r|(i=r.index ?Q)==r.rindex(?Q)?i:p or-2}).zip(y.rotate).map.with_index{|n,i|n.max-n.min==1&&i<y.size-1?-2:n[0]}.inject(:+)*2==(s=x.size)*~-s}

C'est horrible à lire, j'ai donc une version un peu moins golfée ci-dessous

->x{
    (y=x.map{|r|(i=r.index ?Q)==r.rindex(?Q)?i:p or-2})
    .zip(y.rotate)
    .map.with_index{|n,i|n.max-n.min==1&&i<y.size-1?-2:n[0]}
    .inject(:+)*2==(s=x.size)*~-s
}

C'est le même code, mais avec quelques nouvelles lignes pour séparer ce qui se passe.

Le code tself est une fonction lambda anonyme qui prend un tableau de chaînes ( x) au format["..Q", "Q..", ".Q."] .

La première ligne mappe chaque chaîne à l'index du caractère Q dans cette chaîne. S'il n'y a pas de caractère Q, il est remplacé par -2 ¹ . Ce nouveau tableau d'indices est affecté à la variabley .

La ligne suivante zippe ce tableau d'index avec lui-même décalé d'un (pivoté). Il en résulte un tableau de paires d'indices consécutifs.

La ligne suivante est particulièrement compliquée. Il passe par chacune des paires d'indices et soustrait le plus petit du plus grand. Si c'est 1 (et nous ne sommes pas à la dernière paire ² ), alors il y a deux reines qui sont sur la même diagonale, et une valeur de -2 est insérée, sinon l'index original de la reine dans la chaîne est inséré .

La dernière ligne résume tous les index de chacun et vérifie s'il s'agit du numéro du triangle pour n-1, où n est la largeur (ou la hauteur) du carré.

1: -1 aurait été mon choix, mais c'est 1 en dehors de 0, donc je jouerais avec la vérification des diagonales. Son caractère négatif est important pour que la somme finale soit fausse. J'ai pensé à un nombre élevé (avec un seul chiffre) comme 9, mais je ne peux pas être sûr que cela n'entraînera pas une vérification incorrecte.
2: La carte ne s'enroule pas, contrairement à la rotatefonction de tableau de ruby , et si la dernière paire est différente d'une unité, cela n'a pas d'importance - ce n'est pas une diagonale.

PHP, 137 143 octets

inspiré par solution de Neil

for($n=1+strlen($s=$argv[1])**.5|0;($c=$s[$p])&&!(Q==$c&&$v[$x=$p%$n]++|$h[$x=$p/$n]++|$d[$y-$x]++|$a[$y+$x]++);$p++);echo$n-1==count($a)&&!$c;

prend l'entrée du premier argument de ligne de commande; courir avec -r. Nécessite des sauts de ligne à un octet.
^{En fait, vous pouvez utiliser n'importe quel caractère sauf 0pour le saut de ligne.}
affiche vrai ( 1) ou faux (chaîne vide).

panne

for($n=1+strlen($s=$argv[1])**.5|0; // copy input to $s, $n=size+1 (for the linebreak)
    ($c=$s[$p])&&!(                 // loop through characters
        Q==$c&&                         // if queen: test and increment lines
            $v[$x=$p%$n]++|$h[$x=$p/$n]++|$d[$y-$x]++|$a[$y+$x]++
    );                                  // break if a line had been marked before
    $p++);
echo$n-1==count($a)             // print result: true for $n-1(=size) marks
    &&!$c;                      // and loop has finished

Python 3 , 185 176 175 175 172 171 octets

lambda x,c=lambda x:x.count("Q")==1:all([*map(c,x+[[l[i]for l in x]for i in range(len(x[0]))])])*~any(map(lambda s:"Q%sQ"%(s*".")in"".join(x),[len(x[0]),len(x[0])-2]))==-1

Une fonction anonyme prenant une liste de chaînes en entrée.

Python 2 , 175 octets

lambda x:all([a.count("Q")==1for a in x]+[[l[i]for l in x].count("Q")==1for i in range(len(x[0]))]+[all(map(lambda s:"Q%sQ"%(s*".")not in"".join(x),[len(x[0]),len(x[0])-2]))])