001 package de.hska.java.aufgaben.backtracking;
002
003 /**
004 * Löst das Englische Solitär mit 32 Feldern und 31 Spielsteinen mit Hilfe
005 * von Backtracking.
006 * Die Lösung habe ich nicht komplett überprüft, sondern nur die ersten paar und letzten
007 * paar Schritte. Ich hoffe, die dazwischen sind auch richtig.
008 *
009 * <p>
010 * <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/backtracking.html#solitaer">
011 * Zurück zum Aufgabentext</a>
012 * </p>
013 * @author Christian Pape
014 *
015 */
016 public class Solitaer {
017
018 /**
019 * Das Spielfeld mit den Werten 1 = Stein, 2 = Leeres Feld und 0 = nicht benutztes Feld.
020 */
021 private SolitaerSpielfeld spielfeld = new SolitaerSpielfeld();
022
023 /**
024 * Die Lösung als Feld von Spielfeldern.
025 */
026 private SolitaerSpielfeld [] loesung = new SolitaerSpielfeld[32];
027
028 /**
029 * Enthält alle Richtungen für die 4 möglichen Sprünge.
030 */
031 private int [] richtungen = spielfeld.getRichtungen();
032
033 /**
034 * Erzeugt ein neues Solitaer mit "leerer" Lösung
035 * (Spielbretter haben alle die Startposition).
036 */
037 public Solitaer() {
038 for (int i = 0; i < loesung.length; i++) {
039 loesung[i] = new SolitaerSpielfeld();
040 }
041 }
042 /**
043 * Ruft den Lösungsalgoritmus auf und gibt die Lösung als
044 * Folge der einzelnen Spielergebnisse nach jedem Sprung aus.
045 */
046 public static void main(String[] args) {
047 Solitaer solitaer = new Solitaer();
048
049 long t1 = System.currentTimeMillis();
050 if (solitaer.sucheLoesung(1)) {
051 System.out.println("Lösung gefunden in " + (System.currentTimeMillis() - t1) + " [ms]");
052
053 solitaer.loesungAusgeben();
054 } else {
055 System.out.println("Keine Lösung gefunden - na so was!?");
056 }
057 }
058
059 /**
060 * Backtrackingalgorithmus für die Lösungssuche.
061 *
062 * @param zug erste Zugnummer, muss 1 sein
063 */
064 public boolean sucheLoesung(int zug) {
065 for (int x = 0; zug <= 31 && x < spielfeld.getBreite(); x++) {
066 for (int y = 0; y < spielfeld.getHoehe(); y++) {
067 for (int richtung : richtungen) {
068 if (spielfeld.springe(x, y, richtung)) {
069 spielfeld.kopiereSpielfeld(spielfeld, loesung[zug]);
070 if (! (zug >= 31 && spielfeld.isBesetzt(3, 3))) {
071 if ( sucheLoesung(zug + 1)) {
072 return true;
073 } else {
074 spielfeld.zurueckSpringen(x, y, richtung);
075 }
076 } else {
077 return true;
078 }
079 }
080 }
081 }
082 }
083
084 return false;
085 }
086
087 /**
088 * Gibt die Lösung als Folge von Spielbrettern am Bildschirm aus.
089 *
090 */
091 private void loesungAusgeben() {
092 for (int zug = 0; zug < loesung.length; zug++) {
093 loesung[zug].ausgeben();
094 }
095 }
096 }