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 a n choix, la suivante au plus n-1 , et ainsi de suite. Les vérifications des diagonales élaguent la recherche bien en dessous de cette borne, jusqu’à 856,189 échiquiers partiels pour n = 12 . Aucune méthode polynomiale n’est connue pour compter les solutions ; une recherche comme celle-ci est donc la réponse standard. L’espace est de O(n) .

Q: Comment savoir sur quelle diagonale se trouve un carré ?

Se déplacer d’un pas le long d’une diagonale / ajoute 1 à la ligne et soustrait 1 à la colonne, donc row + col ne change jamais. Se déplacer le long d’une diagonale \ ajoute 1 aux deux, donc row - col ne change jamais. Chaque somme désigne une diagonale, et ajouter n-1 à la différence la transforme en un indice de tableau allant de 0 à 2n-2 .

DifficileRetour sur trace

+10

Une reine sur un échiquier attaque toutes les cases de sa rangée, de sa colonne et de ses deux diagonales, quelle que soit leur distance. On vous donne un entier n. Renvoyez 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.

Deux façons sont différentes si une case contient une reine dans l’une et est vide dans l’autre. Ainsi, un plateau et son image miroir comptent comme deux façons, même s’ils se ressemblent.

Fonction

totalNQueens(n: integer) → integer

ninteger: la taille de l’échiquier et le nombre de reines
Renvoieinteger: le nombre de façons de placer les reines de sorte qu’aucune n’attaque une autre

Contraintes

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

Exemples

Entrée: n = 4
Sortie: 2
Explication: En notant la colonne de la reine de chaque rangée de haut en bas, les deux plateaux sont 1, 3, 0, 2 et 2, 0, 3, 1. Chacun est l’image miroir de l’autre, et ils comptent comme deux solutions. Tout autre choix place deux reines dans la même colonne ou sur la même diagonale.

+10 tests cachés à la soumission

Pour aller plus loin

Peux-tu compter uniquement les plateaux qui restent différents après rotation et réflexion du plateau ? Pour n = 8, les 92 plateaux 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

Un placement est déterminé en choisissant une colonne pour chaque ligne, puisque deux reines sur une même ligne s’attaquent toujours. Cela représente encore n^n possibilités, soit environ 8.9 × 10^12 pour n = 12, donc tu ne peux pas toutes les énumérer. Deux idées permettent de résoudre le problème. Construis le plateau ligne par ligne et abandonne un plateau partiel dès qu’une reine est attaquée, ce qui réduit la recherche à moins d’un million de plateaux partiels pour n = 12. Et enregistre les colonnes et les diagonales occupées, afin que tester une case ne nécessite que trois consultations au lieu de parcourir toutes les reines placées jusque-là.

Essayez chaque positionnement avec une reine par ligne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque ligne doit contenir exactement une reine ; un placement est donc une liste cols où cols[r] est la colonne de la reine de la ligne r. Chaque entrée peut être l’une des n colonnes, il y a donc n^n listes. Parcourez-les comme le ferait un compteur kilométrique : augmentez la dernière entrée de un et, lorsqu’elle dépasse n-1, remettez-la à 0 et reportez l’incrément sur l’entrée précédente.

Pour chaque liste, comparez chaque paire de lignes i < j. Les deux reines s’attaquent lorsqu’elles partagent une colonne, cols[i] == cols[j], ou une diagonale. Sur une diagonale, descendre d’une ligne revient à se déplacer d’une colonne vers la gauche ou la droite ; deux reines partagent donc une diagonale exactement lorsque l’écart entre leurs colonnes est égal à l’écart entre leurs lignes : |cols[i] - cols[j]| == j - i. Une liste qui satisfait toutes les vérifications pour chaque paire correspond à un plateau valide. Puisque chaque liste est vérifiée, aucune n’est oubliée et aucune n’est comptée deux fois.

Cette méthode est lente, car elle ne s’arrête jamais à l’avance. Deux reines sur la même diagonale dans les deux premières lignes condamnent le plateau, mais le compteur essaie tout de même les n^(n-2) façons de remplir les autres lignes. Pour n = 8, cela représente 16,777,216 listes pour trouver 92 plateaux. Pour n = 12, cela représente environ 8.9 × 10^12 listes. Même à raison d’une nanoseconde par liste, cela prend environ 2.5 heures.

Algorithme

Commencez avec cols entièrement à zéro : chaque reine se trouve dans la colonne 0.
Vérifiez chaque paire de lignes i < j : la liste est invalide si cols[i] == cols[j] ou |cols[i] - cols[j]| == j - i.
Si aucune paire n’est en conflit, ajoutez 1 au compteur.
Faites avancer cols comme un compteur kilométrique : en partant de la dernière ligne et en remontant, réinitialisez à 0 chaque entrée qui vaut n-1, puis ajoutez 1 à la première entrée qui ne vaut pas cette valeur.
Lorsque toutes les entrées valaient n-1, les n^n listes ont toutes été examinées : renvoyez le compteur.

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 à l’aide d’ensembles de colonnes et de diagonales

Intuition

Placez les reines ligne par ligne, en partant du haut, et vérifiez chaque nouvelle reine dès que vous la placez. Si elle est attaquée, aucun moyen de remplir les lignes en dessous ne peut résoudre le problème : passez donc immédiatement à la case suivante. Si elle est en sécurité, faites un appel récursif sur la ligne suivante et, au retour de cet appel, retirez la reine et essayez la colonne suivante. Un appel qui atteint la ligne n a placé n reines sans danger et compte un échiquier. C’est du retour sur trace, et cette méthode élaguera fortement la recherche : pour n = 12, elle visite 856,189 configurations partielles au lieu de 8.9 × 10^12 configurations complètes.

L’autre moitié consiste à tester rapidement une case. Les lignes en dessous sont vides, et la ligne de la nouvelle reine ne contient aucune autre reine : seules trois lignes peuvent donc attaquer la case (row, c) : sa colonne, sa diagonale / et sa diagonale \. Toutes les cases d’une même diagonale / ont la même valeur row + c, comprise entre 0 et 2n-2. Toutes les cases d’une même diagonale \ ont la même valeur row - c, comprise entre -(n-1) et n-1 : ajoutez donc n-1 pour obtenir un indice compris entre 0 et 2n-2. Utilisez trois tableaux de drapeaux : cols de taille n, et diag et anti de taille 2n-1. La case est sûre si et seulement si les trois drapeaux sont désactivés : trois accès, O(1), alors qu’une comparaison avec chaque reine déjà placée coûterait O(n).

Une ligne ne peut contenir qu’une seule reine : en placer une active ses trois drapeaux, et la retirer les désactive à nouveau, ce qui laisse les tableaux exactement dans leur état initial. Sur l’échiquier de 4 par 4, une reine en (0, 0) active cols[0], diag[0] et anti[3]. À la ligne 1, la colonne 1 se trouve sur anti[3] : elle est donc ignorée sans même vérifier la reine elle-même.

La première ligne offre n colonnes, la deuxième au plus n-1, et ainsi de suite : la recherche est donc limitée à O(n!), et les diagonales réduisent considérablement ce nombre. Pour n = 12, les boucles testent 10,103,868 cases au total. La récursion a une profondeur de n appels et les tableaux contiennent environ 5n drapeaux : l’espace utilisé est donc O(n).

Algorithme

Crée trois tableaux d’indicateurs, tous désactivés : cols avec n entrées, et diag et anti avec 2n-1 entrées chacun.
Écris place(row). Si row == n, renvoie 1 : chaque ligne accueille une reine sans conflit.
Sinon, pour chaque colonne c, ignore-la si cols[c], diag[row + c] ou anti[row - c + n - 1] est activé.
Pour une colonne sans conflit, active les trois indicateurs, ajoute place(row + 1) au total, puis désactive-les.
Renvoie 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 des ensembles est rapide, mais à chaque ligne, elle teste encore les n colonnes, dont la plupart sont attaquées. Un masque de bits permet de passer directement aux cases libres. Le bit c d’un entier représente la colonne c de la ligne que tu es sur le point de remplir, et tu conserves trois masques : cols, les colonnes déjà occupées, left, les cases de cette ligne attaquées dans une direction diagonale, et right, celles attaquées dans l’autre.

Les cases libres s’obtiennent alors avec une seule expression : free = ~(cols | left | right) & full, où full a ses n bits de poids faible à 1. free & -free isole la case libre la plus à droite, et la soustraire permet de passer à la suivante. Lorsque tu places une reine à bit et descends d’une ligne, sa colonne reste occupée, tandis que chaque attaque diagonale se décale d’une colonne. La ligne suivante reçoit donc cols | bit, ((left | bit) << 1) & full et (right | bit) >> 1. Il n’y a rien à annuler : chaque appel possède ses propres trois entiers. Lorsque cols == full, les n reines sont placées.

Prenons n = 4 et une première reine dans la colonne 1, bit = 0010, en écrivant la colonne 0 comme bit le plus à droite. La ligne 1 reçoit cols = 0010, left = 0100 et right = 0001, donc free = 1000 : la colonne 3 est le seul choix, trouvé sans tester les colonnes 0, 1 ou 2.

La recherche visite les mêmes échiquiers partiels que la version avec des ensembles, mais chaque étape de la boucle place désormais une reine. Pour n = 12, cela représente 856,188 étapes au lieu de 10,103,868 tests de cases, avec quelques opérations sur des entiers à chaque étape. Le temps reste borné par O(n!), et la récursion a une profondeur de n appels. Le code R exécute les mêmes masques sans récursion : il conserve dans un vecteur tous les échiquiers partiels d’une ligne et les développe tous, une ligne à la fois ; il stocke donc en mémoire un niveau entier d’échiquiers plutôt que n appels.

Algorithme

Définissez full = (1 << n) - 1, le masque de toutes les n colonnes.
Écrivez 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

La recherche elle-même est courte. La plupart des bogues se trouvent dans l’arithmétique des diagonales et dans l’étape d’annulation.

Utiliser row - c comme indice sans ajouter n-1. En Java, cela provoque une exception ; en C, cela lit de la mémoire en dehors du tableau ; et en Python, anti[-2] lit discrètement l’indicateur d’une autre diagonale, ce qui donne un résultat de comptage erroné sans aucune erreur.
Dimensionner les tableaux de diagonales avec n entrées. Un plateau de n × n possède 2n-1 diagonales dans chaque direction.
Ne vérifier qu’une seule direction de diagonale, ou seulement les colonnes. Les deux directions diagonales sont attaquées.
Oublier de désactiver les indicateurs après le retour de l’appel récursif. Toutes les branches suivantes voient alors des reines qui ne sont plus sur le plateau, et le nombre diminue.
Omettre & full lors du calcul de free. ~x active également tous les bits au-delà de la colonne n-1, donc la boucle sélectionne des cases hors du plateau ; et en Python ou en Ruby, dont les entiers n’ont pas de largeur fixe, free devient négatif et la boucle ne se termine jamais.
Considérer les images miroir comme un seul plateau. Le problème les compte séparément : n = 4 donne 2 plateaux, qui sont l’image miroir l’un de l’autre.
Traiter incorrectement les petits plateaux avec des cas particuliers. n = 1 donne 1 plateau, tandis que n = 2 et n = 3 n’en donnent aucun. La recherche traite correctement les trois cas sans cas particulier.

Questions fréquentes4

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

Le retour sur trace est borné par O(n!) : la première ligne a n choix, la suivante au plus n-1, et ainsi de suite. Les vérifications des diagonales élaguent la recherche bien en dessous de cette borne, jusqu’à 856,189 échiquiers partiels pour n = 12. Aucune méthode polynomiale n’est connue pour compter les solutions ; une recherche comme celle-ci est donc la réponse standard. L’espace est de O(n).

Comment savoir sur quelle diagonale se trouve un carré ?

Se déplacer d’un pas le long d’une diagonale / ajoute 1 à la ligne et soustrait 1 à la colonne, donc row + col ne change jamais. Se déplacer le long d’une diagonale \ ajoute 1 aux deux, donc row - col ne change jamais. Chaque somme désigne une diagonale, et ajouter n-1 à la différence la transforme en un indice de tableau allant de 0 à 2n-2.

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

N-Queens demande tous les échiquiers, représentés sous forme de lignes de texte. N-Queens II demande seulement combien il y en a. La recherche repose sur le même retour sur trace, mais le comptage ne nécessite pas de conserver l’échiquier en mémoire, seulement les ensembles de colonnes et de diagonales ; il est donc plus rapide et plus léger. C’est aussi ce qui rend la version avec masque de bits naturelle ici.

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

Oui. Le miroir horizontal d’un plateau donne un autre plateau valide ; les plateaux dont la première reine se trouve dans la moitié gauche correspondent donc à ceux où elle se trouve dans la moitié droite. Compte les plateaux dont la première reine se trouve dans les colonnes 0 à n/2 - 1, puis double ce nombre. Lorsque n est impair, ajoute une fois les plateaux dont la première reine se trouve dans la colonne centrale. Cela réduit la recherche de moitié.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

n = 4

Attendu

N-Queens II

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque positionnement avec une reine par ligne

Retour arrière à l’aide d’ensembles de colonnes et de diagonales

Retour sur trace avec des masques de bits

Pièges et cas limites

Questions fréquentes4

Problèmes similaires