N-Queens-Problem mit Backtracking in Java/C++

N-Queens-Problem mit Backtracking in Java/C++

Das N-Queens-Problem ist ein klassisches Puzzle der Computerwissenschaft, das darin besteht, N Königinnen auf einem NxN-Schachbrett so zu platzieren, dass sie sich gegenseitig nicht bedrohen. Jede Königin bedroht horizontale, vertikale und diagonale Felder. Dieses Problem kann mit dem Backtracking-Algorithmus gelöst werden.

Backtracking-Algorithmus

Backtracking ist eine Technik zur Problemlösung, bei der partielle Lösungen systematisch erkundet werden. Wenn eine partielle Lösung zu einem Widerspruch führt, wird sie verworfen und die Suche wird von einer früheren partiellen Lösung fortgesetzt.

Lösung des N-Queens-Problems mit Backtracking

Der Backtracking-Algorithmus für das N-Queens-Problem funktioniert wie folgt:

1. Initialisierung: Setze eine Königin in die erste Zeile der ersten Spalte.
2. Lokale Suche: Prüfe für jede Spalte in der aktuellen Zeile, ob eine Königin platziert werden kann, ohne eine andere Königin zu bedrohen.
3. Rekursion: Wenn eine sichere Spalte gefunden wird, setze eine Königin in diese Spalte und gehe zur nächsten Zeile über.
4. Zurückverfolgung: Wenn keine sichere Spalte gefunden wird oder die letzte Zeile erreicht ist, entferne die Königin aus der aktuellen Spalte und gehe zur vorherigen Zeile zurück.
5. Ende: Wenn alle Königinnen platziert sind, wurde eine Lösung gefunden.

Implementierung in Java

java
import java.util.Arrays;

public class NQueens {

private int[] queens;
private int count;

public NQueens(int n) {
queens = new int[n];
count = 0;
}

public void solve() {
solve(0);
}

private void solve(int row) {
if (row == queens.length) {
count++;
System.out.println(Arrays.toString(queens));
return;
}

for (int col = 0; col < queens.length; col++) {
if (isSafe(row, col)) {
queens[row] = col;
solve(row + 1);
}
}
}

private boolean isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || Math.abs(queens[i] - col) == row - i) {
return false;
}
}

return true;
}

public static void main(String[] args) {
NQueens nQueens = new NQueens(8);
nQueens.solve();
System.out.println("Anzahl der Lösungen: " + nQueens.count);
}
}


Implementierung in C++

c++
#include <iostream>
#include <vector>

using namespace std;

class NQueens {
private:
vector<int> queens;
int count;

public:
NQueens(int n) {
queens.resize(n);
count = 0;
}

void solve() {
solve(0);
}

void solve(int row) {
if (row == queens.size()) {
count++;
for (int queen : queens) {
cout << queen << " ";
}
cout << endl;
return;
}

for (int col = 0; col < queens.size(); col++) {
if (isSafe(row, col)) {
queens[row] = col;
solve(row + 1);
}
}
}

bool isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (queens[i] == col || abs(queens[i] - col) == row - i) {
return false;
}
}

return true;
}

int getCount() {
return count;
}
};

int main() {
NQueens nQueens(8);
nQueens.solve();
cout << "Anzahl der Lösungen: " << nQueens.getCount() << endl;

return 0;
}


Fazit

Das N-Queens-Problem ist ein gut untersuchtes Problem, das mit dem Backtracking-Algorithmus effektiv gelöst werden kann. Die Implementierung in Java und C++ zeigt die praktische Anwendung von Backtracking zur Problemlösung. Das Problem kann auch verwendet werden, um komplexere Algorithmen zu veranschaulichen, wie z. B. Heuristiken und Optimierungstechniken.

FAQs

1. Was ist das N-Queens-Problem?
Das N-Queens-Problem besteht darin, N Königinnen auf einem NxN-Schachbrett so zu platzieren, dass sie sich gegenseitig nicht bedrohen.

2. Was ist der Backtracking-Algorithmus?
Der Backtracking-Algorithmus ist eine Technik zur Problemlösung, bei der partielle Lösungen systematisch erkundet werden.

3. Wie löst der Backtracking-Algorithmus das N-Queens-Problem?
Der Algorithmus versucht, Königinnen rekursiv auf dem Schachbrett zu platzieren. Wenn eine Platzierung zu einem Widerspruch führt, wird sie verworfen und die Suche wird von einer früheren partiellen Lösung fortgesetzt.

4. Wie kann ich die Anzahl der Lösungen für das N-Queens-Problem finden?
Du kannst den Backtracking-Algorithmus mit einer Zählfunktion implementieren, die die Anzahl der gefundenen Lösungen zählt.

5. Wie kann ich das N-Queens-Problem optimieren?
Es gibt verschiedene Optimierungen, die die Effizienz des Backtracking-Algorithmus verbessern können, z. B. Heuristiken und symmetrische Einschränkungen.

6. Wo kann ich mehr über das N-Queens-Problem erfahren?
Weitere Informationen findest du in Büchern, Artikeln und Online-Ressourcen zum Thema Backtracking und Problemlösung.

7. Ist das N-Queens-Problem ein NP-vollständiges Problem?
Nein, das N-Queens-Problem ist kein NP-vollständiges Problem, da es in polynomialer Zeit gelöst werden kann.

8. Wie kann ich das N-Queens-Problem in anderen Programmiersprachen lösen?
Du kannst den Backtracking-Algorithmus in jeder Programmiersprache implementieren, die Rekursion und Datenstrukturen unterstützt.