Folgende Realisierung in Java zur Lösung des Springerproblems besteht aus drei Dateien:
- KnightProblem.java
implementiert den Algorithmus zum Springerproblem
und enthält das Hauptprogramm.
- BoardCoordinate.java
implementiert eine gültige Schachkoordinate wie zum Beispiel
a1
oder
c2.
In dieser Datei wird festgelegt welche Ausmaße das zugrundeliegende Brett hat, hier ein
4x5-Brett.
- BoardOfKnightMoves.java
implementiert ein
MxN-Brett,
das zu jedem Feld die Zugnummer des Springers speichert.
Da hier das Brett und der Algorithmus getrennt implementiert sind,
wird der Algorithmus übersichtlicher.
Zum Springerproblem bzgl. eines Schachbrettes gibt des sehr viele Lösungen
(so ziemlich viele Milliarden Lösungen),
deshalb sei hier das Springerproblem nur mit einem
4x5-Brett
demonstriert.
Falls Sie dennoch das zugrundliegende Brett auf Schachbrettgröße vergrößern sollten,
so ist es ratsam den unten angegebenen Algorithmus leicht zu modifizieren.
Ihr Arbeitsspeicher würde sonst von einer gigantisch großen Lösungsmenge erschlagen werden.
Geben Sie also die Lösungen direkt auf den Bildschirm oder auf ein entsprechend großes Speichermedium aus.
Wenn Sie allerdings die Lösungen nur zählen möchten, dann sollten Sie die Klasse
BigInteger
verwenden
(Bereichsüberlauf),
denn es sind wie bereits erwähnt sehr viele Lösungen,
die ein herkömmlicher Integer möglicherweise nicht fassen kann.
Zudem sollten Sie viel Zeit mitbringen
— viel Rechenzeit —
denn,
wieviel Lösungen auf einem Schachbrett zu diesem Problem zustandekommen werden,
kann
ich
leider nicht gut genug abschätzen.
:-(
import java.util.*;
/**
* Der Algorithmus zum Springerproblem.
*/
public class KnightProblem {
/**
* Findet alle Lösungen zum Springerproblem bzgl. der Startkoordinate start.
* @param start Die Startkoordinate
* @return Die Lösungsliste.
*/
public static LinkedList solve(BoardCoordinate start) {
LinkedList boards = new LinkedList();
BoardOfKnightMoves emptyboard = new BoardOfKnightMoves();
solve(boards, emptyboard, start); // Startschuss!
return boards; // Alle Lösungen als Liste zurückgeben!
}
/**
* Findet alle Lösungen zum Springerproblem bzgl. des aktuellen MxN-Brettes
* und der Zugkoordinate des nächsten Zuges.
* @param results Die Lösungsliste.
* @param current Das aktuelle MxN-Brett.
* @param coordinate Die Brett-Koordinate des nächsten Zuges.
*/
private static void solve(LinkedList results, BoardOfKnightMoves current,
BoardCoordinate coordinate) {
current.setKnightMoveAt(coordinate);
if (current.hasSolution()) {
// Lösung wird der Lösungsliste hinzugefügt.
results.add(current.clone());
} else {
// Nur die möglichen Folgezüge
LinkedList nextMoves = current.nextKnightMoves(coordinate);
Iterator iter = nextMoves.listIterator();
while (iter.hasNext()) {
solve(results, current, (BoardCoordinate)iter.next());
}
}
current.unsetKnightMoveAt(coordinate);
}
/**
* Das Hauptprogramm, welches nach einer Lösung bzgl. des Springerproblems
* sucht.
* Diese statische Methode interpretiert jedes einzelne Argument als
* Schachkoordinate.
* @param arguments Die Argumente der Konsole, erlaubt sind nur
* Schachkoordinaten wie z.B. a1, c7 oder h2.
*/
public static void main(String[] arguments) {
for (int i = 0; i < arguments.length; i++) {
if (BoardCoordinate.inRange(arguments[i])) {
LinkedList results = solve(new BoardCoordinate(arguments[i]));
System.out.print("Start(" + arguments[i] + ") -> ");
if (results.size() > 0) {
System.out.println(results.size() + " Result(s)");
} else {
System.out.println("no Results");
}
System.out.println();
Iterator iter = results.listIterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
} else {
System.out.println("Bad Argument: '" + arguments[i] + "'");
System.out.println();
}
}
}
}
/**
* Ein Objekt dieser Klasse repräsentiert eine gültige Koordinate eines
* MxN-Brettes.
* Möchte man das Springerproblem bzgl. des Schachbrettes lösen,
* dann müssen die Attribute M und N, jeweils auf 8 gesetzt werden.
*/
public class BoardCoordinate {
/**
* Die Anzahl der Spalten.
*/
public static final int M = 4; // 1 bis 9
/**
* Die Anzahl der Zeilen.
*/
public static final int N = 5; // 1 bis 9
/**
* Spalten-Zeichen zur Konvertierung einer üblichen Schachkoordinate.
*/
private static final String xList = "abcdefghi";
/**
* Zeilen-Nummern zur Konvertierung einer üblichen Schachkoordinate.
*/
private static final String yList = "123456789";
/**
* Die Spaltennummer.
*/
private int x;
/**
* Die Zeilennummer.
*/
private int y;
/**
* Instanziiert eine Brett-Koordinate.
* @param x Die Spaltennummer.
* @param y Die Zeilennummer.
*/
public BoardCoordinate(int x, int y) {
if (inRange(x, y)) {
this.x = x;
this.y = y;
} else {
this.x = 0;
this.y = 0;
}
}
/**
* Instanziiert eine Brett-Koordinate.
* @param coordinate Übliche Schachkoordinate wie z.B. a1, a5, b3, oder h8.
* i9 ist auch möglich, falls M = 9 und N = 9.
*/
public BoardCoordinate(String coordinate) {
this(0, 0);
if (inRange(coordinate)) {
char xChar = coordinate.charAt(0);
this.x = xList.indexOf(xChar + "");
char yChar = coordinate.charAt(1);
this.y = (N - 1) - yList.indexOf(yChar + "");
}
}
/**
* Prüft, ob die Position(x,y) auf dem Brett existiert.
* @param x Die Spaltennummer.
* @param y Die Zeilennummer.
* @return true, falls Koordinate existiert.
*/
public static boolean inRange(int x, int y) {
return (x >= 0) && (x < M) && (y >= 0) && (y < N);
}
/**
* Prüft, ob die Position(coordinate) auf dem Brett existiert.
* @param coorinate Die Brett-Koordinate.
* @return true, falls Koordinate existiert.
*/
public static boolean inRange(String coordinate) {
if (coordinate.length() == 2) {
char xChar = coordinate.charAt(0);
char yChar = coordinate.charAt(1);
return inRange(xList.indexOf(xChar + ""), yList.indexOf(yChar + ""));
} else {
return false;
}
}
/**
* Gibt die Spaltennummer zurück.
* @return Die Spaltennummer.
*/
public int getX() {
return this.x;
}
/**
* Gibt die Zeilennummer zurück.
* @return Die Zeilennummer.
*/
public int getY() {
return this.y;
}
}
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);
}
}