Resolución del problema de las n reinas en ajedrez

N-Queens

El rompecabezas de n reinas es el problema de colocar n reinas en un tablero de ajedrez de n x n de manera que ninguna de ellas se ataque mutuamente. Dado un número entero n, devuelva todas las soluciones distintas del rompecabezas de n reinas. Puede devolver la respuesta en cualquier orden. Cada solución contiene una configuración del tablero distinta de la colocación de n reinas, donde "Q" y "." indican una reina y un espacio vacío, respectivamente.

Ejemplo 1:

Entrada: n = 4 Salida: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explicación: Existen dos soluciones distintas al rompecabezas de las 4 reinas como se muestra arriba

Solución

def solveNQueens(self, n: int) -> List[List[str]]:
       res = []
       self.dfs([-1]*n, 0, [], res)
       return res
 
def dfs(self, numeros, apuntador, construccionActual, res):
   if apuntador == len(numeros):
       res.append(construccionActual)
       return
   for i in range(len(numeros)):
       numeros[apuntador] = i
       if self.valid(numeros, apuntador):
           tmp = "."*len(numeros)
           self.dfs(numeros, apuntador+1, construccionActual+[tmp[:i]+"Q"+tmp[i+1:]], res)
 
def valid(self, numeros, apuntador):
   for i in range(apuntador):
       if abs(numeros[i]-numeros[apuntador]) == apuntador - i or numeros[i] == numeros[apuntador]:
           return False
   return True