N-Queens II

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

Il backtracking è limitato da O(n!) : la prima riga ha n possibilità, la successiva al massimo n-1 e così via. I controlli delle diagonali riducono la ricerca ben al di sotto di questo limite, a 856,189 scacchiere parziali per n = 12 . Non è noto alcun metodo polinomiale per contare le soluzioni, quindi una ricerca come questa è la risposta standard. Lo spazio è O(n) .

Q: Come fai a capire su quale diagonale si trova un quadrato?

Spostarsi di un passo lungo una diagonale / aggiunge 1 alla riga e sottrae 1 alla colonna, quindi row + col non cambia mai. Spostarsi lungo una diagonale \ aggiunge 1 a entrambe, quindi row - col non cambia mai. Ogni somma identifica una diagonale e aggiungere n-1 alla differenza la trasforma in un indice di array da 0 a 2n-2 .

DifficileBacktracking

+10

Una regina su una scacchiera attacca ogni casella della propria riga, della propria colonna e di entrambe le diagonali, a qualsiasi distanza. Ti viene dato un intero n. Restituisci il numero di modi per disporre n regine su una scacchiera n × n in modo che nessuna coppia di regine si attacchi a vicenda.

Due disposizioni sono diverse quando una casella contiene una regina in una e nell'altra è vuota. Quindi una scacchiera e la sua immagine speculare contano come due disposizioni, anche se sembrano uguali.

Funzione

totalNQueens(n: integer) → integer

ninteger: la dimensione della scacchiera e il numero di regine
Restituisceinteger: il numero di modi per posizionare 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 la colonna della regina di ogni riga dall'alto verso il basso, le due scacchiere sono 1, 3, 0, 2 e 2, 0, 3, 1. Ognuna è l'immagine speculare dell'altra e contano come due soluzioni. Ogni altra scelta mette due regine sulla stessa colonna o diagonale.

+10 test nascosti all’invio

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Una disposizione è fissata scegliendo una colonna per ogni riga, poiché due regine sulla stessa riga si attaccano sempre a vicenda. Sono comunque n^n possibilità, circa 8.9 × 10^12 per n = 12, quindi non puoi elencarle tutte. Due idee risolvono il problema. Costruisci la scacchiera riga per riga e abbandona una scacchiera parziale non appena una regina viene attaccata, riducendo così la ricerca a meno di un milione di scacchiere parziali per n = 12. Inoltre, registra quali colonne e diagonali sono occupate, così per verificare una casella bastano tre consultazioni invece di esaminare tutte le regine collocate fino a quel momento.

Prova ogni disposizione con una regina per riga

Corretto, ma non termina sui test più grandi

Intuizione

Ogni riga deve contenere esattamente una regina, quindi una disposizione è una lista cols in cui cols[r] è la colonna della regina nella riga r. Ogni elemento può essere una qualsiasi delle n colonne, quindi ci sono n^n liste. Scorrile tutte come fa un contachilometri: aumenta di uno l’ultimo elemento e, quando supera n-1, reimpostalo a 0 e riporta l’incremento all’elemento precedente.

Per ogni lista, confronta ogni coppia di righe i < j. Le due regine si attaccano quando condividono una colonna, cols[i] == cols[j], oppure una diagonale. Su una diagonale, scendendo di una riga ci si sposta di una colonna a sinistra o a destra, quindi due regine condividono una diagonale esattamente quando la differenza tra le colonne è uguale alla differenza tra le righe: |cols[i] - cols[j]| == j - i. Una lista che supera tutti i confronti è una scacchiera valida. Poiché viene controllata ogni lista, non ne viene tralasciata nessuna e nessuna viene contata due volte.

È lento perché non si ferma mai in anticipo. Due regine sulla stessa diagonale nelle prime due righe rendono impossibile la scacchiera, eppure il contachilometri prova comunque tutti i n^(n-2) modi di riempire le altre righe. Per n = 8 sono 16,777,216 liste per trovare 92 scacchiere. Per n = 12 sono circa 8.9 × 10^12 liste. Anche impiegando un nanosecondo per lista, ci vogliono circa 2.5 ore.

Algoritmo

Inizia con cols tutti a zero: ogni regina nella colonna 0.
Controlla ogni coppia di righe i < j: la lista non è valida se cols[i] == cols[j] oppure |cols[i] - cols[j]| == j - i.
Se nessuna coppia è in conflitto, aggiungi 1 al conteggio.
Fai avanzare cols come un contachilometri: dall'ultima riga verso l'alto, reimposta a 0 ogni elemento che contiene n-1, poi aggiungi 1 al primo elemento che non lo contiene.
Quando ogni elemento era n-1, tutte le n^n liste sono state viste: restituisci il conteggio.

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

Disponi le regine riga per riga, dall’alto, e controlla ogni nuova regina nel momento in cui la posizioni. Se è sotto attacco, nessun modo di riempire le righe sottostanti può risolvere il problema, quindi salta subito la casella. Se è al sicuro, richiama ricorsivamente la riga successiva e, quando la chiamata restituisce il controllo, rimuovi la regina e prova la colonna successiva. Una chiamata che raggiunge la riga n ha posizionato n regine al sicuro e conta una scacchiera. Questo è il backtracking, e pota in modo aggressivo: per n = 12 visita 856,189 scacchiere parziali invece di 8.9 × 10^12 scacchiere complete.

L’altra metà consiste nel verificare velocemente una casella. Le righe sottostanti sono vuote e nella riga della nuova regina non ci sono altre regine, quindi solo tre linee possono attaccare la casella (row, c): la sua colonna, la sua diagonale / e la sua diagonale \. Tutte le caselle su una stessa diagonale / hanno lo stesso valore row + c, da 0 a 2n-2. Tutte le caselle su una stessa diagonale \ hanno lo stesso valore row - c, da -(n-1) a n-1, quindi aggiungi n-1 per ottenere un indice da 0 a 2n-2. Mantieni tre array di flag, cols di dimensione n e diag e anti di dimensione 2n-1. La casella è al sicuro esattamente quando tutti e tre i flag sono disattivati: tre ricerche, O(1), mentre confrontare la casella con ogni regina già posizionata costerebbe O(n).

Una linea può contenere al massimo una regina, quindi posizionare una regina attiva i suoi tre flag e rimuoverla li disattiva di nuovo, lasciando gli array esattamente com’erano. Sulla scacchiera di 4 per 4, una regina in (0, 0) imposta cols[0], diag[0] e anti[3]. Nella riga 1, la colonna 1 si trova su anti[3], quindi viene saltata senza controllare la regina stessa.

La prima riga offre n colonne, la seconda al massimo n-1 e così via, quindi la ricerca è limitata da O(n!), e le diagonali la riducono molto al di sotto di tale limite. Per n = 12 i cicli verificano in totale 10,103,868 caselle. La ricorsione ha una profondità di n chiamate e gli array contengono circa 5n flag, quindi lo spazio è O(n).

Algoritmo

Crea tre array di flag, tutti disattivati: cols con n elementi, diag e anti con 2n-1 elementi ciascuno.
Scrivi place(row). Se row == n, restituisci 1: ogni riga contiene una regina sicura.
Altrimenti, per ogni colonna c, saltala se cols[c], diag[row + c] o anti[row - c + n - 1] è attivo.
Per una colonna sicura, attiva i tre flag, aggiungi place(row + 1) al totale, quindi 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 insiemi è veloce, ma in ogni riga continua a testare tutte le n colonne, per la maggior parte attaccate. Una maschera di bit ti permette di passare direttamente a quelle libere. Fai corrispondere il bit c di un intero alla colonna c della riga che stai per riempire e mantieni tre maschere: cols, le colonne già occupate, left, le caselle di questa riga raggiunte lungo una direzione diagonale, e right, quelle raggiunte lungo l'altra.

Le caselle libere si ottengono quindi con un'unica espressione: free = ~(cols | left | right) & full, dove full ha impostati gli n bit meno significativi. free & -free isola la casella libera più a destra, e sottrarla permette di passare alla successiva. Quando metti una regina in bit e scendi di una riga, la sua colonna resta occupata, mentre ciascun attacco diagonale si sposta di una colonna. La riga successiva riceve quindi cols | bit, ((left | bit) << 1) & full e (right | bit) >> 1. Non c'è nulla da annullare: ogni chiamata ha i propri tre interi. Quando cols == full, tutte le n regine sono state posizionate.

Prendi n = 4 e una prima regina nella colonna 1, bit = 0010, scrivendo la colonna 0 come bit più a destra. La riga 1 riceve cols = 0010, left = 0100 e right = 0001, quindi free = 1000: la colonna 3 è l'unica scelta, individuata senza testare le colonne 0, 1 o 2.

La ricerca visita le stesse scacchiere parziali della versione con insiemi, ma ora ogni iterazione del ciclo posiziona una regina. Per n = 12, sono 856,188 passaggi invece di 10,103,868 test di caselle, con poche operazioni intere ciascuno. Il tempo resta limitato da O(n!) e la ricorsione raggiunge una profondità di n chiamate. Il codice R esegue le stesse maschere senza ricorsione: mantiene in un vettore tutte le scacchiere parziali di una riga e le espande tutte di una riga alla volta, quindi conserva in memoria un intero livello di scacchiere invece di n chiamate.

Algoritmo

Imposta full = (1 << n) - 1, la maschera di tutte le n colonne.
Scrivi 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

La ricerca in sé è breve. La maggior parte dei bug si trova nei calcoli delle diagonali e nel passaggio di annullamento.

Usare row - c come indice senza aggiungere n-1. In Java questo genera un errore, in C legge memoria fuori dall'array e in Python anti[-2] legge silenziosamente il flag di un'altra diagonale, quindi il conteggio risulta errato senza alcun errore.
Dimensionare gli array delle diagonali con n elementi. Una scacchiera n × n ha 2n-1 diagonali in ciascuna direzione.
Controllare solo una direzione delle diagonali o solo le colonne. Entrambe le direzioni delle diagonali consentono gli attacchi.
Dimenticare di disattivare i flag dopo che la chiamata ricorsiva è terminata. Ogni ramo successivo vede quindi regine che non sono più sulla scacchiera e il conteggio diminuisce.
Omettere & full nel calcolo di free. Anche ~x imposta tutti i bit oltre la colonna n-1, quindi il ciclo seleziona caselle fuori dalla scacchiera e, in Python o Ruby, i cui interi non hanno una larghezza fissa, free diventa negativo e il ciclo non termina mai.
Considerare le immagini speculari come un'unica scacchiera. Il problema le conta separatamente: n = 4 ha 2 scacchiere, che sono immagini speculari l'una dell'altra.
Gestire in modo errato i casi speciali delle scacchiere piccole. n = 1 ha 1 scacchiera, mentre n = 2 e n = 3 non ne hanno nessuna. La ricerca gestisce correttamente tutti e tre i casi senza casi speciali.

Domande frequenti4

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

Il backtracking è limitato da O(n!): la prima riga ha n possibilità, la successiva al massimo n-1 e così via. I controlli delle diagonali riducono la ricerca ben al di sotto di questo limite, a 856,189 scacchiere parziali per n = 12. Non è noto alcun metodo polinomiale per contare le soluzioni, quindi una ricerca come questa è la risposta standard. Lo spazio è O(n).

Come fai a capire su quale diagonale si trova un quadrato?

Spostarsi di un passo lungo una diagonale / aggiunge 1 alla riga e sottrae 1 alla colonna, quindi row + col non cambia mai. Spostarsi lungo una diagonale \ aggiunge 1 a entrambe, quindi row - col non cambia mai. Ogni somma identifica una diagonale e aggiungere n-1 alla differenza la trasforma in un indice di array da 0 a 2n-2.

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

N-Queens chiede tutte le scacchiere, rappresentate come righe di testo. N-Queens II chiede solo quante sono. La ricerca usa lo stesso backtracking, ma per contare non serve mantenere in memoria alcuna scacchiera: bastano gli insiemi delle colonne e delle diagonali, quindi è più veloce e leggero. È proprio questo che rende naturale usare qui la versione con maschera di bit.

Puoi usare la simmetria per velocizzare N-Queens II?

Sì. Riflettendo una scacchiera da sinistra a destra si ottiene un'altra scacchiera valida, quindi le scacchiere con la prima regina nella metà sinistra corrispondono a quelle con la prima regina nella metà destra. Conta le scacchiere in cui la prima regina si trova nelle colonne 0 a n/2 - 1 e raddoppia il risultato. Quando n è dispari, aggiungi una volta le scacchiere con la prima regina nella colonna centrale. In questo modo dimezzi la ricerca.

Python

def totalNQueens(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

n = 4

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 frequenti4

Problemi simili