/**
* Diese Klasse repräsentiert ein NxN-Brett, auf dem nur Damen stehen können
* und vereinfacht insbesondere den Algorithmus zum N-Damenproblem erheblich.
*/
public class BoardOfQueens 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 BoardOfQueens(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 BoardOfQueens-Instanz und sichert darin den aktuellen
* Zustand der aktuellen Objekt-Instanz.
* @return Eine Kopie des aktuellen Objekts.
*/
public Object clone() {
BoardOfQueens result = new BoardOfQueens(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;
}
/* 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;
}
} |
