Vorliegende Implementierung spezialisiert die Implementierung des
N-Damenproblems
nur geringfügig:
- QueenProblem2.java
Die private Methode
solve
wird dahin gehend geändert,
dass kongruent ähnliche Lösungen nicht in die bereits vorhandene Lösungsmenge aufgenommen werden.
- BoardOfQueens2.java
wird um die Vergleichsoperation
isSameBoard(other)
erweitert,
welche es ermöglicht, zwei Bretter auf kongruente Ähnlichkeit zu prüfen.
Aus Gründen, die die Übersichtlichkeit betreffen, benötigt diese Vergleichsoperation folgende Hilfsmethoden:
testEqualMatrix, rotateMatrix
und
mirrorMatrix.
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());
}
}
}
}
/**
* 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;
}
}