# n DamenProblem



## Kubis (24. Jan 2010)

Hallo ich sollte ein programm schreiben das das n damen problem heißt nun bin ich soweit fertig
aber ich bekomme beim compl. foglende fehlermeldung raus.

Compile D:\Users\XXX\Desktop\N Damen Problem\QueenProblem2.java....
Note: D:\Users\XXX\Desktop\N Damen Problem\QueenProblem2.java uses unchecked or unsafe operations.

Note: Recompile with -Xlint:unchecked for details.


Compilierung beendet

hier ist mein code für die klasse QueenProblem2


```
import java.util.LinkedList;
import java.util.Iterator;

/**
 * Der Algorithmus zum N-Damenproblem (kongruenzfrei).
 * Die Besonderheit bei vorliegendem Algorithmus ist, dass die Lösungen NICHT
 * durch Drehung und Spiegelung in andere Lösungen überführt werden können,
 * d.h. dass es in der Lösungsmenge keine zwei Lösungen gibt, die ähnlich sind.
 *
 * Nur die private Methode "solve" bezeichnet den eigentlichen, rekursiven
 * Algorithmus zum Damenproblem.
 */
public class QueenProblem2 {

  /**
   * Löst ein N-Damenproblem und gibt alle gefundenen Lösungen als Liste zurück.
   * @param N Die Mächtigkeit des zugrundeliegenden Brettes (NxN-Brett).
   * @return Liste aller gefundenen Lösungen.
   *         Eine Lösung besteht in Form einer BoardOfQueens2-Instanz.
   */
  public static LinkedList solve(int N) {

    // Die zunächst leere Liste der Lösungen instanziieren.
    LinkedList results = new LinkedList();

    // Das Ausgangsbrett instanziieren, ein leeres NxN-Brett.
    BoardOfQueens2 emptyboard = new BoardOfQueens2(N);

    // Das eigentliche Lösungsverfahren!
    QueenProblem2.solve(results, emptyboard, 0);

    // Alle Lösungen als Liste zurückgeben!
    return results;
  }

  /**
   * Löst das Damenproblem rekursiv mittels Tiefensuche.
   * Die Suchtiefe wird durch die Anzahl der Spalten des zugrundeliegenden
   * Brettes bestimmt. Wenn alle Spalten mit Erfolg abgearbeitet werden konnten,
   * liegt eine Lösung vor, das aktuelle Brett wird in diesem Falle als Kopie
   * der Lösungsliste hinzugefügt.
   * @param results Die Lösungsliste.
   * @param current Das aktuelle Brett.
   * @param x Der aktuelle Spaltenindex des Brettes.
   */
  private static void solve(LinkedList results, BoardOfQueens2 current, int x) {

    // Gibt es eine weitere Spalte, die noch besucht werden kann?
    if (x < current.getN()) {

      /* Lösungen suchen! */

      for (int y = 0; y < current.getN(); y++) {

        if (current.canSetQueenAt(x, y)) {

          // Setze Dame auf Feld(x, y)
          current.setQueenAt(x, y);

          // Rekursionsschritt mit der nächsten Spalte(x + 1)
          QueenProblem2.solve(results, current, x + 1);

          // Nimm die Dame wieder vom Feld(x, y),
          // d.h. alten Zustand des Brettes wieder herstellen
          current.unsetQueenAt(x, y);
        }
        // else: Dame kann nicht gesetzt werden (Sackgasse),
        //       deshalb weitere Suche in die Tiefe nicht nötig.
      }

    } else {

      /* Lösung gefunden! */

      // Es gilt nur noch zu prüfen,
      // ob bereits eine ähnliche Lösung in die Ergebnisliste aufgenommen wurde.
      // Nur im Falle "Es existiert noch keine ähnliche Lösung" wird die
      // aktuelle Lösung (current) als Klon in die Ergebnisliste (results)
      // aufgenommen.

      boolean hasSame = false;

      Iterator iterator = results.listIterator();
      while (iterator.hasNext()) {
        if (current.isSameBoard((BoardOfQueens2)iterator.next())) {
          hasSame = true;
          break;
        }
      }

      if (!hasSame) {
        results.add(current.clone());
      }
    }
  }

  /**
   * Das Hauptprogramm, welches das Damenproblem für viele verschiedengroße
   * Bretter lösen kann.
   * Jedes einzelne Argument wird als natürliche Zahl N interpretiert
   * (N-Damenproblem).
   * @param arguments Die Argumente der Konsole, erwünscht ist nur die
   *                  Auflistung natürlicher Zahlen (größer als Null).
   */
  public static void main(String[] arguments) {

    for (int i = 0; i < arguments.length; i++) {

      try {

        int N = Integer.parseInt(arguments[i]);

        if (N > 0) {

          /* Löse das N-Damenproblem! */

          // Berechne alle Lösungen zum NxN-Brett.
          LinkedList results = QueenProblem2.solve(N);

          // Gib lediglich die Anzahl der gefundenen Lösungen aus.
          System.out.print("(" + N + " x " + N + ")");
          System.out.println(" -> " + results.size() + " Result(s)\n");

          // Gib die gefundenen Lösungen aus, falls vorhanden.
          Iterator iterator = results.listIterator();
          while (iterator.hasNext()) {
            System.out.println(iterator.next());
          }

        } else {
          System.err.println("Argument must be greater than '0'.");
        }

      } catch (NumberFormatException nfe) {
        System.err.println(nfe.getMessage());
      }
    }
  }
}
```

und hier ist mein code für die Klasse BoardOfQueens2


```
/**
 * Diese Klasse repräsentiert ein NxN-Brett, auf dem nur Damen stehen können
 * und vereinfacht insbesondere den Algorithmus zum N-Damenproblem
 * (kongruenzfrei) erheblich.
 */
public class BoardOfQueens2 implements Cloneable {

  /**
   * Gibt die Größe des Brettes an: NxN-Brett.
   */
  private int N;

  /**
   * Ein zweidimensionales Array, welches das Brett darstellt.
   * Jedes Feld gibt an, ob eine Dame drauf steht oder nicht (boolean).
   */
  private boolean[][] board;

  /**
   * Instanziiert ein NxN-Brett.
   * @param N Die Mächtigkeit des Brettes.
   *          Ein übliches Schachbrett wird mit 8 instanziiert.
   */
  public BoardOfQueens2(int N) {

    // NxN-Brett
    this.N = N;
    this.board = new boolean[this.N][this.N];

    // Jedes einzelne Feld wird als leer (false) gekennzeichnet.
    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        this.board[x][y] = false;
      }
    }
  }

  /**
   * Erzeugt eine neue BoardOfQueens2-Instanz und sichert darin den aktuellen
   * Zustand der aktuellen Objekt-Instanz.
   * @return Eine Kopie des aktuellen Objekts.
   */
  public Object clone() {

    BoardOfQueens2 result = new BoardOfQueens2(this.N);

    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        result.board[x][y] = this.board[x][y];
      }
    }

    return result;
  }

  /**
   * Gibt die Mächtigkeit des Brettes zurück (NxN-Brett).
   * @return Die Anzahl der Spalten bzw. der Zeilen.
   */
  public int getN() {
    return this.N;
  }

  /**
   * Prüft, ob eine Dame auf das Feld(x, y) gesetzt werden kann.
   * Eine Dame kann bzw. sollte nur gesetzt werden,
   * wenn die Dame auf dem Feld(x, y) von keiner anderen bereits gesetzten
   * Dame geschlagen werden kann.
   * Diese Methode prüft nun konkret, ob die x-te Spalte leer ist,
   * ob die y-te Zeile leer ist, ob die beiden Diagonalen, die
   * durch das Feld(x, y) führen, leer sind.
   * @param x Der Spaltenindex des Brettes.
   * @param y Der Zeilenindex des Brettes.
   * @return true, Dame kann auf das Feld(x, y) gesetzt werden.
   */
  public boolean canSetQueenAt(int x, int y) {

    return this.isEmptyCol(x)
      && this.isEmptyRow(y)
      && this.isEmptyFalling(x, y)
      && this.isEmptyRising(x, y);
  }

  /**
   * Setzt eine Dame auf das Feld(x, y).
   * @param x Der Spaltenindex des Brettes.
   * @param y Der Zeilenindex des Brettes.
   */
  public void setQueenAt(int x, int y) {

    this.board[x][y] = true;
  }

  /**
   * Nimmt eine Dame vom Feld(x, y).
   * @param x Der Spaltenindex des Brettes.
   * @param y Der Zeilenindex des Brettes.
   */
  public void unsetQueenAt(int x, int y) {

    this.board[x][y] = false;
  }

  /**
   * Gibt den aktuellen Zustand des Brettes in Form eines Diagramms zurück.
   * @return Das Diagramm als Zeichenkette.
   */
  public String toString() {

    String result = "";

    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        if (this.board[x][y]) {
          result += "|D";
        } else {
          result += "| ";
        }
      }
      result += "|\n";
    }

    return result;
  }

  /**
   * Prüft, ob durch Rotation und Spiegelung das gegebene Brett other in das
   * Brett dieser Instanz überführt werden kann.
   * @param other Das Brett, mit dem verglichen wird.
   * @return false, falls keine Ähnlichkeit vorhanden.
   */
  public boolean isSameBoard(BoardOfQueens2 other) {

    // Zunächst muss überprüft werden,
    // ob überhaupt die selbe Cardinalität vorliegt.
    if (this.N != other.N) {
      return false;
    }

    // Die Hilfsvariable "oboard" wird zunächst auf gleichsinnige und
    // nach der Spiegelung auf gegensinnige Kongruenz geprüft.

    boolean[][] oboard = other.board;

    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard spiegeln
    oboard = this.mirrorMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    // oboard rotieren um 90°
    oboard = this.rotateMatrix(oboard);
    // oboard == this.board
    if (this.testEqualMatrix(oboard)) {
      return true;
    }

    return false;
  }

  /* HILFSMETHODEN */

  /**
   * Prüft, ob die x-te Spalte leer ist.
   * @param x Der Spaltenindex des Brettes.
   * @return true, die x-te Spalte ist leer.
   */
  private boolean isEmptyCol(int x) {

    for (int y = 0; y < this.N; y++) {
      if (this.board[x][y]) {
        return false;
      }
    }

    return true;
  }

  /**
   * Prüft, ob die y-te Zeile leer ist.
   * @param y Der Zeilenindex des Brettes.
   * @return true, die y-te Zeile ist leer.
   */
  private boolean isEmptyRow(int y) {

    for (int x = 0; x < this.N; x++) {
      if (this.board[x][y]) {
        return false;
      }
    }

    return true;
  }

  /**
   * Prüft, ob die fallende Diagonale, die durch das Feld(x, y) führt,
   * leer ist.
   * @param x Der Spaltenindex des Brettes.
   * @param y Der Zeilenindex des Brettes.
   * @return true, die fallende Diagonale durch (x,y) ist leer.
   */
  private boolean isEmptyFalling(int x, int y) {

    int min = Math.min(x, y);
    x -= min;
    y -= min;

    while (Math.max(x, y) < this.N) {
      if (this.board[x][y]) {
        return false;
      }
      x++;
      y++;
    }

    return true;
  }

  /**
   * Prüft, ob die steigende Diagonale, die durch das Feld(x, y) führt,
   * leer ist.
   * @param x Der Spaltenindex des Brettes.
   * @param y Der Zeilenindex des Brettes.
   * @return true, die steigende Diagonale durch (x,y) ist leer.
   */
  private boolean isEmptyRising(int x, int y) {

    int min = Math.min(x, this.N - y - 1);
    x -= min;
    y += min;

    while (Math.max(x, this.N - y - 1) < this.N) {
      if (this.board[x][y]) {
        return false;
      }
      x++;
      y--;
    }

    return true;
  }

  /**
   * Prüft zwei Matrizen (this.board und matrix) auf Gleichheit.
   * Die Cardinalität der Matrizen muss übereinstimmen.
   * Diese Methode ist eine Hilfsmethode für isSameBoard.
   * @param matrix Die gegebene Matrix.
   * @return true, falls beide Matrizen deckungsgleich.
   */
  private boolean testEqualMatrix(boolean[][] matrix) {
    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        if (this.board[x][y] != matrix[x][y]) {
          return false;
        }
      }
    }
    return true;
  }

  /**
   * Rotiert gegebene NxN-Matrix um 90°.
   * Diese Methode ist eine Hilfsmethode für isSameBoard.
   * @param matrix Die quadratische NxN-Matrix.
   * @return Die rotierte NxN-Matrix.
   */
  private boolean[][] rotateMatrix(boolean[][] matrix) {
    boolean[][] result = new boolean[this.N][this.N];
    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        result[(this.N - 1) - y][x] = matrix[x][y];
      }
    }
    return result;
  }

  /**
   * Spiegelt gegebene NxN-Matrix an der Hauptdiagonalen.
   * Diese Methode ist eine Hilfsmethode für isSameBoard.
   * @param matrix Die quadratische NxN-Matrix.
   * @return Die gespiegelte NxN-Matrix.
   */
  private boolean[][] mirrorMatrix(boolean[][] matrix) {
    boolean[][] result = new boolean[this.N][this.N];
    for (int x = 0; x < this.N; x++) {
      for (int y = 0; y < this.N; y++) {
        result[y][x] = matrix[x][y];
      }
    }
    return result;
  }
}
```

nun hab ich eine bitte könnt ihr mir helfen und ich hab 2 glaub ich sehr dummer fragen
die 2Klassen müssen ja miteinader kommunizieren wie soll ich das am besten machen 
also am anfang mit import..... und weiter weiß ich nicht tut mir echt leid
und dann bräuchte ich die datei Iterator
wisst ihr woher ich sie bekomme?

danke


----------



## Marco13 (24. Jan 2010)

Beim Drüberschauen: Die Meldung kommt daher, dass Listen ohne Generics verwendet werden. (Kannst ja auch mal den Rat befolgen, und mit -Xlint compilieren).

Ganz pragmatisch: Überall dort, wo jetzt [c]LinkedList[/c] steht, sollte (wenn ich das richtig überfloagn habe) [c]LinkedList<BoardOfQueens2>[/c] stehen....


----------



## Landei (24. Jan 2010)

Hach, die acht Damen hatte ich neulich in meinem Blog zu Besuch, allerdings in Clean und in Scala: Wie funktional ist Scala?  eSCALAtion Blog

Als Datenstruktur für das Brett bietet sich eine Integer-Liste an, die für jede Reihe die Spalte enthält, in der die Dame steht. Dabei nutzt man natürlich aus, dass ein einer Reihe immer nur eine Dame stehen kann. Das vereinfacht die Sache ungemein...


----------



## Kubis (24. Jan 2010)

nun hab ich den tipp vom Marco13 befolgt aber nun bekomme ich folgende Fehlermeldung

D:\Users\Paul\Desktop\queentest\QueenProblem.java:92: cannot find symbol

symbol  : method add(java.lang.Object)

location: class java.util.LinkedList<Board>

        results.add(current.clone());

               ^


hoffe ihr könnt mir helfen


----------



## Landei (24. Jan 2010)

clone() liefert ein Object, aber du brauchst ein Board (und dass es eines ist, weißt du ja):

```
results.add((Board) current.clone());
```


----------

