Jika Anda tidak tahu apa arti ratu dalam catur, itu tidak masalah; itu hanya nama :)

Input Anda akan berupa kuadrat lebar dan tinggi acak yang berisi sejumlah ratu. Papan input akan terlihat seperti ini (papan ini memiliki lebar dan tinggi 8):

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

Ada 8 ratu di papan ini. Jika ada, katakanlah, 7, atau 1, atau 10 di sini, dewan tidak akan valid.

Di sini kita gunakan .untuk ruang kosong, dan Quntuk ratu. Anda dapat, sebagai alternatif, menggunakan karakter non-spasi putih yang Anda inginkan.

Input ini dapat diverifikasi sebagai valid, dan Anda harus mencetak (atau mengembalikan) nilai yang sebenarnya (jika tidak valid, Anda harus mencetak (atau mengembalikan) nilai palsu). Ini valid karena tidak ada ratu di baris yang sama, kolom, diagonal atau anti-diagonal seperti yang lain .

Contoh (jangan tampilkan benda dalam tanda kurung):

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

Biarkan saya tekankan bahwa input hanya valid, jika tidak ada ratu di baris, kolom, diagonal atau anti-diagonal yang sama dengan yang lain .

Aturan

• Anda tidak akan pernah menerima input kosong
• Jika input mengandung lebih sedikit ratu daripada akar kuadrat dari area papan, itu tidak valid.
• Perhatikan tidak ada solusi yang valid untuk papan 2x2 atau 3x3, tetapi ada solusi untuk setiap papan ukuran persegi lainnya, di mana lebar dan tinggi adalah bilangan alami.
• Input mungkin dalam format apa pun yang masuk akal, sesuai aturan PPCG
• Input akan selalu berupa sqaure
• Saya menggunakan 1 dan 0 dalam contoh, tetapi Anda dapat menggunakan nilai yang benar atau salah (seperti Why yes, sir, that is indeed the casedan Why no, sir, that is not the case)

Karena ini adalah kode-golf , kode terpendek menang!

Siput , 14 byte

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

Cobalah online!

Tidak ada yang seperti bahasa pencocokan pola 2D untuk masalah keputusan 2D. :)

Penjelasan

Pada &baris pertama adalah opsi mode pencocokan yang membutuhkan pola pada baris kedua untuk mencocokkan dari setiap posisi yang mungkin dalam input. Jika demikian, program akan mencetak 1, jika tidak maka akan dicetak 0.

Adapun pola itu sendiri, perhatikan bahwa ada yang tersirat )di akhir.

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

Mengapa ini bekerja paling mudah untuk dilihat dengan mulai dari lookahead negatif: dengan memastikan bahwa tidak ada Qdalam garis lurus dari yang lain yang Qtelah kami temukan, kami memastikan bahwa tidak ada lebih dari N ratu (jika tidak, akan ada menjadi dua dalam satu baris, dan tidak mungkin menemukan ratu ini tanpa menemukan yang lain). Kemudian bagian pertama, memastikan bahwa ada ratu yang dapat dijangkau dalam arah ortogonal dari posisi mana pun, memastikan bahwa ada ratu N yang tepat . Jika ada yang hilang, akan ada baris dan kolom tanpa ratu. Mulai dari persimpangan ini, tidak mungkin menemukan ratu hanya dengan pergi ke arah ortogonal.

Jelly , 17 atau 15 byte

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

Cobalah online!

Penggunaan ‘untuk seorang ratu dan ¹untuk ruang kosong. (Ini sebagian besar merupakan konsekuensi dari larangan mengambil input sebagai array, karena memaksa input menjadi string; mengubah string ke integer adalah sulit di Jelly, dengan metode termudah sedang dievaluasi, dan ternyata bukan 1 dan 0, menggunakan "tambah 1" ( ‘) dan "tambah 0" ( ¹) memungkinkan untuk menghilangkan beberapa jumlah dan instruksi peta, karena kita dapat menghitung ratu dalam daftar dengan mengevaluasinya.) Nilai-nilai kebenaran dan falsey adalah normal Jelly 1dan 0.

EDIT: Pertanyaannya sudah diubah sejak saya menulis jawaban ini untuk memungkinkan mengambil input sebagai matriks. Ini memungkinkan untuk menjatuhkan yang terdepan Ỵµ, menghemat 2 byte. Mungkin juga memungkinkan mengubah format input menjadi sesuatu yang lebih normal, menggunakan Spenjumlahan daripada Vuntuk mengevaluasi, tapi saya tidak berpikir bahwa menyimpan byte dan saya semacam format funky ini.

Penjelasan

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

Jadi ide dasarnya adalah kita memastikan bahwa paling banyak ada satu ratu pada setiap antidiagonal, diagonal, dan kolom; dan tepat satu ratu di setiap baris. Kondisi-kondisi ini cukup bersama sehingga membutuhkan paling banyak satu ratu pada masing-masing dari empat jenis garis, dan sejumlah ratu sama dengan panjang sisi papan.

Kebetulan, Jelly mungkin bisa melakukan dengan built-in untuk antidiagonals, tetapi AFAICT tampaknya tidak memilikinya, jadi saya perlu puas dengan memantulkan papan dan kemudian mengambil diagonal.

Catatan lain yang menarik adalah bahwa perubahan =1Ṃke E(semua sama) memberikan umum n -queens checker, yang juga akan menerima n × n papan di mana setiap baris, kolom, diagonal, dan antidiagonal mengandung tidak lebih dari k ratu, dan papan berisi persis kn queens. Membatasi k sama dengan 1 sebenarnya menghabiskan dua byte.

Oktaf, 57 70 67 51 52 byte

Disimpan 1 byte menggunakan flipbukan rot90berkat @LuisMendo, tetapi menemukan bug pada kasing 1x1

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

Mengambil input sebagai matriks biner dengan 1 mewakili Queen dan 0 mewakili ruang kosong.

Menciptakan fungsi anonim yang pertama kali menggabungkan matriks input dan transposinya.

spdiagsmenciptakan matriks dengan jumlah baris yang sama dengan argumen, dengan diagonal diubah menjadi kolom (nol-empuk seperlunya), jadi digabungkan spdiagsdari matriks input untuk mendapatkan diagonal dan spdiagsdari matriks membalik secara horizontal untuk mendapatkan antidiagonal.

Sekarang ambil jumlah dari setiap kolom dari matriks gabungan dan pastikan setiap kolom adalah tepat 1.

Sampel dijalankan ideone .

MATL , 38 34 byte

4 byte off berkat @ speaker !

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

Input adalah array 2D dari nol dan satu, menggunakan titik koma sebagai pemisah baris.

Ini menghasilkan vektor kolom yang benar, dan vektor kolom berisi setidaknya satu nol sebagai kepalsuan.

Cobalah online! Kode footer adalahif cabang untuk menunjukkan kebenaran atau kepalsuan.

Atau verifikasi semua kasus uji .

Penjelasan

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 byte

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

Fungsi kereta anonim yang mengambil matriks Boolean sebagai argumen.

Cobalah online!

( +/jumlah &dari ,ravel yang =sama #penghitungan baris)

* dan (kali lit.)

1satu =sama [:dengan >./maksimum

+/jumlah /.diagonal ,dan (lit. dikurangkan ke)

+/jumlah yang /.diagonal &dari |.sebaliknya ,dan

+/jumlah di ,dan

+/jumlah &dari |:transpos

SnakeEx , 67 byte

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

Digunakan _sebagai pengganti .input. Mengembalikan 1 atau lebih kecocokan untuk kebenaran, 0 kecocokan untuk falsey. Anda dapat menemukan juru bahasa online di tautan di tajuk.

Penjelasan

SnakeEx adalah bahasa dari tantangan Pencocokan Pola 2-D . Ini mendefinisikan "ular" yang bergerak di sekitar hal-hal yang cocok dengan kotak. Ular dapat memunculkan ular lain, membuat bahasanya cukup kuat.

Mari kita lihat program ini dari bawah ke atas.

n:_+$

Ini mendefinisikan ular nyang cocok dengan 1 atau lebih garis bawah dan kemudian tepi kisi. Perhatikan bahwa ini mungkin berada di salah satu dari 8 arah mata angin - arahnya ditentukan ketika ular itu melahirkan.

q:_*Q_*$

Mirip dengan di natas, ini mendefinisikan qsebagai ular yang cocok dengan sejumlah garis bawah, satu Q, sejumlah garis bawah, dan tepi grid. Dengan kata lain, baris / kolom / diagonal yang hanya memiliki satu ratu di dalamnya.

e:.$

e adalah ular yang cocok dengan satu karakter dan ujung kisi.

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

Ular utama m menggunakan blok bangunan ini untuk memeriksa seluruh papan. Secara konseptual, ia berjalan di sekitar tepi luar grid, menelurkan ular lain untuk memeriksa bahwa semua kolom dan baris memiliki tepat satu ratu, dan semua diagonal memiliki paling banyak satu ratu. Jika ada ular yang muncul gagal untuk mencocokkan, seluruh pertandingan gagal. Mari kita jabarkan.

• ( )%{4}menjalankan apa yang ada di dalam tanda kurung 4 kali, sekali untuk setiap sisi. (Dalam penjelasan berikut, sangat membantu untuk menggambarkan sisi tertentu - katakanlah, tepi atas kisi, mulai dari sudut kiri atas dan bergerak ke kanan.)
• {q<>}memunculkan qular ke arah yang sama bahwa ular utama bergerak. Ini memverifikasi bahwa tepi saat ini memenuhi aturan "tepat satu ratu". Perhatikan bahwa ular yang bertelur tidak menggerakkan pointer korek api ular utama, jadi kita masih berada di awal tepian.
• ( )* cocok dengan 0 atau lebih dari apa yang ada di dalam tanda kurung.
• {q<R>}memunculkan qular berbelok ke kanan dari arah ular utama. (Misalnya jika ular utama bergerak ke kanan di sepanjang tepi atas, ular ini bergerak ke bawah.) Ini memeriksa setiap kolom / baris.
• [ ] cocok dengan salah satu opsi di dalam kurung:
  • {q<RF>}memunculkan qular berbelok 45 derajat ke kanan (yaitu Right dan Forward) dari arah ular utama. The qular cocok jika diagonal yang berisi tepat satu Ratu.
  • {n<RF>}memunculkan nular sebagai gantinya. The nular cocok jika diagonal tidak mengandung ratu.
• . cocok dengan karakter apa pun, menggerakkan penunjuk pertandingan ke depan.
• Setelah memeriksa sebanyak mungkin horizontal dan diagonal, kami memverifikasi bahwa kami berada di ujung dengan pemijahan {e<>}.
• Akhirnya, <R>putar ular utama ke kanan, siap untuk mencocokkan tepi berikutnya.

Hal-hal aneh

• Tidak ada dalam program untuk memastikan bahwa pencocokan dimulai dari sudut luar. Bahkan, kasus uji kebenaran menghasilkan beberapa pertandingan, beberapa di antaranya dimulai dari dalam di suatu tempat. Meskipun demikian, tidak ada kasus palsu yang saya coba menghasilkan positif palsu.
• Jika saya membaca spec bahasa dengan benar, saya seharusnya bisa menggunakan X(cabang di semua arah diagonal) sebagai pengganti RF. Sayangnya, juru bahasa online mengatakan itu adalah kesalahan sintaksis. Saya juga mencoba *(bercabang ke segala arah), tapi itu tergantung juru bahasa.
• Secara teoritis, sesuatu seperti _*Q?_*$seharusnya bekerja untuk mencocokkan "paling banyak satu ratu" di diagonal, tetapi itu juga menggantung penerjemah. Dugaan saya adalah bahwa kemungkinan kecocokan kosong menyebabkan masalah.

Ruby, 120 byte

Fungsi Lambda berdasarkan spesifikasi asli yang membutuhkan input sebagai string.

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

mengubah Q menjadi bilangan kompleks dan menguranginya satu sama lain. Jika perbedaan antara koordinat dari dua ratu adalah horisontal, vertikal atau diagonal, menaikkannya ke daya 4 akan menghasilkan bilangan real dan pengaturan tidak valid.

Tidak digabungkan dalam program uji

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 byte

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

Cobalah online!

-32 byte terima kasih kepada @beaker yang memperhatikan perubahan spesifikasi input; Saya telah mengubah bahasa dari Python 3 menjadi 2, sehingga memungkinkan saya untuk menggunakan inputinput sebagai array string atau array array karakter.

-45 byte terima kasih kepada @Leaky Nun

JavaScript (ES6), 115 byte

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

Tidak Terkumpul:

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

Ruby, 155 byte

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

Ini mengerikan untuk dibaca, jadi saya punya versi yang sedikit kurang golf di bawah ini

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

Ini adalah kode yang sama, tetapi dengan beberapa baris baru untuk memisahkan apa yang terjadi.

Kode itu sendiri adalah fungsi lambda anonim yang mengambil larik string ( x) dalam format ["..Q", "Q..", ".Q."].

Baris pertama adalah memetakan setiap string ke indeks karakter Q dalam string itu. Jika tidak ada karakter Q, itu diganti dengan -2 ¹ . Array indeks baru ini ditugaskan ke variabel y.

Baris berikutnya ritsleting array indeks ini dengan dirinya sendiri diimbangi oleh satu (diputar). Ini menghasilkan array pasang indeks berurutan.

Baris berikutnya sangat rumit. Itu melewati masing-masing pasangan indeks, dan mengurangi yang lebih kecil dari yang lebih besar. Jika ini 1 (dan kami bukan pasangan terakhir ² ), maka ada dua ratu yang berada di diagonal yang sama, dan nilai -2 dimasukkan, jika tidak, indeks asli ratu dalam string dimasukkan .

Baris terakhir merangkum semua indeks untuk masing-masing dan memeriksa untuk melihat apakah itu adalah angka segitiga untuk n-1, di mana n adalah lebar (atau tinggi) dari bujur sangkar.

1: -1 akan menjadi tujuan saya, tetapi 1 terpisah dari 0, jadi akan berantakan dengan pemeriksaan diagonal. Negatifnya adalah penting untuk membuat jumlah akhir yang salah. Saya memikirkan angka tinggi (dengan angka tunggal) seperti 9, tetapi saya tidak yakin itu tidak akan menghasilkan verifikasi yang salah.
2: Papan tidak membungkus, sedangkan rotatefungsi array ruby tidak, dan jika pasangan terakhir berbeda satu sama lain tidak masalah - itu bukan diagonal.

PHP, 137 143 byte

terinspirasi oleh solusi 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;

mengambil input dari argumen baris perintah pertama; jalankan bersama -r. Membutuhkan jeda baris byte tunggal.
^{Sebenarnya Anda dapat menggunakan karakter apa pun kecuali 0untuk jeda baris.}
mencetak true ( 1) atau false (string kosong).

kerusakan

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 byte

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

Fungsi anonim mengambil daftar string sebagai input.

Python 2 , 175 byte

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