Startseite
Informatik
Algorithmen
Sortieren
Komprimieren
Suchen
Damenproblem
DRUCK
2004
2005
2006
2007
2008
2009
Springerproblem
Solitaire
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
Springerproblem
Ein Springer besucht jedes Feld auf dem Schachbrett genau ein Mal.
Ein Springer besucht jedes Feld auf dem Schachbrett genau ein Mal.
Einführung
Theorie: Springerproblem
Definition
Springerproblem:
Die Springerfigur eines Schachspiels wird auf ein beliebiges Feld eines Schachbretts gestellt.
Gesucht wird eine Zugfolge, bei der der Springer entsprechend seiner Bewegungsmöglichkeit im Schach nacheinander alle Felder
des Schachbrettes, jedes Feld genau einmal, besetzt.
[INFODUDEN S. 682ff]
Die Gangart des Springers im Schachspiel finden Sie unter Schachregeln.
Die Gangart des Springers im Schachspiel finden Sie unter Schachregeln.
Der Algorithums
… zum Springerproblem lässt sich auf ein Suchproblem zurückführen:
eine
Tiefensuche
(Backtracking).
Die Rekursionstiefe liegt bei maximal 64, da es 64 Felder auf dem Schachbrett gibt, die der Springer besuchen kann.
Der Branchingfaktor liegt zwischen 2 und 8, der im Eck stehende Springer hat maximal 2 Zugmöglichkeiten und der zentral stehende Springer hat bis zu 8 Zugmöglichkeiten.
Die Rekursionstiefe liegt bei maximal 64, da es 64 Felder auf dem Schachbrett gibt, die der Springer besuchen kann.
Der Branchingfaktor liegt zwischen 2 und 8, der im Eck stehende Springer hat maximal 2 Zugmöglichkeiten und der zentral stehende Springer hat bis zu 8 Zugmöglichkeiten.
Beispiele
Im Folgenden seien nur mal zwei Lösungen zum Springerproblem mit dem Startpunkt
a1
gezeigt:
Eine Lösung zum Springerproblem
|46|39|28|43|60|55|64|53|
|27|42|45|50|29|52|61|56|
|38|47|40|59|44|63|54|15|
|41|26|49|30|51|16|57|62|
|48|37|24|17|58|21|14| 5|
|25|34|31|22|13| 6| 9|20|
|36|23| 2|33|18|11| 4| 7|
| 1|32|35|12| 3| 8|19|10|
Eine weitere Lösung zum Springerproblem
|62|43|58|53|60|37|48|39|
|57|54|61|42|47|40|51|36|
|44|63|56|59|52|49|38|15|
|55|28|33|46|41|16|35|50|
|64|45|24|17|34|21|14| 5|
|27|32|29|22|13| 6| 9|20|
|30|23| 2|25|18|11| 4| 7|
| 1|26|31|12| 3| 8|19|10|
Implementierung
Implementierung: Springerproblem
Implementierung mit Java
Folgende Realisierung in Java zur Lösung des Springerproblems besteht aus drei Dateien:
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
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
- KnightProblem.java implementiert den Algorithmus zum Springerproblem und enthält das Hauptprogramm.
- BoardCoordinate.java
implementiert eine gültige Schachkoordinate wie zum Beispiel
a1oder c2. In dieser Datei wird festgelegt welche Ausmaße das zugrundeliegende Brett hat, hier ein4x5-Brett. - BoardOfKnightMoves.java
implementiert ein
MxN-Brett,das zu jedem Feld die Zugnummer des Springers speichert.
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.
:-(
knightproblem.java
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();
}
}
}
}
BoardCoordinate.java
/**
* 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;
}
}
BoardOfKnightMoves.java
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);
}
}
Ergebnisse
Ergebnisse zum Springerproblem
Um Lösungen zum o. a. Algorithmus zu erhalten, muss das Hauptprogramm mit den entsprechenden Parametern ausgeführt werden.
Hierzu ein Beispiel:
C:\> java KnightProblem a1
sucht nach allen Lösungen des Springerproblems ausgehend von der Position a1 (Startposition).
java KnightProblem a1 a2 a3 b1 b2 b3
Start(a1) -> 32 Result(s)
| 5|10|15|20|
|14|19| 6| 3|
| 9| 4|11|16|
|18|13| 2| 7|
| 1| 8|17|12|
| 5|10|17|12|
|18|13| 6| 3|
| 9| 4|11|16|
|14|19| 2| 7|
| 1| 8|15|20|
| 9| 4|19|14|
|20|15|10| 3|
| 5| 8|13|18|
|16|11| 2| 7|
| 1| 6|17|12|
| 9| 4|15|20|
|14|19|10| 3|
| 5| 8|13|16|
|18|11| 2| 7|
| 1| 6|17|12|
| 9| 4|13|18|
|12|17|10| 3|
| 5| 8|19|14|
|16|11| 2| 7|
| 1| 6|15|20|
| 9| 4|13|20|
|14|19| 8| 3|
| 5|10|17|12|
|18|15| 2| 7|
| 1| 6|11|16|
| 9| 4|13|18|
|14|19| 8| 3|
| 5|10|17|12|
|20|15| 2| 7|
| 1| 6|11|16|
| 9| 4|17|20|
|16|19| 8| 3|
| 5|10|13|18|
|12|15| 2| 7|
| 1| 6|11|14|
| 9| 4|17|14|
|18|15| 8| 3|
| 5|10|13|16|
|12|19| 2| 7|
| 1| 6|11|20|
| 9| 4|15|20|
|16|13| 8| 3|
| 5|10|19|14|
|12|17| 2| 7|
| 1| 6|11|18|
| 9| 4|19|14|
|20|13| 8| 3|
| 5|10|15|18|
|12|17| 2| 7|
| 1| 6|11|16|
| 9| 4|19|14|
|18|13| 8| 3|
| 5|10|15|20|
|12|17| 2| 7|
| 1| 6|11|16|
| 9| 4|17|14|
|16|13| 8| 3|
| 5|10|15|18|
|12|19| 2| 7|
| 1| 6|11|20|
| 9| 4|11|16|
|20|15| 8| 3|
| 5|10|17|12|
|14|19| 2| 7|
| 1| 6|13|18|
| 9| 4|11|16|
|18|15| 8| 3|
| 5|10|17|12|
|14|19| 2| 7|
| 1| 6|13|20|
| 9| 4|11|20|
|12|19| 8| 3|
| 5|10|13|16|
|18|15| 2| 7|
| 1| 6|17|14|
| 9| 4|11|14|
|12|15| 8| 3|
| 5|10|13|18|
|16|19| 2| 7|
| 1| 6|17|20|
| 9| 4|11|20|
|12|19| 8| 3|
| 5|10|15|18|
|16|13| 2| 7|
| 1| 6|17|14|
| 9| 4|11|16|
|12|17| 8| 3|
| 5|10|15|18|
|20|13| 2| 7|
| 1| 6|19|14|
| 9| 4|11|16|
|12|17| 8| 3|
| 5|10|15|20|
|18|13| 2| 7|
| 1| 6|19|14|
| 9| 4|11|18|
|12|17| 8| 3|
| 5|10|19|14|
|16|13| 2| 7|
| 1| 6|15|20|
| 7| 4|15|20|
|14|19| 6| 3|
| 5| 8|11|16|
|18|13| 2| 9|
| 1|10|17|12|
| 7| 4|17|12|
|18|13| 6| 3|
| 5| 8|11|16|
|14|19| 2| 9|
| 1|10|15|20|
| 7|10|15|20|
|14|19| 6| 9|
| 3| 8|11|16|
|18|13| 2| 5|
| 1| 4|17|12|
| 7|10|17|12|
|18|13| 6| 9|
| 3| 8|11|16|
|14|19| 2| 5|
| 1| 4|15|20|
| 7| 4|15|20|
|14|19| 8| 5|
| 3| 6|11|16|
|18|13| 2| 9|
| 1|10|17|12|
| 7| 4|17|12|
|18|13| 8| 5|
| 3| 6|11|16|
|14|19| 2| 9|
| 1|10|15|20|
| 3|10|15|20|
|14|19| 4| 9|
| 7| 2|11|16|
|18|13| 8| 5|
| 1| 6|17|12|
| 3|10|17|12|
|18|13| 4| 9|
| 7| 2|11|16|
|14|19| 8| 5|
| 1| 6|15|20|
| 3| 8|15|20|
|16|11| 4| 9|
| 7| 2|19|14|
|12|17|10| 5|
| 1| 6|13|18|
| 3| 8|17|12|
|16|11| 4| 9|
| 7| 2|13|18|
|20|15|10| 5|
| 1| 6|19|14|
| 3| 8|17|12|
|18|11| 4| 9|
| 7| 2|13|16|
|14|19|10| 5|
| 1| 6|15|20|
Start(a2) -> 7 Result(s)
|20|15|10| 5|
| 9| 4|19|14|
|16|11| 6| 3|
| 1| 8|13|18|
|12|17| 2| 7|
|12|17|10| 5|
| 9| 4|13|18|
|16|11| 6| 3|
| 1| 8|19|14|
|20|15| 2| 7|
|20|15| 4| 9|
| 5|10|19|14|
|16|13| 8| 3|
| 1| 6|11|18|
|12|17| 2| 7|
|14|19| 4| 9|
| 5|10|15|20|
|18|13| 8| 3|
| 1| 6|11|16|
|12|17| 2| 7|
|18|13| 4| 9|
| 5|10|17|12|
|14|19| 8| 3|
| 1| 6|11|16|
|20|15| 2| 7|
|20|15| 8| 3|
| 7| 2|19|14|
|16|11| 4| 9|
| 1| 6|13|18|
|12|17|10| 5|
|12|17| 8| 3|
| 7| 2|13|18|
|16|11| 4| 9|
| 1| 6|19|14|
|20|15|10| 5|
Start(a3) -> 4 Result(s)
| 5|10|15|20|
|14|19| 4| 9|
| 1| 6|11|16|
|18|13| 8| 3|
| 7| 2|17|12|
| 5|10|17|12|
|18|13| 4| 9|
| 1| 6|11|16|
|14|19| 8| 3|
| 7| 2|15|20|
| 7| 2|15|20|
|14|19| 8| 3|
| 1| 6|11|16|
|18|13| 4| 9|
| 5|10|17|12|
| 7| 2|17|12|
|18|13| 8| 3|
| 1| 6|11|16|
|14|19| 4| 9|
| 5|10|15|20|
Start(b1) -> no Results
Start(b2) -> no Results
Start(b3) -> no Results
Quellenangabe
-
[INFODUDEN]