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. La poda reduce el trabajo real mucho más, a 856,189 tableros parciales para n = 12 . El espacio es O(n) .

DifícilBacktracking

+10

Una reina ataca todas las casillas de su fila, su columna y ambas diagonales, por lejos que estén. Dado 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 entre sí.

Los tableros que difieran en cualquier casilla cuentan por separado, incluidas las imágenes especulares.

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 de modo 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 tableros son 1, 3, 0, 2 y 2, 0, 3, 1: imágenes especulares, contadas como dos. Cualquier otra elección coloca dos reinas en la misma columna o diagonal.

Para ir más allá

¿Puedes contar solo los tableros que siguen siendo distintos después de rotar y reflejar el tablero? Para n = 8, los 92 tableros se agrupan 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

Dos reinas en una misma fila siempre se atacan, así que el tablero tiene una columna por fila: n^n listas, aproximadamente 8.9 × 10^12 para n = 12. Constrúyelo fila por fila; en cuanto una reina sea atacada, descarta el tablero parcial y marca las columnas y diagonales ocupadas para que comprobar una casilla cueste tres consultas.

Prueba cada ubicación con una reina por fila

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

Intuición

Escribe una disposición como una lista cols, con la columna de la reina de cada fila, y recorre todas las listas n^n como si fuera un odómetro. Las reinas en las filas i < j se atacan cuando cols[i] == cols[j] o |cols[i] - cols[j]| == j - i, ya que una diagonal avanza una columna por fila. Cada lista se comprueba una vez, así que no se omite ni se cuenta dos veces ningún tablero.

Nada se detiene antes de tiempo: un conflicto en las dos primeras filas aún deja n^(n-2) listas. Para n = 8, eso significa 16,777,216 listas para 92 tableros; para n = 12, 8.9 × 10^12, unas 2.5 horas a un nanosegundo por lista.

Algoritmo

Empieza con cols todo en cero.
Suma 1 al contador si no hay ningún par de filas i < j para el que se cumpla cols[i] == cols[j] o |cols[i] - cols[j]| == j - i.
Avanza como un cuentakilómetros: desde la última fila hacia arriba, restablece a 0 cada entrada que esté en n-1 y luego suma 1 a la primera entrada que sea menor que n-1.
Detente y devuelve el contador cuando todas las entradas hayan sido n-1.

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 y prueba cada posición al colocarla. Ningún relleno de las filas inferiores puede salvar a una reina atacada, así que omite esa casilla. Una reina segura continúa recursivamente en la siguiente fila y se retira cuando la llamada retorna; llegar a la fila n cuenta como un tablero.

Solo tres líneas pueden atacar la casilla (row, c): su columna, su diagonal /, donde row + c es constante, y su diagonal \, donde row - c es constante (suma n-1 para indexarla desde 0). Los arreglos de indicadores cols, diag y anti convierten la prueba de seguridad en tres consultas. Cada línea contiene como máximo una reina, así que borrar los indicadores al retornar restaura los arreglos exactamente.

La fila k ofrece como máximo n - k columnas, por lo que la búsqueda está acotada por O(n!), con espacio O(n).

Algoritmo

Crea matrices de indicadores cols de tamaño n y diag y anti de tamaño 2n-1, todas apagadas.
place(row): si row == n, devuelve 1.
Para cada columna c, sáltala si cols[c], diag[row + c] o anti[row - c + n - 1] está encendida.
De lo contrario, enciende los tres indicadores, suma place(row + 1) al total y apágalos.
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 indicadores sigue probando las n columnas de cada fila; las máscaras de bits van directamente a las libres. El bit c es la columna c de la fila que se está completando: cols contiene las columnas ocupadas, y left y right, las casillas atacadas en cada diagonal. Después, free = ~(cols | left | right) & full, donde full son los n bits menos significativos, y free & -free es la casilla libre más baja. Una fila más abajo, una columna sigue ocupada y cada ataque diagonal se desplaza una columna.

Con n = 4 y una primera reina en bit = 0010, la fila 1 obtiene free = 1000: la columna 3, encontrada sin probar las demás. Para n = 12, 856,188 pasos de bucle reemplazan 10,103,868 pruebas de casillas. El código R genera de una vez una fila entera de tableros parciales, en lugar de recurrir.

Algoritmo

Establece full = (1 << n) - 1.
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

Indexar anti con row - c sin añadir n-1. Java lanza una excepción, C lee fuera del array y anti[-2] de Python lee silenciosamente la marca de otra diagonal.
Dimensionar los arrays de diagonales con n en lugar de 2n-1. row + c llega hasta 2n-2.
No borrar las marcas después de la llamada recursiva. Las ramas posteriores ven reinas que ya no están y el recuento disminuye.
Omitir & full de free. ~x activa los bits por encima de la columna n-1, así que el bucle selecciona casillas fuera del tablero; en Python o Ruby, free se vuelve negativo y el bucle nunca termina.

Preguntas frecuentes3

¿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. La poda reduce el trabajo real mucho más, a 856,189 tableros parciales para n = 12. El espacio es O(n).

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

N-Queens devuelve todos los tableros, representados como filas de texto; N-Queens II devuelve solo cuántos hay. La búsqueda es la misma, pero contar no almacena ningún tablero, lo que encaja con la versión de máscara de bits.

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

Reflejar un tablero de izquierda a derecha da otro tablero válido, así que cuenta los tableros cuya primera reina está en las columnas 0 a n/2 - 1 y duplica esa cantidad. Para n impar, añade una vez los tableros cuya primera reina está en la columna central.

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

Prueba #1

Prueba #2

Argumento

n = 4

Salida Esperada

N-Queens II

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada ubicación 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 frecuentes3

Problemas similares