001 package de.hska.java.aufgaben.backtracking;
002
003 import java.util.Arrays;
004 import java.util.HashSet;
005 import java.util.List;
006 import java.util.Set;
007
008 import com.sun.org.apache.xpath.internal.operations.And;
009
010 /**
011 * Sucht eine Lösung für das Sixtee-Puzzle mit rekursiven Backtracking.
012 *
013 * @author Christian Pape
014 */
015 public class SixteenPuzzle {
016
017 private static int KEIN_FELD = -1;
018 private static int LEERES_FELD = 0;
019 private static int ROT = 1;
020 private static int GRUEN = 2;
021
022 private int [] [] puzzle = {
023 {ROT, ROT, ROT, KEIN_FELD, KEIN_FELD},
024 {ROT, ROT, ROT, KEIN_FELD, KEIN_FELD},
025 {ROT, ROT, LEERES_FELD, GRUEN, GRUEN},
026 {KEIN_FELD, KEIN_FELD, GRUEN, GRUEN, GRUEN},
027 {KEIN_FELD, KEIN_FELD, GRUEN, GRUEN, GRUEN}
028 };
029
030 private Feld [] loesung;
031
032 private int maximum = 0;
033
034 public SixteenPuzzle(int maximaleAnzahlZuege) {
035 this.loesung = new Feld[maximaleAnzahlZuege];
036 }
037
038 public static void main(String [] argv) {
039
040 for (int zug = 50; zug < 51; zug++) {
041 SixteenPuzzle puzzle = new SixteenPuzzle(zug);
042
043 puzzle.print();
044 if (puzzle.sucheLoesung()) {
045 System.out.println("Lösung gefunden");
046 }
047 puzzle.print();
048 }
049
050 }
051
052 public boolean sucheLoesung() {
053 return sucheLoesung(new Feld(2,2), 0, 0);
054 }
055
056 private boolean sucheLoesung(Feld leeresFeld, int anzahlRotRechtsUnten, int zug) {
057 for (Feld feld : berechneMoeglicheZuege(leeresFeld)) {
058 int zusaetzlicherRoterSteinRechtsUnten = 0;
059 int zusaetzlicherGruenerSteinLinksOben = 0;
060 if (feld != null) {
061 int spielfarbe = puzzle[feld.getX()][feld.getY()];
062 if (spielfarbe == ROT) {
063 zusaetzlicherRoterSteinRechtsUnten = aenderungRoterSteineErmitteln(feld, leeresFeld);
064 } else {
065 zusaetzlicherGruenerSteinLinksOben = aenderungRoterSteineErmitteln(leeresFeld, feld);
066 }
067 // System.out.println("Zug: von " + feld + " nach " + leeresFeld + " (" + spielfarbe + " / " + zusaetzlicherRoterSteinRechtsUnten + " / " + anzahlRotRechtsUnten + ")" );
068 loesung[zug] = feld;
069 puzzle[leeresFeld.getX()][leeresFeld.getY()] = spielfarbe;
070 puzzle[feld.getX()][feld.getY()] = LEERES_FELD;
071 boolean zugOk = zusaetzlicherRoterSteinRechtsUnten != -1
072 && zusaetzlicherGruenerSteinLinksOben != - 1
073 && (zug / 8) <= anzahlRotRechtsUnten
074 && (zug <= 20 || puzzle[4][4] == ROT);
075 if (maximum < anzahlRotRechtsUnten + zusaetzlicherRoterSteinRechtsUnten) {
076 maximum = anzahlRotRechtsUnten + zusaetzlicherRoterSteinRechtsUnten;
077 System.out.println(maximum + " / " + zug);
078 print();
079 }
080 if (false && zugOk) {
081 System.out.println(zug + " : " + feld);
082 System.out.println("rote steine : " + (anzahlRotRechtsUnten + zusaetzlicherRoterSteinRechtsUnten));
083 print();
084 }
085 if ( anzahlRotRechtsUnten + zusaetzlicherRoterSteinRechtsUnten < 8
086 || ! (leeresFeld.getX() == 2 && leeresFeld.getY() == 2)) {
087 if ( zugOk && sucheLoesung(feld, anzahlRotRechtsUnten + zusaetzlicherRoterSteinRechtsUnten, zug + 1)) {
088 return true;
089 } else {
090 loesung[zug] = null;
091 puzzle[feld.getX()][feld.getY()] = spielfarbe;
092 puzzle[leeresFeld.getX()][leeresFeld.getY()] = LEERES_FELD;
093 }
094 } else {
095 return true;
096 }
097 }
098 }
099 return false;
100 }
101
102 private Feld [] berechneMoeglicheZuege(Feld leeresFeld) {
103 Feld [] zuege = new Feld[8];
104
105 for (int i = 0; i < 8; i++) {
106 zuege[i] = naechstenZugErmitteln(leeresFeld, i);
107 }
108 Arrays.sort(zuege);
109
110 return zuege;
111 }
112
113
114 /**
115 * Stellte fest, ob im rechten unteren Bereich durch den Zug
116 * von feld nach leeresFeld ein roter Stein in diesen Bereich hineinkommt (+1)
117 * oder wieder weggenommen wird (-1).
118 *
119 * @param feld Feld, von dem der rote(!) Spielstein kommt
120 * @param leeresFeld Feld, in das hineingezogen wird
121 *
122 * @return +1,0,-1 ja nachdem, wie sich die Anzahl roter Steine im rechten unteren
123 * Spielfeld geändert hat
124 */
125 private int aenderungRoterSteineErmitteln(Feld feld, Feld leeresFeld) {
126 int anzahl = 0;
127
128 if ( inRechtenUnterenBereichVerschoben(feld, leeresFeld) ) {
129 anzahl = 1;
130 } else if ( inRechtenUnterenBereichVerschoben(leeresFeld, feld) ) {
131 // das leere Feld "wandert" vom linken oberen in den rechten
132 // unteren Bereich und damit der Stein zurück in den
133 // linken oberen Bereich
134 anzahl = -1;
135 }
136
137 return anzahl;
138 }
139
140 private boolean inRechtenUnterenBereichVerschoben(Feld von, Feld nach) {
141 return ( (von.getX() <= 1 && von.getY() <= 2)
142 || (von.getX() <= 2 && von.getY() <= 1))
143 && nach.getX() >= 2 && nach.getY() >= 2;
144 }
145
146 private Feld naechstenZugErmitteln(Feld leeresFeld, int i) {
147 Feld feld = null;
148 int x = leeresFeld.getX();
149 int y = leeresFeld.getY();
150 // Sprünge werden bevorzugt
151 switch (i) {
152 case 0: x += 2;
153 break;
154 case 1: y += 2;
155 break;
156 case 2: x -= 2;
157 break;
158 case 3: y -= 2;
159 break;
160 case 4: x++;
161 break;
162 case 5: y++;
163 break;
164 case 6: x--;
165 break;
166 case 7: y--;
167 break;
168 }
169
170 if (0 <= x && x < puzzle.length
171 && 0 <= y && y < puzzle.length
172 && puzzle[x][y] != KEIN_FELD) {
173 feld = new Feld(x,y);
174 }
175
176 return feld;
177 }
178
179 private void print() {
180 for (int y = 0; y < puzzle.length; y++) {
181 for (int x = 0; x < puzzle.length; x++) {
182 System.out.print(puzzle[x][y] + "\t");
183 }
184 System.out.println();
185 }
186 }
187 private class Feld {
188 private int x;
189 private int y;
190
191 public Feld(int x, int y) {
192 this.x = x;
193 this.y = y;
194 }
195
196 public int getX() {
197 return x;
198 }
199
200 public int getY() {
201 return y;
202 }
203
204 public String toString() {
205 return x + "/" + y;
206 }
207
208 }
209
210 private class Sprung implements Comparable<Sprung> {
211
212 private Feld von;
213 private Feld nach;
214
215 public Sprung(Feld von, Feld nach) {
216 this.von = von;
217 this.nach = nach;
218 }
219
220 private int getDistanz() {
221 return nach.x - von.x + nach.y - von.y;
222 }
223 public int compareTo(Sprung sprung) {
224 if (puzzle[sprung.von.x][sprung.von.y] == ROT) {
225 return sprung.getDistanz() - getDistanz();
226 }
227 return getDistanz() - sprung.getDistanz();
228 }
229 }
230
231 }