N-Queens II

Q: ¿Cuál es la complejidad temporal de N-Queens II?

El retroceso está acotado por O(n!) : la primera fila tiene n opciones, la siguiente como máximo n-1 , y así sucesivamente. Las comprobaciones de diagonales podan mucho más que ese límite: se exploran 856,189 tableros parciales para n = 12 . No se conoce ningún método polinómico para contar las soluciones, así que una búsqueda como esta es la respuesta habitual. El espacio es O(n) .

Q: ¿Cómo puedes saber en qué diagonal está un cuadrado?

Avanzar un paso por una diagonal / suma 1 a la fila y resta 1 a la columna, así que row + col nunca cambia. Avanzar por una diagonal \ suma 1 a ambas, así que row - col nunca cambia. Cada suma identifica una diagonal, y sumar n-1 a la diferencia la convierte en un índice de array de 0 a 2n-2 .

DifícilBacktracking

+10

Una reina en un tablero de ajedrez ataca todas las casillas de su fila, de su columna y de sus dos diagonales, sin importar lo lejos que estén. Se te da un entero n. Devuelve el número de formas de colocar n reinas en un tablero de n × n de modo que ninguna pareja de reinas se ataque.

Dos formas son diferentes cuando en una de ellas alguna casilla tiene una reina y en la otra está vacía. Así que un tablero y su imagen especular cuentan como dos formas, aunque parezcan iguales.

Función

totalNQueens(n: integer) → integer

ninteger: el tamaño del tablero y el número de reinas
Devuelveinteger: el número de maneras de colocar las reinas para que ninguna ataque a otra

Restricciones

1 ≤ n ≤ 12
La respuesta para n = 12 es 14,200, así que cabe en un entero de 32 bits.

Ejemplos

Entrada: n = 4
Salida: 2
Explicación: Escribiendo la columna de la reina de cada fila de arriba abajo, los dos tableros son 1, 3, 0, 2 y 2, 0, 3, 1. Cada uno es la imagen especular del otro y cuentan como dos formas. Cualquier otra elección coloca dos reinas en la misma columna o diagonal.

+10 pruebas ocultas al enviar

Para ir más allá

¿Puedes contar solo los tableros que siguen siendo diferentes después de rotar y reflejar el tablero? Para n = 8, los 92 tableros se dividen en 12 grupos de este tipo.

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una disposición queda determinada al elegir una columna para cada fila, ya que dos reinas en una misma fila siempre se atacan entre sí. Aun así, hay n^n posibilidades, aproximadamente 8.9 × 10^12 para n = 12, así que no puedes enumerarlas todas. Dos ideas lo resuelven. Construye el tablero fila por fila y abandona un tablero parcial en cuanto ataquen a una reina; así se reduce la búsqueda a menos de un millón de tableros parciales para n = 12. Y registra qué columnas y diagonales están ocupadas, de modo que comprobar una casilla cueste tres consultas en lugar de recorrer todas las reinas colocadas hasta el momento.

Prueba todas las posiciones con una reina por fila

Correcto, pero no termina con las pruebas más grandes

Intuición

Cada fila debe contener exactamente una reina, por lo que una colocación es una lista cols donde cols[r] es la columna de la reina en la fila r. Cada entrada puede ser cualquiera de las n columnas, así que hay n^n listas. Recorre todas ellas como cuenta un cuentakilómetros: incrementa en uno la última entrada y, cuando pasa de n-1, restablécela a 0 y lleva uno a la entrada anterior.

Para cada lista, compara cada par de filas i < j. Las dos reinas se atacan entre sí cuando comparten una columna, cols[i] == cols[j], o una diagonal. En una diagonal, al bajar una fila te mueves una columna a la izquierda o a la derecha, así que dos reinas comparten una diagonal exactamente cuando la diferencia entre sus columnas es igual a la diferencia entre sus filas: |cols[i] - cols[j]| == j - i. Una lista que supera todas las comparaciones por pares es un tablero válido. Como se comprueba cada lista, no se omite ninguna ni se cuenta ninguna dos veces.

Es lento porque nunca se detiene antes de tiempo. Dos reinas en la misma diagonal en las dos primeras filas condenan el tablero, pero el cuentakilómetros sigue probando todas las n^(n-2) formas de llenar las demás filas. Para n = 8, eso supone 16,777,216 listas para encontrar 92 tableros. Para n = 12, son alrededor de 8.9 × 10^12 listas. Incluso a un nanosegundo por lista, eso supone unas 2.5 horas.

Algoritmo

Empieza con cols todo en ceros: cada reina en la columna 0.
Comprueba cada par de filas i < j: la lista no es válida si cols[i] == cols[j] o |cols[i] - cols[j]| == j - i.
Si ningún par entra en conflicto, suma 1 al contador.
Avanza cols como un cuentakilómetros: desde la última fila hacia arriba, restablece a 0 cada entrada que tenga n-1 y luego suma 1 a la primera entrada que no lo tenga.
Cuando todas las entradas hayan sido n-1, ya se habrán visto las n^n listas: devuelve el contador.

def totalNQueens(n):
    def is_valid(cols):
        # cols[r] is the column of the queen in row r, so rows never clash.
        for i in range(n):
            for j in range(i + 1, n):
                if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
                    return False
        return True

    cols = [0] * n
    count = 0
    while True:
        if is_valid(cols):
            count += 1
        # Move to the next placement, like an odometer with n digits in base n.
        row = n - 1
        while row >= 0 and cols[row] == n - 1:
            cols[row] = 0
            row -= 1
        if row < 0:
            return count
        cols[row] += 1

Retroceso con conjuntos de columnas y diagonales

Intuición

Coloca las reinas fila por fila, desde arriba, y comprueba cada nueva reina en cuanto la coloques. Si está amenazada, ninguna forma de llenar las filas de abajo puede solucionarlo, así que descarta esa casilla de inmediato. Si está a salvo, llama recursivamente a la siguiente fila y, cuando esa llamada regrese, retira la reina e intenta la siguiente columna. Una llamada que llega a la fila n ha colocado n reinas a salvo y cuenta un tablero. Esto es retroceso y poda mucho: para n = 12 visita 856,189 tableros parciales en vez de 8.9 × 10^12 tableros completos.

La otra mitad consiste en comprobar rápidamente una casilla. Las filas de abajo están vacías y en la propia fila de la nueva reina no hay ninguna otra reina, así que solo tres líneas pueden atacar la casilla (row, c): su columna, su diagonal / y su diagonal \. Todas las casillas de una misma diagonal / tienen el mismo valor de row + c, desde 0 hasta 2n-2. Todas las casillas de una misma diagonal \ tienen el mismo valor de row - c, desde -(n-1) hasta n-1, así que suma n-1 para obtener un índice de 0 a 2n-2. Mantén tres arreglos de indicadores: cols de tamaño n, y diag y anti de tamaño 2n-1. La casilla está a salvo exactamente cuando los tres indicadores están apagados: tres consultas, O(1), mientras que compararla con cada reina colocada hasta el momento costaría O(n).

Una línea puede contener como máximo una reina, así que al colocar una reina se activan sus tres indicadores y al retirarla se vuelven a desactivar, dejando los arreglos exactamente como estaban. En el tablero de 4 por 4, una reina en (0, 0) activa cols[0], diag[0] y anti[3]. En la fila 1, la columna 1 está en anti[3], así que se descarta sin tener que mirar a la reina misma.

La primera fila ofrece n columnas, la segunda como máximo n-1, y así sucesivamente, por lo que la búsqueda está acotada por O(n!), y las diagonales reducen muchísimo ese valor. Para n = 12, los bucles comprueban 10,103,868 casillas en total. La recursión tiene una profundidad de n llamadas y los arreglos contienen aproximadamente 5n indicadores, así que el espacio es O(n).

Algoritmo

Crea tres arreglos de banderas, todas apagadas: cols con n entradas, y diag y anti con 2n-1 entradas cada uno.
Escribe place(row). Si row == n, devuelve 1: cada fila tiene una reina que no está amenazada.
De lo contrario, para cada columna c, sáltala si cols[c], diag[row + c] o anti[row - c + n - 1] está activada.
Para una columna segura, activa las tres banderas, suma place(row + 1) al total y después desactívalas.
Devuelve el total. La respuesta es place(0).

def totalNQueens(n):
    cols = [False] * n             # cols[c]: column c holds a queen
    diag = [False] * (2 * n - 1)   # diag[r + c]: that / diagonal holds a queen
    anti = [False] * (2 * n - 1)   # anti[r - c + n - 1]: that \ diagonal holds a queen

    def place(row):
        if row == n:
            return 1  # a queen in every row: one complete board
        count = 0
        for c in range(n):
            if cols[c] or diag[row + c] or anti[row - c + n - 1]:
                continue  # attacked: three lookups, no scan of the board
            cols[c] = diag[row + c] = anti[row - c + n - 1] = True
            count += place(row + 1)
            cols[c] = diag[row + c] = anti[row - c + n - 1] = False  # take it back
        return count

    return place(0)

Retroceso con máscaras de bits

Intuición

La búsqueda con conjuntos es rápida, pero en cada fila sigue comprobando las n columnas, la mayoría de las cuales están atacadas. Una máscara de bits permite ir directamente a las casillas libres. Haz que el bit c de un entero represente la columna c de la fila que estás a punto de rellenar y mantén tres máscaras: cols, las columnas ya ocupadas; left, las casillas de esta fila atacadas a lo largo de una dirección diagonal; y right, las atacadas a lo largo de la otra.

Las casillas libres se obtienen con una sola expresión: free = ~(cols | left | right) & full, donde full tiene establecidos los n bits inferiores. free & -free aísla la casilla libre de menor valor, y restarla permite pasar a la siguiente. Cuando colocas una reina en bit y bajas una fila, su columna sigue ocupada, mientras que cada ataque diagonal se desplaza una columna. Así que la fila siguiente recibe cols | bit, ((left | bit) << 1) & full y (right | bit) >> 1. No hay nada que deshacer: cada llamada obtiene sus propios tres enteros. Cuando cols == full, las n reinas están colocadas.

Tomemos n = 4 y una primera reina en la columna 1, bit = 0010, escribiendo la columna 0 como el bit situado más a la derecha. La fila 1 recibe cols = 0010, left = 0100 y right = 0001, así que free = 1000: la columna 3 es la única opción, encontrada sin comprobar las columnas 0, 1 o 2.

La búsqueda visita los mismos tableros parciales que la versión con conjuntos, pero ahora cada paso del bucle coloca una reina. Para n = 12, eso supone 856,188 pasos en lugar de 10,103,868 comprobaciones de casillas, con unas pocas operaciones con enteros en cada uno. El tiempo sigue estando acotado por O(n!), y la recursión tiene una profundidad de n llamadas. El código de R ejecuta las mismas máscaras sin recursión: mantiene en un vector todos los tableros parciales de una fila y los amplía todos, una fila a la vez, por lo que guarda en memoria un nivel completo de tableros en lugar de n llamadas.

Algoritmo

Establece full = (1 << n) - 1, la máscara de todas las n columnas.
Escribe count(cols, left, right). Si cols == full, devuelve 1.
Calcula free = ~(cols | left | right) & full.
Mientras free no sea 0, toma bit = free & -free, elimínalo de free y suma count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) al total.
Devuelve el total. La respuesta es count(0, 0, 0).

def totalNQueens(n):
    full = (1 << n) - 1  # bit c stands for column c of the current row

    def count(cols, left, right):
        # cols: columns taken. left, right: squares of this row hit along a diagonal.
        if cols == full:
            return 1  # every column used: n queens placed
        total = 0
        free = full & ~(cols | left | right)
        while free:
            bit = free & -free  # the lowest free square
            free -= bit
            # Moving down a row shifts each diagonal attack one column over.
            total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
        return total

    return count(0, 0, 0)

Errores comunes y casos límite

La búsqueda en sí es corta. La mayoría de los errores están en la aritmética de las diagonales y en el paso de deshacer.

Usar row - c como índice sin sumar n-1. En Java eso produce una excepción; en C, lee memoria fuera del arreglo; y en Python, anti[-2] lee silenciosamente la bandera de otra diagonal, por lo que el conteo es incorrecto y no se produce ningún error.
Dimensionar los arreglos de diagonales con n entradas. Un tablero de n × n tiene 2n-1 diagonales en cada dirección.
Comprobar solo una dirección de las diagonales, o solo las columnas. Ambas direcciones de las diagonales atacan.
Olvidar desactivar las banderas después de que retorna la llamada recursiva. Todas las ramas posteriores ven entonces reinas que ya no están en el tablero, y el conteo disminuye.
Omitir & full al calcular free. ~x también activa todos los bits por encima de la columna n-1, así que el bucle selecciona casillas fuera del tablero y, en Python o Ruby, cuyos enteros no tienen un ancho fijo, free se vuelve negativo y el bucle nunca termina.
Tratar las imágenes especulares como un solo tablero. El problema las cuenta por separado: n = 4 tiene 2 tableros, y son imágenes especulares uno del otro.
Tratar incorrectamente los tableros pequeños con casos especiales. n = 1 tiene 1 tablero, mientras que n = 2 y n = 3 no tienen ninguno. La búsqueda resuelve correctamente los tres casos sin ningún caso especial.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de N-Queens II?

El retroceso está acotado por O(n!): la primera fila tiene n opciones, la siguiente como máximo n-1, y así sucesivamente. Las comprobaciones de diagonales podan mucho más que ese límite: se exploran 856,189 tableros parciales para n = 12. No se conoce ningún método polinómico para contar las soluciones, así que una búsqueda como esta es la respuesta habitual. El espacio es O(n).

¿Cómo puedes saber en qué diagonal está un cuadrado?

Avanzar un paso por una diagonal / suma 1 a la fila y resta 1 a la columna, así que row + col nunca cambia. Avanzar por una diagonal \ suma 1 a ambas, así que row - col nunca cambia. Cada suma identifica una diagonal, y sumar n-1 a la diferencia la convierte en un índice de array de 0 a 2n-2.

¿Cuál es la diferencia entre N-Queens y N-Queens II?

N-Queens pide todos los tableros, representados como filas de texto. N-Queens II solo pregunta cuántos hay. La búsqueda utiliza el mismo retroceso, pero para contar no hace falta guardar ningún tablero en memoria, solo los conjuntos de columnas y diagonales, así que es más rápida y ligera. Eso también hace que la versión con máscara de bits resulte natural en este caso.

¿Puedes usar la simetría para acelerar N-Queens II?

Sí. Reflejar un tablero de izquierda a derecha produce otro tablero válido, así que los tableros cuya primera reina está en la mitad izquierda coinciden con los que la tienen en la mitad derecha. Cuenta los tableros cuya primera reina está en las columnas 0 a n/2 - 1 y duplica esa cantidad. Cuando n es impar, suma una vez los tableros cuya primera reina está en la columna central. Así reduces a la mitad la búsqueda.

Python

def totalNQueens(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

n = 4

Esperado

N-Queens II

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba todas las posiciones con una reina por fila

Retroceso con conjuntos de columnas y diagonales

Retroceso con máscaras de bits

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares