Recientemente, estaba investigando mis desarrollos / scripts antiguos y encontré un script donde se resolvió el problema de las reinas. De hecho, esto sirvió para escribir un artículo sobre cómo fueron las etapas de redacción de su algoritmo. Quizás sea útil para que los programadores novatos resuelvan problemas similares (el código de los ejemplos está escrito en Java).
Introducción
Hace 4 años hubo un gran revuelo sobre el problema de colocar 1000 reinas en un tablero de 1000x1000. El caso es que colocar reinas de forma que no estén
entre sí en el tablero es un problema con un gran número de iteraciones y, por tanto, un tiempo de ejecución largo. Como muchos otros, quería comprobar si se podía solucionar en un tiempo aceptable.
Estudia la tarea
Hay 8 reinas en la imagen que no se cruzan a lo largo de líneas horizontales, verticales o diagonales.
Es necesario escribir un guión que coloque a las reinas en el tablero de acuerdo con estas reglas.
Algoritmo para encontrar reinas
Se eligió la recursividad para buscar formas.
Descripción del método que se llama a sí mismo:
Si la celda pasada se cruza con otras figuras, regresamos
false
Si la celda transferida no se cruza con nadie:
true
.
( )
true
.
.
false
false
)false
.
true
.
8x8, 32x32, 50x50 . .
.
.
.
. .
.
400x400.
.
.
.
.
.
"row+1" "column+2" , .
1000x1000 ~4 ( : Intel Core i5-10400H CPU 2.60GHz).
1116x1116 ~6 .