Algoritmo del Problema de las 8 Reinas Explicado

El algoritmo del problema de las 8 reinas es un ejemplo clásico de retroceso en ciencias de la computación. Esta página explica el algoritmo paso a paso, proporciona código Python y visualiza el proceso de solución. Dominar este algoritmo te ayudará a comprender recursión, satisfacción de restricciones y estrategias de resolución de problemas.

¿Qué es el Problema de las 8 Reinas?

El problema de las 8 reinas pregunta: ¿Cómo puedes colocar ocho reinas en un tablero de ajedrez estándar de modo que ninguna se amenace entre sí? Esto significa que no comparten la misma fila, columna o diagonal. El problema es famoso por su solución elegante y se utiliza a menudo para enseñar pensamiento algorítmico.

Algoritmo Paso a Paso

1. Comienza con un tablero vacío.
2. Coloca una reina en la primera fila, primera columna.
3. Pasa a la siguiente fila e intenta colocar una reina en una columna segura (sin amenazas de las reinas anteriores).
4. Si encuentras un lugar seguro, coloca la reina y pasa a la siguiente fila.
5. Si no hay lugar seguro, retrocede a la fila anterior y mueve la reina a la siguiente columna disponible.
6. Repite hasta que las ocho reinas estén colocadas o se agoten todas las posibilidades.

Implementación en Python

def solve_nqueens(n):
    solutions = []
    board = []
    def is_safe(row, col):
        for r, c in enumerate(board):
            if c == col or abs(row - r) == abs(col - c):
                return False
        return True
    def backtrack(row=0):
        if row == n:
            solutions.append(list(board))
            return
        for col in range(n):
            if is_safe(row, col):
                board.append(col)
                backtrack(row + 1)
                board.pop()
    backtrack()
    return solutions

print(solve_nqueens(8))

Este código usa recursión y retroceso para encontrar todas las soluciones válidas al problema de las 8 reinas. Cada solución es una lista de índices de columna para cada fila.

Visualizando la Solución

Visualizar el proceso de retroceso ayuda a entender cómo el algoritmo explora posibilidades y retrocede cuando surgen conflictos. ¡Prueba nuestro juego interactivo de las 8 reinas para ver el algoritmo en acción!

Preguntas Frecuentes