In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Das N-Queens Problem fragt: Wie kann man N Damen auf ein Schachbrett setzen, ohne dass eine Dame eine andere angreift?

Eine Dame im Schach kann sich horizontal, vertikal und diagonal bewegen. Genau das macht das Problem spannend: Schon bei kleinen N entstehen viele Möglichkeiten.

Das N-Queens Problem ist bekannt, weil es ein klassisches Beispiel für Backtracking ist: Du probierst etwas aus, merkst später, dass es nicht passt, und gehst einen Schritt zurück.

In diesem Artikel lernst du, wie du eine Lösung systematisch aufbaust. Nebenbei übst du Rekursion, Abbruchbedingungen und saubere kleine Hilfsmethoden in Java.

 

Problemstellung

Platziere N Damen auf einem N x N-Brett so, dass keine Dame eine andere angreift.

  • Keine gleiche Zeile: In einer Zeile darf höchstens eine Dame stehen.
  • Keine gleiche Spalte: In einer Spalte darf höchstens eine Dame stehen.
  • Keine Diagonalen: Auch diagonal dürfen sich Damen nicht sehen.
  • Wir suchen hier eine gültige Anordnung (eine Lösung). Optional können wir später alle Lösungen zählen.

Mini-Beispiel für N = 4 (eine gültige Lösung als Spaltenposition pro Zeile):

  1. Zeile 0: Dame in Spalte 1
  2. Zeile 1: Dame in Spalte 3
  3. Zeile 2: Dame in Spalte 0
  4. Zeile 3: Dame in Spalte 2

 

Die Idee dahinter

Backtracking bedeutet: Du baust die Lösung schrittweise auf. Für jede Zeile suchst du eine Spalte, die gerade noch erlaubt ist. Wenn später nichts mehr geht, nimmst du die letzte Entscheidung zurück und probierst die nächste Möglichkeit.

Rekursion passt hier perfekt: solve(row) versucht, ab row eine Dame zu setzen, und ruft sich selbst für die nächste Zeile auf.

Eine einfache Visualisierung (wir gehen zeilenweise vor):

  • Zeile 0: setze eine Dame irgendwo
  • Zeile 1: setze die nächste Dame so, dass sie nicht kollidiert
  • ...
  • Zeile N-1: wenn auch hier alles passt, hast du eine Lösung

 

Schritt für Schritt zur Lösung

  1. Wir platzieren Damen zeilenweise: pro Zeile genau eine Dame.
  2. Wir merken uns, in welcher Spalte pro Zeile eine Dame steht, z.B. in einem Array cols[row] = col.
  3. Bevor wir eine Dame setzen, prüüfen wir: gleiche Spalte oder gleiche Diagonale mit allen vorherigen Zeilen?
  4. Wenn es passt: setzen (Array eintragen) und zur nächsten Zeile gehen.
  5. Abbruchbedingung: Wenn row == n, sind alle Damen gesetzt, die Lösung ist fertig.
  6. Wenn keine Spalte in einer Zeile passt: zurück (Backtracking) und in der vorherigen Zeile die nächste Spalte probieren.

 

Java-Implementierung (Variante A: straightforward)

public class NQueensStraightforward {

  public static void main(String[] args) {
    int n = 4;

    int[] cols = new int[n]; // cols[row] = col
    boolean solved = solve(n, 0, cols);

    if (solved) {
      System.out.println("Found solution for n=" + n);
      printBoard(n, cols);
      System.out.println("Positions (row -> col): " + positionsAsString(cols));
    } else {
      System.out.println("No solution for n=" + n);
    }
  }

  private static boolean solve(int n, int row, int[] cols) {
    // Abbruchbedingung: alle Zeilen sind belegt
    if (row == n) {
      return true;
    }

    for (int col = 0; col < n; col++) {
      if (isSafe(row, col, cols)) {
        cols[row] = col;

        if (solve(n, row + 1, cols)) {
          return true; // wir suchen nur eine Loesung
        }
        // Backtracking: keine Loesung gefunden, also naechste Spalte probieren
      }
    }

    return false;
  }

  private static boolean isSafe(int newRow, int newCol, int[] cols) {
    for (int row = 0; row < newRow; row++) {
      int col = cols[row];

      // gleiche Spalte
      if (col == newCol) {
        return false;
      }

      // Diagonalen: Abstand in Zeilen == Abstand in Spalten
      int rowDiff = newRow - row;
      int colDiff = Math.abs(newCol - col);

      if (rowDiff == colDiff) {
        return false;
      }
    }

    return true;
  }

  private static void printBoard(int n, int[] cols) {
    for (int row = 0; row < n; row++) {
      StringBuilder line = new StringBuilder();

      for (int col = 0; col < n; col++) {
        line.append(cols[row] == col ? "Q " : ". ");
      }

      System.out.println(line.toString().trim());
    }
  }

  private static String positionsAsString(int[] cols) {
    StringBuilder sb = new StringBuilder();
    sb.append("[");

    for (int i = 0; i < cols.length; i++) {
      if (i > 0) sb.append(", ");
      sb.append(i).append("->").append(cols[i]);
    }

    sb.append("]");

    return sb.toString();
  }
}

Variante A ist bewusst direkt: Wir prüfen bei jedem Versuch die bisher gesetzten Damen. Das ist leicht zu verstehen und für kleine N absolut okay. Wichtig ist die Abbruchbedingung row == n: Erst dann ist die Lösung vollständig. Die Laufzeit wächst schnell, weil viele Kombinationen ausprobiert werden.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class NQueensOptimized {

  public static void main(String[] args) {
    int n = 8;

    int[] cols = new int[n];

    boolean[] usedCols = new boolean[n];
    boolean[] usedDiag1 = new boolean[2 * n - 1]; // row + col
    boolean[] usedDiag2 = new boolean[2 * n - 1]; // row - col + (n - 1)

    boolean solved = solve(n, 0, cols, usedCols, usedDiag1, usedDiag2);

    if (solved) {
      System.out.println("Found solution for n=" + n);
      printBoard(n, cols);
      System.out.println("Positions (row -> col): " + positionsAsString(cols));
    } else {
      System.out.println("No solution for n=" + n);
    }
  }

  private static boolean solve(int n,
                               int row,
                               int[] cols,
                               boolean[] usedCols,
                               boolean[] usedDiag1,
                               boolean[] usedDiag2) {

    // Abbruchbedingung: alle Zeilen sind belegt
    if (row == n) {
      return true;
    }

    for (int col = 0; col < n; col++) {
      int d1 = diag1Index(row, col);       // row + col
      int d2 = diag2Index(row, col, n);    // row - col + (n - 1)

      if (usedCols[col] || usedDiag1[d1] || usedDiag2[d2]) {
        continue;
      }

      // set
      cols[row] = col;
      usedCols[col] = true;
      usedDiag1[d1] = true;
      usedDiag2[d2] = true;

      if (solve(n, row + 1, cols, usedCols, usedDiag1, usedDiag2)) {
        return true;
      }

      // unset (Backtracking)
      usedCols[col] = false;
      usedDiag1[d1] = false;
      usedDiag2[d2] = false;
    }

    return false;
  }

  private static int diag1Index(int row, int col) {
    return row + col;
  }

  private static int diag2Index(int row, int col, int n) {
    return row - col + (n - 1);
  }

  private static void printBoard(int n, int[] cols) {
    for (int row = 0; row < n; row++) {
      StringBuilder line = new StringBuilder();

      for (int col = 0; col < n; col++) {
        line.append(cols[row] == col ? "Q " : ". ");
      }

      System.out.println(line.toString().trim());
    }
  }

  private static String positionsAsString(int[] cols) {
    StringBuilder sb = new StringBuilder();
    sb.append("[");

    for (int i = 0; i < cols.length; i++) {
      if (i > 0) sb.append(", ");
      sb.append(i).append("->").append(cols[i]);
    }

    sb.append("]");

    return sb.toString();
  }
}

Variante B macht die gleiche Suche, aber die Prüfung ist schneller: Statt jedes Mal alle vorherigen Damen zu vergleichen, merken wir uns belegte Spalten und Diagonalen in drei boolean-Arrays. Das ist idiomatisch, gut testbar und spart Arbeit pro Versuch. An der grundsätzlichen Sache ändert sich nichts: Die Anzahl der Versuche wächst trotzdem schnell, aber die einzelnen Checks sind konstant schnell.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1: Eingabe n=4, mögliche Ausgabe (eine Lösung):

  • Output Positions (row -> col): [0->1, 1->3, 2->0, 3->2]
  • Output . Q . .
  • Output . . . Q
  • Output Q . . .
  • Output . . Q .

Beispiel 2: Eingabe n=1, Ausgabe:

  • Output Positions (row -> col): [0->0]
  • Output Q

Beispiel 3: Eingabe n=2 oder n=3, Ausgabe:

  • Output No solution for n=2 (bzw. No solution for n=3)

 

Typische Fehler

  • Abbruchbedingung falsch: Wenn du bei row == n - 1 abbrichst, fehlt die letzte Dame oder du meldest zu früh Erfolg.
  • Off-by-one in Schleifen: col <= n statt col < n führt zu ArrayIndexOutOfBoundsException.
  • Diagonalen falsch geprüft: Diagonal bedeutet nicht row + col gleich in beiden, sondern bei Variante A: abs(colDiff) == rowDiff.
  • Backtracking nicht sauber rückgängig: In Variante B musst du beim Zurückgehen alle drei Marker wieder auf false setzen.
  • Array wird nicht pro Zeile überschrieben: Wenn du cols[row] nicht setzt, bleibt ein alter Wert stehen und verwirrt dich beim Debuggen.
  • Zu frühes return: Wenn du in der Schleife ein return false an der falschen Stelle hast, probierst du nie die nächste Spalte.

 

Fazit

Du hast gesehen, wie man das N-Queens Problem vereinfacht löst, indem man zeilenweise Damen platziert und Konflikte prüft. Dabei sind zwei Kernideen hängen geblieben: Rekursion mit klarer Abbruchbedingung und Backtracking zum systematischen Ausprobieren. Variante A ist ideal zum Verstehen, Variante B zeigt, wie man Checks mit passenden Datenstrukturen beschleunigt.