import java.util.*;
/**
* Ein Objekt dieser Klasse repräsentiert ein MxN-Brett
* und vereinfacht den Algorithmus zum Springerproblem erheblich.
* Jedes Feld des Brettes repräsentiert eine Zugnummer eines Springerzuges.
*/
public class BoardOfKnightMoves implements Cloneable {
/**
* Die letzte Zugnummer eines Springerzuges.
*/
private int moveNumber;
/**
* Ein zweidimensionales Array, welches das MxN-Brett darstellt.
* Jedes Feld speichert die Zugnummer eines Springerzuges.
*/
private int[][] board;
/**
* Instantiiert ein MxN-Brett für das Springerproblem.
*/
public BoardOfKnightMoves() {
this.moveNumber = 0;
this.board = new int[BoardCoordinate.M][BoardCoordinate.N];
// Jedes einzelne Feld wird als noch nicht besucht gekennzeichnet.
for (int x = 0; x < BoardCoordinate.M; x++) {
for (int y = 0; y < BoardCoordinate.N; y++) {
this.board[x][y] = 0;
}
}
}
/**
* Erzeugt ein neues BoardOfKnightMoves und sichert darin den aktuellen
* Zustand der Objekt-Instanz.
* @return Eine Kopie des Objekts.
*/
public Object clone() {
BoardOfKnightMoves result = new BoardOfKnightMoves();
result.moveNumber = this.moveNumber;
for (int x = 0; x < BoardCoordinate.M; x++) {
for (int y = 0; y < BoardCoordinate.N; y++) {
result.board[x][y] = this.board[x][y];
}
}
return result;
}
/**
* Prüft, ob eine Lösung erreicht wurde.
* @return true, falls die Zugnummer größer oder gleich M*N.
*/
public boolean hasSolution() {
return this.moveNumber >= BoardCoordinate.M * BoardCoordinate.N;
}
/**
* Gibt die Liste aller möglichen Springerzüge von der Position(x,y) zurück.
* @param x Die Spalte.
* @param y Die Zeile.
* @return Die Zugliste.
*/
public LinkedList nextKnightMoves(int x, int y) {
LinkedList result = new LinkedList();
if (this.canMoveTo(x + 2, y + 1)) {
result.add(new BoardCoordinate(x + 2, y + 1));
}
if (this.canMoveTo(x + 1, y + 2)) {
result.add(new BoardCoordinate(x + 1, y + 2));
}
if (this.canMoveTo(x - 2, y + 1)) {
result.add(new BoardCoordinate(x - 2, y + 1));
}
if (this.canMoveTo(x - 1, y + 2)) {
result.add(new BoardCoordinate(x - 1, y + 2));
}
if (this.canMoveTo(x + 2, y - 1)) {
result.add(new BoardCoordinate(x + 2, y - 1));
}
if (this.canMoveTo(x + 1, y - 2)) {
result.add(new BoardCoordinate(x + 1, y - 2));
}
if (this.canMoveTo(x - 2, y - 1)) {
result.add(new BoardCoordinate(x - 2, y - 1));
}
if (this.canMoveTo(x - 1, y - 2)) {
result.add(new BoardCoordinate(x - 1, y - 2));
}
return result;
}
/**
* Gibt die Liste aller möglichen Springerzüge von der Position(coordinate)
* zurück.
* @param coordinate Die Position(x,y).
* @return Die Zugliste.
*/
public LinkedList nextKnightMoves(BoardCoordinate coordinate) {
return this.nextKnightMoves(coordinate.getX(), coordinate.getY());
}
/**
* Setzt einen Zug des Pferdes auf das Feld(x,y).
* @param x Die Spalte.
* @param y Die Zeile.
*/
public void setKnightMoveAt(int x, int y) {
this.moveNumber++;
this.board[x][y] = this.moveNumber;
}
/**
* Setzt einen Zug des Pferdes auf das Feld(coordinate).
* @param coordinate Die Position(x,y).
*/
public void setKnightMoveAt(BoardCoordinate coordinate) {
this.setKnightMoveAt(coordinate.getX(), coordinate.getY());
}
/**
* Nimmt einen Zug des Pferdes auf dem Feld(x,y) wieder zurück.
* @param x Die Spalte.
* @param y Die Zeile.
*/
public void unsetKnightMoveAt(int x, int y) {
this.board[x][y] = 0;
this.moveNumber--;
}
/**
* Nimmt einen Zug des Pferdes auf dem Feld(coordinate) wieder zurück.
* @param coordinate Die Position(x,y).
*/
public void unsetKnightMoveAt(BoardCoordinate coordinate) {
this.unsetKnightMoveAt(coordinate.getX(), coordinate.getY());
}
/**
* Gibt den aktuellen Zustand des MxN-Brettes in Form eines Diagramms zurück.
* @return Das Diagramm als Zeichenkette.
*/
public String toString() {
String result = "";
for (int y = 0; y < BoardCoordinate.N; y++) {
for (int x = 0; x < BoardCoordinate.M; x++) {
int number = this.board[x][y];
if (number <= 0) {
result += "| ";
} else if (number < 10) {
result += "| " + number;
} else {
result += "|" + number;
}
}
result += "|\r\n";
}
return result;
}
/* HILFSMETHODE */
/**
* Prüft, ob das Feld(x,y) auf dem Brett existiert und darauf noch
* kein Zug gespeichert wurde.
* @param x Die Spalte.
* @param y Die Zeile.
* @return true, falls das Feld(x,y) existiert und beziehbar ist.
*/
private boolean canMoveTo(int x, int y) {
return BoardCoordinate.inRange(x, y) && (this.board[x][y] <= 0);
}
} |
