NQueens package

Aperçu

Le problème N-Queens est un défi classique souvent rencontré dans les entretiens en programmation et les paramètres académiques. Le défi consiste à placer n queens sur un échangeur n × n de sorte que deux reines ne menacent. Cela signifie qu'aucune reine ne peut partager la même ligne, colonne ou diagonale.

Déclaration de problème

Étant donné un entier n, retournez toutes les solutions distinctes au puzzle N-Queens. Vous pouvez retourner les réponses dans n'importe quel ordre.

Chaque solution contient une configuration de carte distincte du placement de N-Queens, où «q» indique une reine et '. indique un espace vide.

Exemple

Pour n = 4, les solutions possibles sont:

 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Approche et algorithmes

Algorithme de retour en arrière

L'approche la plus courante pour résoudre le problème des N-Queens consiste à utiliser du retour en arrière. L'algorithme de retour en arrière construit progressivement les candidats à la solution et abandonne un candidat dès qu'il détermine que le candidat ne peut pas conduire à une solution valide.

Mesures:

1. Initialize the Board : commencez par une carte N × N vide.
2. Place the Queen : essayez de placer la reine dans la première rangée et procédez à la place des reines suivantes.
3. Check Validity : pour chaque placement de la reine, vérifiez s'il est en conflit avec les reines déjà placées.
4. Backtrack if Necessary : Si placer une reine ne mène à aucune solution, retirez la reine (retour en arrière) et essayez la position suivante.
5. Store the Solution : si une configuration valide est trouvée (n Queens placé), stockez la configuration de la carte.
6. Repeat : continuez ce processus jusqu'à ce que toutes les configurations possibles aient été essayées.

Défis

Représentation du conseil d'administration

La carte peut être représentée à l'aide d'une liste 2D où chaque cellule est «Q» ou «».

Vérification des conflits

La vérification efficace des conflits est cruciale:

1. Row Check : s'assurer qu'aucune autre reine n'est dans la même ligne.
2. Column Check : s'assurer qu'aucune autre reine n'est dans la même colonne.
3. Diagonal Check : s'assurer qu'aucune autre reine n'est sur la même diagonale.

Optimisation

L'utilisation d'ensembles pour suivre les colonnes et les diagonales occupées peut accélérer le processus de vérification des conflits.

Concurrence avec ThreadpoolExecutor

Pour optimiser la résolution du problème pour plus grand N, la solution tire parti de la concurrence avec ThreadPoolExecutor:

• Chaque fil commence à résoudre le problème pour une colonne différente dans la première ligne.
• Cette approche parallèle peut réduire considérablement le temps pour trouver toutes les solutions.

Notre solution

Cette solution est venue à Frome l'un de nos défis gratuits du vendredi , où nous choisissons des défis entre les interviews aléatoires pendant nos temps d'arrêt pour écrire des solutions.

Installation

 pip install wolfsoftware.NQueens

Usage

 usage: nqueens [-h] [-v] [-V] [board_size]

See solutions to the NQueens problem.

positional arguments:
  board_size     Size of the board (default is 8 for the Eight Queens puzzle) (default: 8)

flags:
  -h, --help     Show this help message and exit
  -v, --verbose  Enable verbose output - show the actual boards (default: False)
  -V, --version  Show program's version number and exit.

The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other.

Résumé

Le problème de N-Queens est un défi fascinant et complexe qui nécessite une compréhension approfondie des techniques de récursivité, de retour en arrière et d'optimisation. En tirant parti du multi-threading, cette implémentation trouve efficacement toutes les solutions possibles pour une taille de carte donnée. La compréhension et la mise en œuvre du problème des N-Queens est un exercice précieux pour améliorer les compétences de résolution de problèmes et la pensée algorithmique.