001 package de.hska.info1.backtracking.springer;
002
003 /**
004 * Findet eine Springer-Tour für ein n mal n
005 * Schachbrett.
006 *
007 * @author Christian Pape
008 */
009 public class SpringerProblem {
010
011 /**
012 * Das Schachbrett mit der später gefundenen Lösung
013 * als durchnumerierte Zugreihenfolge.
014 */
015 private int [] [] schachbrett = new int[0][0];
016
017 /**
018 * Enthält die Sprungweiten für die x und y Richtung
019 * aller 8 möglichen Springerzüge.
020 */
021 private int [] [] sprungweite = {
022 {1, -2},
023 {2, -1},
024 {2, 1},
025 {1, 2},
026 {-1, 2},
027 {-2, 1},
028 {-2, -1},
029 {-1, -2}
030 };
031
032 /**
033 * Erzeugt ein neues SpringerProblem für ein
034 * n mal n Schachbrett.
035 *
036 * @param n eine positive ganze Zahl
037 */
038 public SpringerProblem(int n) {
039 schachbrett = new int[n][n];
040 }
041
042 /**
043 * Sucht eine Springer-Tour ab dem gegeben
044 * Feld (x,y) und gibt <code>true</code> zurück,
045 * wenn eine Lösung gefunden wurde.
046 */
047 private boolean sucheSpringerTour(int x, int y, int zugNummer) {
048 schachbrett[x][y] = zugNummer;
049 if (zugNummer < schachbrett.length * schachbrett.length) {
050 for (int i = 0; i <= 7; i++) {
051 int neuesX = x + sprungweite[i][0];
052 int neuesY = y + sprungweite[i][1];
053
054 if (isSchrittSinnvoll(neuesX, neuesY)) {
055 if (sucheSpringerTour(neuesX, neuesY, zugNummer + 1)) {
056 return true;
057 } else {
058 schachbrett[neuesX][neuesY] = 0;
059 }
060 }
061 }
062 return false;
063 } else {
064 return true;
065 }
066 }
067
068 /**
069 * Überprüft, ob er Springer zu diesem Feld springen darf.
070 */
071 private boolean isSchrittSinnvoll(int neuesX, int neuesY) {
072 return 0 <= neuesY && neuesY < schachbrett.length
073 && 0 <= neuesX && neuesX < schachbrett[neuesY].length
074 && schachbrett[neuesX][neuesY] == 0;
075 }
076
077 /**
078 * Gibt den Inhalt des Schachbretts auf dem
079 * Bildschirm aus.
080 */
081 public void printSchachbrett() {
082 for (int [] zeile : schachbrett) {
083 for (int zelle : zeile) {
084 System.out.print(zelle + "\t");
085 }
086 System.out.println();
087 }
088 System.out.println();
089 }
090
091 public static void main(String [] argv) {
092
093 for (int n = 5; n <= 8; n++) {
094 SpringerProblem problem = new SpringerProblem(n);
095 if (problem.sucheSpringerTour(0, 0, 1)) {
096 System.out.println("Lösung gefunden (n=" + n + "):");
097 }
098 problem.printSchachbrett();
099 }
100 }
101 }