NQueens package

Überblick

Das N-Queens-Problem ist eine klassische Herausforderung, die häufig in Programminterviews und akademischen Umgebungen auftritt. Die Herausforderung besteht darin, N Queens auf ein N × N -Schachbrett zu legen, so dass sich keine zwei Königinnen drohen. Dies bedeutet, dass keine zwei Königinnen dieselbe Zeile, Spalte oder Diagonale teilen können.

Problemanweisung

Bei einer Ganzzahl N geben Sie alle unterschiedlichen Lösungen an das N-Queens-Puzzle zurück. Sie können die Antworten in jeder Reihenfolge zurückgeben.

Jede Lösung enthält eine bestimmte Platinekonfiguration der N-Queens-Platzierung, wobei 'Q' eine Königin anzeigt und ''. zeigt einen leeren Raum an.

Beispiel

Für n = 4 sind die möglichen Lösungen:

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

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

Ansatz und Algorithmen

Backtracking -Algorithmus

Der häufigste Ansatz zur Lösung des N-Queens-Problems ist die Verwendung von Backtracking. Der Backtracking -Algorithmus baut inkrementell Kandidaten für die Lösung auf und verlässt einen Kandidaten, sobald er feststellt, dass der Kandidat unmöglich zu einer gültigen Lösung führen kann.

Schritte:

1. Initialize the Board : Beginnen Sie mit einem leeren N × N -Board.
2. Place the Queen : Versuchen Sie, die Königin in die erste Reihe zu platzieren und weiter nachfolgenden Königinnen zu platzieren.
3. Check Validity : Überprüfen Sie für jede Platzierung der Königin, ob sie mit bereits platzierten Königinnen in Konflikt steht.
4. Backtrack if Necessary : Wenn das Platzieren einer Königin zu keiner Lösung führt, entfernen Sie die Königin (Rückstrahl) und probieren Sie die nächste Position aus.
5. Store the Solution : Wenn eine gültige Konfiguration gefunden wird (N Queens platziert), speichern Sie die Board -Konfiguration.
6. Repeat : Setzen Sie diesen Vorgang fort, bis alle möglichen Konfigurationen ausprobiert wurden.

Herausforderungen

Vorstandsdarstellung

Die Karte kann mit einer 2D -Liste dargestellt werden, in der jede Zelle entweder 'q' oder 'ist.

Konflikte überprüfen

Es ist entscheidend, effizient über die Überprüfung auf Konflikte zu prüfen:

1. Row Check : Stellen Sie sicher, dass sich keine anderen Königinnen in derselben Zeile befinden.
2. Column Check : Stellen Sie sicher, dass sich keine anderen Königinnen in derselben Spalte befinden.
3. Diagonal Check : Sicherstellen, dass keine anderen Königinnen auf derselben Diagonal sind.

Optimierung

Die Verwendung von Sets zum Verfolgung besetzter Spalten und Diagonalen kann den Konfliktprüfprozess beschleunigen.

Parallelität mit Threadpoolexecutor

Um das Lösen des Problems für größere N zu optimieren, nutzt die Lösung die Parallelität mit ThreadPoolexecutor:

• Jeder Thread löst das Problem für eine andere Spalte in der ersten Zeile.
• Dieser parallele Ansatz kann die Zeit erheblich verkürzen, um alle Lösungen zu finden.

Unsere Lösung

Diese Lösung kam zu einer unserer kostenlosen Freitag -Herausforderungen , bei denen wir während unserer Ausfallzeiten zufällige Interview -Herausforderungen auswählen, um Lösungen zu schreiben.

Installation

 pip install wolfsoftware.NQueens

Verwendung

 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.

Zusammenfassung

Das N-Queens-Problem ist eine faszinierende und komplexe Herausforderung, die ein tiefes Verständnis der Techniken der Rekursion, Rückverfolgung und Optimierung erfordert. Durch die Nutzung von Multi-Threading findet diese Implementierung alle möglichen Lösungen für eine bestimmte Board-Größe effizient. Das Verständnis und die Umsetzung des N-Queens-Problems ist eine wertvolle Übung zur Verbesserung der Fähigkeiten zur Problemlösung und zum algorithmischen Denken.