En el juego de ajedrez, hay una pieza llamada reina que puede atacar a cualquier otra pieza que esté en la misma fila, columna o diagonal. En el ajedrez, generalmente hay dos lados, blanco y negro, y cada pieza pertenece a uno de los equipos. Las piezas no pueden atacar piezas que pertenecen al mismo equipo.
Tu objetivo es descubrir los ejércitos pacíficos más grandes y coexistentes para un tablero cuadrado. Esa es la mayor cantidad de reinas en blanco y negro que pueden caber en el tablero, de modo que no hay dos reinas que puedan atacarse entre sí y la cantidad de reinas negras es igual a la cantidad de reinas blancas.
Recibirá como entrada la longitud lateral de un tablero cuadrado, y debería generar el número de tamaño de los ejércitos coexistentes pacíficos más grandes que pueden caber en ese tablero.
Este es el código de golf, por lo que se aplican las reglas estándar para la etiqueta.
Estos casos de prueba abarcan todas las respuestas conocidas. Su solución debe ser una respuesta generalizada que, dada la potencia y el tiempo de cálculo suficientes, pueda calcular la solución para cualquier valor de entrada.
1: 0 2: 0 3: 1 4: 2 5: 4 sesenta y cinco 7: 7 8: 9 9: 12 10: 14 11: 17 12: 21 13: 24
Respuestas:
C, 476 bytes, reinas blancas iterativas DFS, O (2 n 2 )
518 bytes, DFS con poda, O (2 n )
577 bytes, DFS iterando reinas blancas y negras, O (?)
Básicamente, el código itera sobre las posibilidades de la reina blanca y verifica si la reina negra se puede colocar en ese momento.
Tabla de referencia de velocidad (en segundos):
fuente
Clingo , 90 bytes
Manifestación
fuente
Python 2 |
325284217 bytesPruébalo en línea!
Editar: tuplas reemplazadas con enteros en gy otras ediciones triviales.
Edit2: ¡ Bytes hasta 217 gracias a musicman523 y CalculatorFeline !
Cómo funciona
El programa itera sobre todas las posiciones posibles de las
nreinas y filtra los puntos no pacíficosgcausados debido a la posición de las reinas. Si los puntos restantes son mayores queneso, significa que es posible que losnejércitos reina permanezcan en paz. Si para el siguiente valor den, no se encuentra una situación pacífica, entonces el programa sale con el código de salida:n-1que es la respuesta. En resumen, es fuerza brutaEl programa se puede hacer más rápido cambiando las dos últimas líneas a
fuente
from module import*para importar todo desde un módulo y guardar bytes.Haskell ,
169156153152bytesDefine una función
g, puede ser más golfable. Pruébalo en línea! En TIO, cuando se compila-O2, esto lleva unos 36 segundos para n = 4 y el tiempo de espera en n = 5 . La complejidad del tiempo debe ser O (n 2 4 n 2 ) .Explicación
Repetimos los valores posibles para el número de reinas ( q ). Para cada q , generamos todos los pares de subconjuntos de tamaño- q de [1..n] 2 , un conjunto de reinas negras ( b ) y una de reinas blancas ( w ). Luego, cada elemento de b se compara con cada elemento de w para ver si comparten una fila, una columna, una diagonal o una anti-diagonal. Esto también se encarga de dos piezas que comparten la misma coordenada. El mayor valor de q que admite una configuración pacífica es el valor final.
Las dos primeras líneas del programa definen la función
!, que calcula lasksubsecuencias de longitud de una listax. La implementación es por una recursión básica: elija el primer elemento para estar en el conjunto o no y recurra a la cola, disminuyendoksi es necesario. Luego la lista vacía o alcanzada, verifique esok==0.La segunda función auxiliar
&toma un númeroq(número de reinas en cada lado) y una listal(las coordenadas x del tablero, también utilizadas como coordenadas y), y devuelve un valor booleano que indica si existe una configuración pacífica. Primero calculamospla lista deqsubsecuencias de longitud de la lista de valores[x,y,x-y,x+y], dóndexyyrangol. Representan la fila, columna, diagonal y anti-diagonal de un cuadrado(x,y)en el tablero.A continuación tenemos el resultado de
q&l. Dibujamos dos subsecuenciasby , awpartir de ellasp, emparejamos las 4 listas de ellas de todas las formas posibles y verificamos que siempre difieran en las 4 coordenadas. Si algunas eleccionesbywresultan en un resultado verdadero, regresamosTrue.La última línea es la función principal. Dado
n, simplemente encuentra el mayor valor posibleqpara el cualq&[1..n]es verdadero.fuente