Jeśli nie wiesz, czym jest królowa w szachach, nie ma to większego znaczenia; to tylko nazwa :)

Twój wkład będzie kwadratem o dowolnej szerokości i wysokości zawierającym pewną liczbę królowych. Tablica wejściowa będzie wyglądać następująco (ta tablica ma szerokość i wysokość 8):

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

Na tej planszy jest 8 królowych. Gdyby było na przykład 7, 1 lub 10, plansza nie byłaby ważna.

Tutaj używamy .pustej przestrzeni i Qkrólowej. Zamiast tego możesz użyć dowolnego znaku spacji, który chcesz.

Dane wejściowe można zweryfikować jako poprawne i powinieneś wydrukować (lub zwrócić) prawdziwą wartość (jeśli nie jest poprawna, powinieneś wydrukować (lub zwrócić) wartość fałszu). Jest ważny, ponieważ żadna królowa nie znajduje się w tym samym rzędzie, kolumnie, przekątnej lub przeciw przekątnej jak inne .

Przykłady (nie wypisuj rzeczy w nawiasach):

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

Podkreślę, że dane wejściowe są prawidłowe tylko wtedy, gdy żadna królowa nie znajduje się w tym samym rzędzie, kolumnie, przekątnej lub anty-przekątnej jak inne .

Zasady

• Nigdy nie otrzymasz pustego wejścia
• Jeśli dane wejściowe zawierają mniej królowych niż pierwiastek kwadratowy obszaru planszy, nie są poprawne.
• Uwaga: nie ma prawidłowych rozwiązań dla płyty 2x2 lub 3x3, ale istnieje rozwiązanie dla każdej kwadratowej płyty o innym rozmiarze , gdzie szerokość i wysokość są liczbą naturalną.
• Dane wejściowe mogą być w dowolnym rozsądnym formacie, zgodnie z zasadami PPCG
• Dane wejściowe zawsze będą kwadratowe
• W przykładach użyłem 1 i 0, ale możesz użyć dowolnych wartości prawdziwości lub fałszowania (takich jak Why yes, sir, that is indeed the casei Why no, sir, that is not the case)

Ponieważ jest to kod-golf , wygrywa najkrótszy kod!

Ślimaki , 14 bajtów

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

Wypróbuj online!

Nie ma to jak język dopasowania wzoru 2D dla problemu decyzyjnego 2D. :)

Wyjaśnienie

&W pierwszym wierszu jest opcja Tryb mecz, który wymaga wzorzec w drugim wierszu, aby dopasować z każdej możliwej pozycji w wejściu. W takim przypadku program drukuje 1, w przeciwnym razie drukuje 0.

Jeśli chodzi o sam wzorzec, zwróć uwagę, że )na końcu jest niejawny .

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

Dlaczego to działa najłatwiej zobaczyć, zaczynając od negatywnego spojrzenia w przyszłość: upewniając się, że nie ma Qlinii prostej od drugiej Q, którą już znaleźliśmy, upewniamy się, że nie ma więcej niż N królowych (w przeciwnym razie byłoby być dwiema w jednym rzędzie i nie byłoby możliwe znalezienie tych królowych bez znalezienia innej). Następnie pierwsza część, upewniając się, że królowa jest osiągalna w ortogonalnym kierunku z dowolnej pozycji, upewnia się, że są dokładnie N królowych. Gdyby jednego brakowało, byłby rząd i kolumna bez królowej. Zaczynając od ich skrzyżowania, nie byłoby możliwe znalezienie królowej, idąc tylko w kierunku ortogonalnym.

Galaretka , 17 lub 15 bajtów

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

Wypróbuj online!

Używa ‘królowej i ¹pustej przestrzeni. (Jest to głównie konsekwencja zakazu pobierania danych wejściowych jako tablicy, ponieważ wymusza to, aby dane wejściowe były łańcuchami; konwersja ciągów na liczby całkowite jest trudna w Jelly, przy czym najłatwiejszą metodą jest ocena, i okazuje się, że zamiast 1 i 0, używając „dodaj 1” ( ‘) i „dodaj 0” (¹ ) pozwala pominąć kilka instrukcji sumowania i mapowania, ponieważ możemy policzyć królowe na liście, oceniając je.) Wartości true i falsey są normalne dla Jelly 1i 0.

EDYCJA: Pytanie zostało zmienione, odkąd napisałem tę odpowiedź, aby umożliwić przyjmowanie danych wejściowych jako matrycy. Pozwala to upuścić wiodące Ỵµ, oszczędzając 2 bajty. Prawdopodobnie pozwala to również zmienić format wejściowy na bardziej normalny, wykorzystując Sraczej sumowanie niż Vocenę, ale nie sądzę, że to oszczędza bajty i podobał mi się ten funky format.

Wyjaśnienie

Ỵµ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.

Zatem podstawową ideą jest zapewnienie, że na każdej antydiagonalnej, przekątnej i kolumnie znajduje się najwyżej jedna królowa; i dokładnie jedna królowa w każdym rzędzie. Te warunki są razem wystarczające, aby na każdej z czterech rodzajów linii była najwyżej jedna królowa i liczba królowych równa długości boku planszy.

Nawiasem mówiąc, galaretka prawdopodobnie mogłaby zrobić z wbudowanym w antydiagonale, ale AFAICT wydaje się, że nie ma takiego, więc muszę zadowolić się odbiciem planszy, a następnie wzięciem przekątnych.

Inną interesującą uwagą jest to, że zmiana =1Ṃna E(wszystkie równe) daje uogólniony moduł sprawdzania n- kwadratów, który akceptuje również tablicę n × n, w której każdy rząd, kolumna, przekątna i antypoślizgowa zawiera nie więcej niż k królowych, a tablica zawiera dokładnie kn królowe. Ograniczenie k do równego 1 faktycznie kosztuje dwa bajty.

Oktawa, 57 70 67 51 52 bajtów

Zaoszczędzono 1 bajt flipzamiast rot90podziękowań dla @LuisMendo, ale znaleziono błąd w przypadku 1x1

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

Pobiera dane wejściowe jako macierz binarną, gdzie 1 oznacza Królową, a 0 reprezentuje pustą przestrzeń.

Tworzy anonimową funkcję, która najpierw łączy macierz wejściową i jej transpozycję.

spdiagstworzy macierz z taką samą liczbą wierszy jak argument, z przekątnymi zamienionymi w kolumny (w razie potrzeby uzupełnionymi zerami), więc połącz spdiagsmacierz wejściową, aby uzyskać przekątne ispdiags uzupełnionymi zerami matrycę obróconą w poziomie, aby uzyskać antydiagonale.

Teraz weź sumę każdej kolumny skonkatowanej macierzy i upewnij się, że każda kolumna ma dokładnie 1.

Próbka uruchomiona na ideone .

MATL , 38 34 bajtów

4 bajty wyłączone dzięki @beaker !

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

Dane wejściowe to tablica 2D zer i jedynek, wykorzystująca średniki jako separatory wierszy.

To powoduje, że wektor kolumnowy z nich jest prawdziwy, a wektor kolumnowy zawiera co najmniej jedno zero jako fałsz.

Wypróbuj online! Kod stopki toif gałąź służąca do wykazania prawdziwości lub fałszu.

Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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

jot , 37 bajtów

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

Anonimowy ciąg funkcji, który jako argument przyjmuje macierz boolowską.

Wypróbuj online!

( +/suma &z ,gmatwaninie =równa# się zgadzają wierszy)

* i (razy razy)

1jeden =równa [:się>./ maksimum

+/sumy /.po przekątnej, i (lit. catenated to)

+/sumy /.ukośnie &w |.odwrotnej, i

+/ sumy w poprzek , i

+/kwoty &z |:transpozycją

SnakeEx , 67 bajtów

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

Używa _zamiast. na wejściu. Zwraca 1 lub więcej dopasowań dla prawdy, 0 dopasowań dla falsey. Tłumacz online znajduje się pod linkiem w nagłówku.

Wyjaśnienie

SnakeEx to język z wyzwania 2-D Pattern Matching . Definiuje „węże”, które poruszają się po siatce, dopasowując rzeczy. Węże mogą odradzać inne węże, dzięki czemu język jest dość mocny.

Spójrzmy na ten program od podstaw.

n:_+$

Definiuje węża, nktóry pasuje do 1 lub więcej znaków podkreślenia, a następnie do krawędzi siatki. Pamiętaj, że może to być jeden z 8 głównych kierunków - kierunek jest ustalany, kiedy wąż się odradza.

q:_*Q_*$

Podobnie jak npowyżej, definiuje się to qjako węża, który pasuje do dowolnej liczby znaków podkreślenia, jednego Q, dowolnej liczby znaków podkreślenia i krawędzi siatki. Innymi słowy, wiersz / kolumna / przekątna, która ma tylko jedną królową.

e:.$

e jest wężem, który pasuje do jednej postaci i krawędzi siatki.

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

Główny wąż m wykorzystuje te klocki do sprawdzania całej planszy. Pod względem koncepcyjnym biegnie wokół zewnętrznych krawędzi siatki, spawnując inne węże, aby sprawdzić, czy wszystkie kolumny i rzędy mają dokładnie jedną królową, a wszystkie przekątne mają co najwyżej jedną królową. Jeśli którykolwiek ze spawnowanych węży się nie zgadza, całe dopasowanie kończy się niepowodzeniem. Rozwalmy to.

• ( )%{4}uruchamia to, co jest w nawiasach 4 razy, raz dla każdej strony. (W dalszej części pomocne jest zobrazowanie konkretnej strony - powiedzmy, górnej krawędzi siatki, zaczynając od lewego górnego rogu i przesuwając się w prawo.)
• {q<>}spawnuje qwęża w tym samym kierunku, w którym porusza się główny wąż. To weryfikuje, czy bieżąca krawędź spełnia zasadę „dokładnie jednej królowej”. Zauważ, że odrodzone węże nie poruszają wskaźnikiem dopasowania głównego węża, więc wciąż jesteśmy na początku krawędzi.
• ( )* dopasowuje 0 lub więcej elementów znajdujących się w nawiasach.
• {q<R>}spawnuje qwęża obróconego w prawo od głównego węża. (Np. Jeśli główny wąż porusza się w prawo wzdłuż górnej krawędzi, ten wąż porusza się w dół.) Sprawdza każdą kolumnę / wiersz.
• [ ] pasuje do jednej z opcji w nawiasach:
  • {q<RF>}spawnuje qwęża obróconego o 45 stopni w prawo (tj. Rdo Fprzodu i do przodu) od kierunku głównego węża. qWęża pasuje jeśli przekątna zawiera dokładnie jedną królową.
  • {n<RF>}nzamiast tego spawnuje węża. nWęża pasuje jeśli przekątna zawiera żadnych królowych.
• . dopasowuje dowolny znak, przesuwając wskaźnik dopasowania do przodu.
• Po sprawdzeniu jak największej liczby poziomów i przekątnych, sprawdzamy, czy jesteśmy na krawędzi, odradzając się {e<>}.
• Na koniec <R>obraca głównego węża w prawo, gotowy do dopasowania do następnej krawędzi.

Dziwne rzeczy

• W programie nie ma nic, co zapewni, że dopasowanie rozpocznie się w zewnętrznym rogu. W rzeczywistości prawdziwe przypadki testowe dają kilka dopasowań, z których niektóre zaczynają się gdzieś wewnątrz. Mimo to żaden z przypadków Falsey, które próbowałem, nie wygenerował fałszywych trafień.
• Jeśli dobrze czytam specyfikację języka , powinienem móc użyć X(gałąź we wszystkich kierunkach po przekątnej) zamiast RF. Niestety tłumacz online stwierdził, że to błąd składniowy. Próbowałem też *(oddział we wszystkich kierunkach), ale to zawiesiło tłumacza.
• Teoretycznie coś takiego _*Q?_*$powinno działać w celu dopasowania „najwyżej jednej królowej” na przekątnych, ale to także zawiesiło tłumacza. Domyślam się, że możliwość pustych dopasowań powoduje problemy.

Rubinowy, 120 bajtów

Funkcja Lambda oparta na oryginalnej specyfikacji, która wymagała wprowadzenia jako łańcucha.

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

konwertuje liczby Q na liczby zespolone i odejmuje je od siebie. Jeśli różnica między współrzędnymi dwóch królowych jest pozioma, pionowa lub ukośna, podniesienie jej do czwartej potęgi da rzeczywistą liczbę, a układ będzie nieważny.

Niegolfowany w programie testowym

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 bajtów

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

Wypróbuj online!

-32 bajty dzięki @beaker zauważając zmianę specyfikacji wejściowej; Zmieniłem język z Python 3 na 2, dzięki czemu mogłem używać inputdanych wejściowych jako tablicy ciągów lub tablicy tablic znaków.

-45 bajtów dzięki @Leaky Nun

JavaScript (ES6), 115 bajtów

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=[])

Nie golfowany:

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

Rubin, 155 bajtów

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

To jest okropne do przeczytania, więc poniżej mam nieco mniej golfową wersję

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

To jest ten sam kod, ale z kilkoma nowymi wierszami, aby rozróżnić, co się dzieje.

Sam kod jest anonimową funkcją lambda, która pobiera tablicę łańcuchów ( x) w formacie ["..Q", "Q..", ".Q."].

Pierwszy wiersz odwzorowuje każdy ciąg na indeks znaku Q w tym ciągu. Jeśli nie ma znaku Q, jest on zastępowany -2 ¹ . Ta nowa tablica indeksów jest przypisana do zmiennej y.

Następny wiersz zamyka tę tablicę indeksów, przesuwając ją o jeden (obrócony). Daje to tablicę par następujących po sobie wskaźników.

Kolejna linia jest szczególnie skomplikowana. Przechodzi przez każdą z par indeksów i odejmuje mniejszą od większej. Jeśli jest to 1 (i nie jesteśmy przy ostatniej parze ² ), to są dwie królowe, które są na tej samej przekątnej i wstawiana jest wartość -2, w przeciwnym razie wstawiany jest oryginalny indeks królowej w ciągu .

Ostatni wiersz sumuje wszystkie indeksy dla każdego i sprawdza, czy jest to numer trójkąta dla n-1, gdzie n jest szerokością (lub wysokością) kwadratu.

1: -1 byłoby moim celem, ale jest to 1 oprócz 0, więc popsułoby się sprawdzanie przekątnych. Negatywność jest ważna, aby błędna była ostateczna suma. Myślałem o dużej liczbie (z pojedynczymi cyframi), takiej jak 9, ale nie jestem pewien, czy nie spowoduje to niepoprawnej weryfikacji.
2: Plansza się nie zawija, podczas gdy rotatefunkcja tablicy Ruby ma tę funkcję, a jeśli ostatnia para różni się o jedną, nie ma to znaczenia - to nie jest przekątna.

PHP, 137 143 bajtów

zainspirowany rozwiązaniem Neila

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;

pobiera dane wejściowe z argumentu pierwszego wiersza poleceń; biegać z -r. Wymaga podziału wiersza na jeden bajt.
^{Właściwie możesz użyć dowolnego znaku, z wyjątkiem 0podziału linii.}
wypisuje true ( 1) lub false (pusty ciąg).

awaria

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 172 171 bajtów

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

Anonimowa funkcja pobierająca listę ciągów jako dane wejściowe.

Python 2 , 175 bajtów

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