Masalah N-Queens [ditutup]

9

Dalam catur, seorang ratu dapat bergerak sejauh papan melebar secara horizontal, vertikal, atau diagonal.

Diberikan papan catur berukuran NxN, cetak berapa banyak posisi yang memungkinkan N que dapat ditempatkan di papan tulis dan tidak dapat saling pukul dalam satu gerakan.

code-challenge combinatorics chess Dan McGrath
sumber
Apakah kita perlu menangani 2 <= N <= 4 kasus? Kalau begitu bagaimana?
st0le
Tidak ada solusi untuk kasus: N = 2,3. Wikipedia memiliki penulisan yang sangat baik tentang masalah klasik ini. Ini mendokumentasikan dengan baik tentang nomor solusi dari N = 1 ke N = 14. (Saya masih baru untuk Code Golf. Belum yakin apa cara terbaik untuk berpartisipasi.))
Dongshengcn
A000170
Peter Taylor

Jawaban:

4

Inilah solusi (aslinya dari entri blog ini ) di mana saya membuat deskripsi logis tentang solusi dalam bentuk normal konjungtif yang kemudian dipecahkan oleh Mathematica:

(* Define the variables: Q[i,j] indicates whether there is a 
   Queen in row i, column j *)
Qs = Array[Q, {8, 8}];

(* Define the logical constraints. *)
problem =
  And[
   (* Each row must have a queen. *)
   And @@ Map[(Or @@ #) &, Qs],
   (* for all i,j: Q[i,j] implies Not[...] *)
   And @@ Flatten[
     Qs /. Q[i_, j_] :>
       And @@ Map[Implies[Q[i, j], Not[#]] &, 
         Cases[Qs, 
          Q[k_, l_] /;
           Not[(i == k) && (j == l)] && (
             (i == k) ||          (* same row *)
                 (j == l) ||          (* same column *)
             (i + j == k + l) ||  (* same / diagonal *)
             (i - j == k - l)),   (* same \ diagonal *)
          2]]]];

(* Find the solution *)
solution = FindInstance[problem, Flatten[Qs], Booleans] ;

(* Display the solution *)
Qs /. First[solution] /. {True -> Q, False -> x} // MatrixForm

Inilah hasilnya:

x   x   x   x   Q   x   x   x
x   Q   x   x   x   x   x   x
x   x   x   Q   x   x   x   x
x   x   x   x   x   x   Q   x
x   x   Q   x   x   x   x   x
x   x   x   x   x   x   x   Q
x   x   x   x   x   Q   x   x
Q   x   x   x   x   x   x   x
nibot
sumber
0

Rubi

Saya tidak melihat golftag, jadi saya menganggap itu hanya sebuah tantangan.

Berikut ini adalah implementasi dari Algoritma yang disebutkan di Wikipedia. Bukan oleh saya, itu di Rosetta Stone dan dapat ditemukan di sini

Buat Jawaban ini.

st0le
sumber
0

Python 2, 190 185 karakter

dari impor itertools *
n = input ()
print len ​​(filter (lambda x: all (1 ^ (y in (z, z + ij, z-i + j)) untuk i, y dalam penghitungan (x) untuk j, z dalam penghitungan (x [: i] + (1e9,) + x [i + 1:])), permutasi (rentang (1, n + 1), n))))

Saya hanya mengasumsikan tag kode golf meskipun tidak ada di sana. N dibaca dari stdin, program menghitung solusi hingga n = 10 dalam waktu yang dapat diterima.

cemper93
sumber
0

Asyik

n=8
s=(1..n).permutations().findAll{ 
  def x=0,y=0
  Set a=it.collect{it-x++} 
  Set b=it.collect{it+y++} 
  a.size()==it.size()&&b.size()==it.size() 
}

Memberikan daftar semua solusi ratu seperti ini:

[ [4, 7, 3, 0, 6, 1, 5, 2], 
  [6, 2, 7, 1, 4, 0, 5, 3], 
  ... ]

Untuk representasi grafis, tambahkan:

s.each { def size = it.size()
         it.each { (it-1).times { print "|_" }
                   print "|Q"
                   (size-it).times { print "|_" }
                   println "|"
                 }
         println ""
         }

yang terlihat seperti ini: 

|_|Q|_|_|_|_|_|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|_|_|_|_|_|_|_|Q|
|_|_|Q|_|_|_|_|_|
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|_|Q|_|_|_|
Jonas Eicher
sumber