Problema de N-Queens [cerrado]

9

En ajedrez, una reina puede moverse tanto como el tablero se extienda horizontal, vertical o diagonalmente.

Dado un tablero de ajedrez de tamaño NxN, imprima cuántas posiciones posibles se pueden colocar N reinas en el tablero y no podrán golpearse entre sí en 1 movimiento.

code-challenge combinatorics chess Dan McGrath
fuente
¿Necesitamos manejar 2 <= N <= 4 casos? ¿Si es así, cómo?
st0le
No hay solución para el caso: N = 2,3. La wikipedia tiene una excelente redacción sobre este clásico problema. Documenta muy bien sobre el número de solución de N = 1 a N = 14. (Todavía soy nuevo en Code Golf. No estoy seguro de cuál es la mejor manera de participar todavía. :))
Dongshengcn
A000170
Peter Taylor

Respuestas:

4

Aquí hay una solución (originalmente de esta entrada del blog ) donde construyo una descripción lógica de la solución en forma conjuntiva normal que luego resuelve 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

Aquí está la salida:

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
fuente
0

Rubí

No veo una golfetiqueta, así que supongo que es solo un desafío.

Aquí hay una implementación del Algoritmo mencionado en Wikipedia. No es por mí, está en Rosetta Stone y se puede encontrar aquí.

CommWikied esta respuesta.

st0le
fuente
0

Python 2, 190 185 caracteres

de itertools import *
n = input ()
print len ​​(filter (lambda x: all (1 ^ (y in (z, z + ij, z-i + j)) para i, y en enumerate (x) para j, z en enumerate (x [: i] + (1e9,) + x [i + 1:])), permutaciones (rango (1, n + 1), n)))

Simplemente asumí la etiqueta del código de golf a pesar de que no estaba allí. N se lee de stdin, el programa calcula soluciones hasta n = 10 en un tiempo aceptable.

cemper93
fuente
0

Maravilloso

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

Ofrece una lista de todas las soluciones de reina como esta:

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

Para representación gráfica agregue:

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

que se ve así: 

|_|Q|_|_|_|_|_|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|_|_|_|_|_|_|_|Q|
|_|_|Q|_|_|_|_|_|
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|_|Q|_|_|_|
Jonas Eicher
fuente