N-Queens II

Q: Qual è la complessità temporale di N-Queens II?

Il backtracking è limitato da O(n!) : la prima riga ha n scelte, la successiva al massimo n-1 e così via. Il pruning riduce il lavoro effettivo a un valore molto più basso, pari a 856,189 scacchiere parziali per n = 12 . Lo spazio è O(n) .

DifficileBacktracking

+10

Una regina attacca ogni casella della sua riga, della sua colonna e di entrambe le diagonali, per quanto lontane. Dato un numero intero n, restituisci il numero di modi per posizionare n regine su una scacchiera di n × n in modo che nessuna coppia di regine si attacchi a vicenda.

Le scacchiere che differiscono anche solo per una casella si contano separatamente, comprese le immagini speculari.

Funzione

totalNQueens(n: integer) → integer

ninteger: la dimensione della scacchiera e il numero di regine
Restituisceinteger: il numero di modi per disporre le regine in modo che nessuna ne attacchi un'altra

Vincoli

1 ≤ n ≤ 12
La risposta per n = 12 è 14.200, quindi rientra in un intero a 32 bit.

Esempi

Input: n = 4
Output: 2
Spiegazione: Scrivendo dall’alto verso il basso la colonna della regina in ogni riga, le scacchiere sono 1, 3, 0, 2 e 2, 0, 3, 1: immagini speculari, contate come due. Ogni altra scelta colloca due regine sulla stessa colonna o diagonale.

Per approfondire

Riesci a contare solo le scacchiere che restano diverse dopo aver ruotato e specchiato la scacchiera? Per n = 8, le 92 scacchiere si suddividono in 12 gruppi di questo tipo.

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Due regine nella stessa riga si attaccano sempre, quindi la scacchiera è una colonna per riga: n^n elenchi, circa 8.9 × 10^12 per n = 12. Costruiscila invece riga per riga, scarta una scacchiera parziale non appena una regina viene attaccata e contrassegna le colonne e le diagonali occupate, così verificare una casella costa tre ricerche.

Prova ogni disposizione con una regina per riga

Corretto, ma non termina sui test più grandi

Intuizione

Rappresenta una disposizione come un elenco cols, con la colonna della regina di ogni riga, e scorri tutti gli n^n elenchi come un contachilometri. Le regine nelle righe i < j si attaccano quando cols[i] == cols[j] oppure |cols[i] - cols[j]| == j - i, poiché una diagonale si sposta di una colonna per riga. Ogni elenco viene controllato una volta, quindi nessuna scacchiera viene tralasciata o contata due volte.

Nulla interrompe la ricerca in anticipo: anche uno scontro nelle prime due righe lascia n^(n-2) elenchi. Per n = 8 sono 16,777,216 elenchi per 92 scacchiere; per n = 12, 8.9 × 10^12, circa 2.5 ore a un nanosecondo ciascuno.

Algoritmo

Inizia con cols tutti a zero.
Aggiungi 1 al conteggio se nessuna coppia di righe i < j ha cols[i] == cols[j] o |cols[i] - cols[j]| == j - i.
Procedi come un contachilometri: dall'ultima riga verso l'alto, reimposta a 0 ogni voce uguale a n-1, poi aggiungi 1 alla prima voce inferiore a n-1.
Interrompi e restituisci il conteggio quando tutte le voci erano 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

Backtracking con insiemi di colonne e diagonali

Intuizione

Posiziona le regine riga per riga e verifica ciascuna mentre la posizioni. Riempire le righe sottostanti non può salvare una regina sotto attacco, quindi salta quella casella. Una regina al sicuro ricorre alla riga successiva e viene rimossa quando la chiamata restituisce il controllo; raggiungere la riga n conta come una scacchiera.

Solo tre linee possono attaccare la casella (row, c): la sua colonna, la diagonale /, dove row + c è costante, e la diagonale \, dove row - c è costante (aggiungi n-1 per indicizzarla a partire da 0). Gli array di flag cols, diag e anti riducono il test di sicurezza a tre accessi. Ogni linea contiene al massimo una regina, quindi azzerare i flag al ritorno ripristina esattamente gli array.

La riga k offre al massimo n - k colonne, quindi la ricerca è limitata da O(n!), con spazio O(n).

Algoritmo

Crea gli array di flag cols di dimensione n e diag e anti di dimensione 2n-1, tutti disattivati.
place(row): se row == n, restituisci 1.
Per ogni colonna c, saltala se cols[c], diag[row + c] o anti[row - c + n - 1] è attivo.
Altrimenti attiva i tre flag, aggiungi place(row + 1) al totale e disattivali.
Restituisci il totale. La risposta è 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)

Backtracking con maschere di bit

Intuizione

La ricerca con flag continua a testare tutte le n colonne di ogni riga; le maschere di bit passano direttamente a quelle libere. Il bit c è la colonna c della riga da riempire: cols contiene le colonne occupate, mentre left e right le caselle minacciate lungo ciascuna diagonale. Quindi free = ~(cols | left | right) & full, dove full contiene i n bit meno significativi, e free & -free è la casella libera più a sinistra. Una riga più in basso, una colonna resta occupata e ogni attacco diagonale si sposta di una colonna.

Con n = 4 e una prima regina in bit = 0010, la riga 1 ottiene free = 1000: la colonna 3, trovata senza testare le altre. Per n = 12, 856,188 iterazioni del ciclo sostituiscono 10,103,868 test delle caselle. Il codice R crea in una volta un'intera riga di scacchiere parziali invece di ricorrere.

Algoritmo

Imposta full = (1 << n) - 1.
count(cols, left, right): se cols == full, restituisci 1.
Calcola free = ~(cols | left | right) & full.
Finché free non è 0, prendi bit = free & -free, rimuovilo da free e aggiungi count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) al totale.
Restituisci il totale. La risposta è 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)

Trappole e casi limite

Indicizzare anti con row - c senza aggiungere n-1. Java genera un'eccezione, C legge fuori dall'array e anti[-2] di Python legge silenziosamente il flag di un'altra diagonale.
Dimensionare gli array delle diagonali a n invece che a 2n-1. row + c arriva a 2n-2.
Non azzerare i flag dopo la chiamata ricorsiva. I rami successivi vedono regine che non ci sono più e il conteggio diminuisce.
Omettere & full da free. ~x imposta i bit oltre la colonna n-1, quindi il ciclo seleziona caselle fuori dalla scacchiera; in Python o Ruby, free diventa negativo e il ciclo non termina mai.

Domande frequenti3

Qual è la complessità temporale di N-Queens II?

Il backtracking è limitato da O(n!): la prima riga ha n scelte, la successiva al massimo n-1 e così via. Il pruning riduce il lavoro effettivo a un valore molto più basso, pari a 856,189 scacchiere parziali per n = 12. Lo spazio è O(n).

Qual è la differenza tra N-Queens e N-Queens II?

N-Queens restituisce ogni scacchiera, rappresentata come righe di testo; N-Queens II restituisce solo quante sono. La ricerca è la stessa, ma il conteggio non memorizza alcuna scacchiera, il che si adatta alla versione con maschera di bit.

Puoi usare la simmetria per velocizzare N-Queens II?

Riflettere una scacchiera da sinistra a destra dà un’altra scacchiera valida, quindi conta le scacchiere in cui la prima regina si trova nelle colonne da 0 a n/2 - 1 e raddoppia il risultato. Se n è dispari, aggiungi una volta le scacchiere in cui la prima regina si trova nella colonna centrale.

def totalNQueens(n):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

n = 4

Output atteso

N-Queens II

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni disposizione con una regina per riga

Backtracking con insiemi di colonne e diagonali

Backtracking con maschere di bit

Trappole e casi limite

Domande frequenti3

Problemi simili