NQueens package

Descripción general

El problema N-Queens es un desafío clásico que a menudo se encuentra en la programación de entrevistas y entornos académicos. El desafío es colocar n reinas en un tablero de ajedrez N × n de modo que no hay dos reinas amenazadas entre sí. Esto significa que no hay dos reinas pueden compartir la misma fila, columna o diagonal.

Declaración del problema

Dado un entero N, devuelva todas las soluciones distintas al rompecabezas N-Queens. Puede devolver las respuestas en cualquier orden.

Cada solución contiene una configuración de placa distinta de la colocación de N-Queens, donde 'Q' indica una reina y '. indica un espacio vacío.

Ejemplo

Para n = 4, las posibles soluciones son:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Enfoque y algoritmos

Algoritmo de retroceso

El enfoque más común para resolver el problema de N-Queens es usar retroceso. El algoritmo de retroceso crea incrementalmente candidatos a la solución y abandona a un candidato tan pronto como determina que el candidato no puede conducir a una solución válida.

Pasos:

1. Initialize the Board : comience con una placa N × N vacía.
2. Place the Queen : trate de colocar a la reina en la primera fila y proceda a colocar las reinas posteriores.
3. Check Validity : para cada colocación de la reina, verifique si entra en conflicto con las reinas ya colocadas.
4. Backtrack if Necessary : si colocar una reina no conduce a ninguna solución, retire la reina (retroceso) e intente la siguiente posición.
5. Store the Solution : si se encuentra una configuración válida (N Queens colocada), almacene la configuración de la placa.
6. Repeat : continúe este proceso hasta que se hayan probado todas las configuraciones posibles.

Desafíos

Representación de la junta

La placa se puede representar utilizando una lista 2D donde cada celda es 'Q' o '.'.

Verificación de conflictos

Verificar eficientemente los conflictos es crucial:

1. Row Check : Asegurar que no hay otras reinas en la misma fila.
2. Column Check : Asegurando que no hay otras reinas en la misma columna.
3. Diagonal Check : Asegurar que no hay otras reinas en la misma diagonal.

Mejoramiento

El uso de conjuntos para rastrear columnas y diagonales ocupadas puede acelerar el proceso de verificación de conflictos.

Concurrencia con threadpoolexecutor

Para optimizar la resolución del problema para N más grande, la solución aprovecha la concurrencia con ThreadPoolExecutor:

• Cada hilo comienza a resolver el problema para una columna diferente en la primera fila.
• Este enfoque paralelo puede reducir significativamente el tiempo para encontrar todas las soluciones.

Nuestra solución

Esta solución fue Frome uno de nuestros desafíos gratuitos del viernes , donde elegimos desafíos de entrevistas aleatorias durante nuestro tiempo de inactividad para escribir soluciones.

Instalación

 pip install wolfsoftware.NQueens

Uso

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

Resumen

El problema N-Queens es un desafío fascinante y complejo que requiere una comprensión profunda de las técnicas de recursión, retroceso y optimización. Al aprovechar el subproceso múltiple, esta implementación encuentra eficientemente todas las soluciones posibles para un tamaño de placa dado. Comprender e implementar el problema N-Queens es un ejercicio valioso para mejorar las habilidades de resolución de problemas y el pensamiento algorítmico.