Problema de las 8 reinas en Python 3 con backtracking

Solución al clásico problema de las 8 reinas en Python 3 usando backtracking. El algoritmo coloca una reina por fila y descarta ramas inválidas antes de continuar, lo que lo hace mucho más eficiente que la fuerza bruta. Encuentra las 92 soluciones distintas e imprime un tablero ASCII para cada una. Fácilmente adaptable a tableros de N×N.

				"""

El problema de las 8 reinas — Python 3 con backtracking



Consiste en colocar 8 reinas en un tablero de ajedrez 8×8 de modo que

ninguna ataque a otra. Una reina ataca en horizontal, vertical y diagonal.



Hay exactamente 92 soluciones distintas para N=8.

El algoritmo usa backtracking: coloca una reina por fila e intenta todas

las columnas posibles, descartando las que generan conflictos antes de

continuar. Esto evita explorar millones de combinaciones inválidas.



Código mejorado por David Carrero — https://carrero.es

Fecha de modificación: 2026-05-09

"""





def resolver(n: int = 8) -> list[list[int]]:

    """

    Devuelve todas las soluciones para el problema de las N reinas.

    Cada solución es una lista donde solución[fila] = columna.

    """

    soluciones: list[list[int]] = []

    tablero    = [-1] * n           # tablero[fila] = columna de la reina



    def es_seguro(fila: int, col: int) -> bool:

        """Comprueba que no haya conflicto con las reinas ya colocadas."""

        for f in range(fila):

            c = tablero[f]

            if c == col or abs(c - col) == abs(f - fila):

                return False        # misma columna o misma diagonal

        return True



    def backtrack(fila: int) -> None:

        if fila == n:

            soluciones.append(tablero[:])

            return

        for col in range(n):

            if es_seguro(fila, col):

                tablero[fila] = col

                backtrack(fila + 1)

                tablero[fila] = -1  # deshacer



    backtrack(0)

    return soluciones





def dibujar(solucion: list[int]) -> str:

    """Dibuja un tablero ASCII con la solución."""

    n = len(solucion)

    lineas = []

    borde  = '  +' + ('---+' * n)

    lineas.append(borde)

    for fila, col_reina in enumerate(solucion):

        fila_str = f'{n - fila} |'

        for col in range(n):

            fila_str += ' Q |' if col == col_reina else ' . |'

        lineas.append(fila_str)

        lineas.append(borde)

    cols  = '   ' + ''.join(f' {chr(65 + c)}  ' for c in range(n))

    lineas.append(cols)

    return 'n'.join(lineas)





# ?? Programa principal ????????????????????????????????????????????????????????



N = 8

soluciones = resolver(N)



print(f'Problema de las {N} reinas')

print(f'Soluciones encontradas: {len(soluciones)}n')



# Mostrar las 3 primeras y la última

mostrar = soluciones[:3] + [soluciones[-1]]

etiquetas = [f'Solución #{i+1}' for i in range(3)] + [f'Solución #{len(soluciones)}']



for etiqueta, sol in zip(etiquetas, mostrar):

    print(f'?? {etiqueta} ??')

    print(f'   Columnas por fila: {sol}')

    print(dibujar(sol))

    print()