N-Queens II

Q: Quelle est la complexité temporelle de N-Queens II ?

Le retour sur trace est borné par O(n!) : la première ligne offre n choix, la suivante au plus n-1 , et ainsi de suite. L’élagage réduit considérablement le travail réel, à 856,189 plateaux partiels pour n = 12 . L’espace est de O(n) .

DifficileRetour sur trace

+10

Une reine attaque toutes les cases de sa ligne, de sa colonne et de ses deux diagonales, quelle que soit leur distance. Étant donné un entier n, renvoie le nombre de façons de placer n reines sur un plateau de n × n de sorte qu’aucune paire de reines ne s’attaque.

Les plateaux qui diffèrent sur une case sont comptés séparément, y compris les images miroir.

Fonction

totalNQueens(n: integer) → integer

ninteger: la taille du plateau et le nombre de reines
Renvoieinteger: le nombre de façons de placer les reines de sorte qu’aucune n’en attaque une autre

Contraintes

1 ≤ n ≤ 12
La réponse pour n = 12 est 14,200, donc elle tient dans un entier 32 bits.

Exemples

Entrée: n = 4
Sortie: 2
Explication: En écrivant la colonne de la reine de chaque ligne de haut en bas, les échiquiers sont 1, 3, 0, 2 et 2, 0, 3, 1 : des images miroir, comptées comme deux solutions. Tout autre choix place deux reines dans une même colonne ou sur une même diagonale.

Pour aller plus loin

Peux-tu compter uniquement les échiquiers qui restent différents après avoir fait pivoter et reflété l’échiquier ? Pour n = 8, les 92 échiquiers se répartissent en 12 groupes de ce type.

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Deux reines sur une même ligne s’attaquent toujours, donc un plateau correspond à une colonne par ligne : n^n listes, soit environ 8.9 × 10^12 pour n = 12. Construis-le plutôt ligne par ligne, abandonne un plateau partiel dès qu’une reine est attaquée et marque les colonnes et diagonales occupées afin que tester une case ne nécessite que trois consultations.

Essayez chaque placement avec une reine par ligne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Écris un placement sous forme d’une liste cols, où figure la colonne de la reine de chaque ligne, puis parcours les n^n listes comme un compteur kilométrique. Les reines des lignes i < j s’attaquent lorsque cols[i] == cols[j] ou |cols[i] - cols[j]| == j - i, car une diagonale se déplace d’une colonne par ligne. Chaque liste est vérifiée une fois, donc aucun échiquier n’est oublié ni compté deux fois.

Rien n’interrompt le parcours prématurément : même un conflit dans les deux premières lignes laisse encore n^(n-2) listes à parcourir. Pour n = 8, cela représente 16,777,216 listes pour 92 échiquiers ; pour n = 12, 8.9 × 10^12, soit environ 2,5 heures à raison d’une nanoseconde chacune.

Algorithme

Commencez avec cols entièrement à zéro.
Ajoutez 1 au compteur si aucune paire de lignes i < j ne vérifie cols[i] == cols[j] ou |cols[i] - cols[j]| == j - i.
Avancez comme un compteur kilométrique : en partant de la dernière ligne et en remontant, remettez à 0 chaque entrée égale à n-1, puis ajoutez 1 à la première entrée inférieure à n-1.
Arrêtez-vous et renvoyez le compteur lorsque chaque entrée était 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

Retour arrière avec des ensembles de colonnes et de diagonales

Intuition

Place les reines ligne par ligne et vérifie chacune au moment où tu la places. Aucun remplissage des lignes inférieures ne peut sauver une reine attaquée, alors ignore cette case. Une reine en sécurité déclenche un appel récursif pour la ligne suivante et est retirée au retour de l’appel ; atteindre la ligne n compte un échiquier.

Seules trois lignes peuvent attaquer la case (row, c) : sa colonne, sa diagonale /, où row + c est constant, et sa diagonale \, où row - c est constant (ajoute n-1 pour l’indexer à partir de 0). Les tableaux d’indicateurs cols, diag et anti réduisent le test de sécurité à trois consultations. Chaque ligne contient au plus une reine, donc la remise à zéro des indicateurs au retour restaure exactement les tableaux.

La ligne k propose au plus n - k colonnes, la recherche est donc bornée par O(n!), avec un espace de O(n).

Algorithme

Crée des tableaux de drapeaux cols de taille n et diag et anti de taille 2n-1, tous désactivés.
place(row) : si row == n, retourne 1.
Pour chaque colonne c, ignore-la si cols[c], diag[row + c] ou anti[row - c + n - 1] est activé.
Sinon, active les trois drapeaux, ajoute place(row + 1) au total, puis désactive-les.
Retourne le total. La réponse est 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)

Retour sur trace avec des masques de bits

Intuition

La recherche avec indicateurs teste toujours les n colonnes de chaque ligne ; les masques de bits vont directement aux colonnes libres. Le bit c correspond à la colonne c de la ligne en cours de remplissage : cols contient les colonnes occupées, et left et right, les cases menacées le long de chaque diagonale. Ensuite, free = ~(cols | left | right) & full, où full représente les n bits de poids faible, et free & -free est la case libre la plus à gauche. À la ligne suivante, une colonne reste occupée et chaque attaque diagonale se décale d’une colonne.

Avec n = 4 et une première reine à bit = 0010, la ligne 1 obtient free = 1000 : la colonne 3, trouvée sans tester les autres. Pour n = 12, 856,188 étapes de boucle remplacent 10,103,868 tests de cases. Le code R construit toute une ligne de plateaux partiels à la fois, au lieu de recourir à la récursion.

Algorithme

Définissez full = (1 << n) - 1.
count(cols, left, right) : si cols == full, renvoyez 1.
Calculez free = ~(cols | left | right) & full.
Tant que free n’est pas égal à 0, prenez bit = free & -free, retirez-le de free et ajoutez count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1) au total.
Renvoyez le total. La réponse est 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)

Pièges et cas limites

Indexer anti avec row - c sans ajouter n-1. Java déclenche une exception, C lit en dehors du tableau et anti[-2] de Python lit discrètement le drapeau d’une autre diagonale.
Dimensionner les tableaux de diagonales à n au lieu de 2n-1. row + c atteint 2n-2.
Ne pas effacer les drapeaux après l’appel récursif. Les branches suivantes voient des reines qui ont disparu, et le décompte diminue.
Omettre & full de free. ~x définit les bits au-dessus de la colonne n-1, donc la boucle sélectionne des cases hors de l’échiquier ; en Python ou Ruby, free devient négatif et la boucle ne se termine jamais.

Questions fréquentes3

Quelle est la complexité temporelle de N-Queens II ?

Le retour sur trace est borné par O(n!) : la première ligne offre n choix, la suivante au plus n-1, et ainsi de suite. L’élagage réduit considérablement le travail réel, à 856,189 plateaux partiels pour n = 12. L’espace est de O(n).

Quelle est la différence entre N-Queens et N-Queens II ?

N-Queens renvoie chaque échiquier, représenté sous forme de lignes de texte ; N-Queens II renvoie uniquement leur nombre. La recherche est la même, mais le comptage ne stocke aucun échiquier, ce qui convient à la version utilisant un masque de bits.

Peux-tu utiliser la symétrie pour accélérer la résolution de N-Queens II ?

La réflexion d’un plateau de gauche à droite donne un autre plateau valide. Il suffit donc de compter les plateaux dont la première reine se trouve dans les colonnes 0 à n/2 - 1, puis de doubler ce nombre. Si n est impair, ajoute les plateaux dont la première reine se trouve dans la colonne du milieu une seule fois.

def totalNQueens(n):
    # Écrivez le code ici

Test #1

Test #2

Argument

n = 4

Résultat attendu

N-Queens II

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque placement avec une reine par ligne

Retour arrière avec des ensembles de colonnes et de diagonales

Retour sur trace avec des masques de bits

Pièges et cas limites

Questions fréquentes3

Problèmes similaires