001 package de.hska.info1.klausur.ss07;
002
003 /**
004 * Lösungen für die Klausuraufgabe zum Magischen Quadrat.
005 *
006 * @author Christian Pape
007 */
008 public class MagischesQuadrat {
009
010 /**
011 * Eine quadratische Matrix mit den Werten des Magischen Quadrats.
012 */
013 private int [] [] quadrat = null;
014
015 /**
016 * Für jede Zahl z ist <code>zahlIstVerwendet[z]</code> genau dann, true
017 * wenn z im partiell erzeugten Magischen Quadrat vorhanden ist.
018 */
019 private boolean [] zahlIstVerwendet;
020
021 /**
022 * Summe zeile und spalten, die ein magisches Quadrat in jeder Zeile und Summe haben muss.
023 */
024 private int summe;
025
026 public MagischesQuadrat(int [] [] quadrat) {
027 this.quadrat = quadrat;
028 this.zahlIstVerwendet = new boolean[quadrat.length * quadrat.length + 1];
029 this.summe = (quadrat.length * quadrat.length * quadrat.length + quadrat.length) / 2;
030 }
031
032 /**
033 * Gibt für die <code>zeile</code> die Summe aller darin enthaltenen
034 * Werte zurück.
035 * Iterative Lösung.
036 */
037 private int getZeilenSumme(int zeile) {
038 int summe = 0;
039
040 for (int wert : quadrat[zeile]) {
041 summe += wert;
042 }
043
044 return summe;
045 }
046
047
048 /**
049 * Nicht rekursive Lösung, um die Summe aller Zahlen in einer Spalte
050 * zu berechnen. Diese wird statt der rekursiven in den unteren
051 * Algorithmen verwendet, da sie etwas schneller ist (bzw. sein sollte).
052 */
053 private int getSpaltenSumme(int spalte) {
054 int summe = 0;
055
056 for (int zeile = 0; zeile < quadrat.length; zeile++) {
057 summe += quadrat[zeile][spalte];
058 }
059
060 return summe;
061 }
062
063 /**
064 * Gibt für die <code>spalte</code> die Summe aller darin enthaltenen
065 * Werte zurück.
066 */
067 private int getSpaltenSumme1(int spalte) {
068 return getSpaltenSummeRekursiv(spalte, 0);
069 }
070
071 /**
072 * Gibt für die <code>spalte</code> die Summe aller darin enthaltenen
073 * Werte zurück. Lösung mit linearer Rekursion - analog zur Rechnerübung
074 * (rekursive Minimumsuche).
075 */
076 private int getSpaltenSummeRekursiv(int spalte, int zeile) {
077 if (zeile >= quadrat.length) {
078 return 0;
079 } else {
080 return quadrat[zeile][spalte] + getSpaltenSummeRekursiv(spalte, zeile + 1);
081 }
082 }
083
084 /**
085 * Gibt genau dann true zurück, wenn <code>quadrat</code> ein Magisches Quadrat ist.
086 */
087 public boolean isMagischesQuadrat() {
088 int summe = getZeilenSumme(0);
089
090 // Prüfe, ob alle anderen Spalten und Zeilen, die selbe Summe besitzen
091 // Wenn nicht, wird false zurückgegebe
092 for (int i = 0; i < quadrat.length; i++) {
093 if (summe != getZeilenSumme(i) || summe != getSpaltenSumme(i)) {
094 return false;
095 }
096 }
097
098 // Initialisierung, um die Verwendung jeder Zahl von 1 bis n * n zu prüfen
099 for (int i = 0; i < zahlIstVerwendet.length; i++) {
100 zahlIstVerwendet[i] = false;
101 }
102
103
104 // Testet, ob eine Zahl mehrfach vorkommt
105 // Wenn eine Zahl doppelt vorkommt, wird false zurückgegeben
106 for (int zeile = 0; zeile < quadrat.length; zeile++) {
107 for (int spalte = 0; spalte < quadrat.length; spalte++) {
108 if ( zahlIstVerwendet[quadrat[zeile][spalte]] ) {
109 return false;
110 } else {
111 zahlIstVerwendet[quadrat[zeile][spalte]] = true;
112 }
113 }
114 }
115
116 // Setzt die Werte wieder auf false, da es in erzeugeMagischesQuadrat1/2
117 // zur optimierten Suche dieses Feld auch verwendet wird
118 for (int i = 0; i < zahlIstVerwendet.length; i++) {
119 zahlIstVerwendet[i] = false;
120 }
121
122 return true;
123 }
124
125 /**
126 * Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
127 * Dies wäre die einfachste Lösung für die Klausur. Allerdings auch sehr langsam.
128 * Dauert bei n = 3 ein paar Sekunden.
129 * Dies liegt an zwei Dingen:
130 * <ul>
131 * <li>isMagischesQuadrat() wird immer wieder berechnet mit O(n<sup>2</sup>) Aufwand
132 * im schlimmsten Fall</li>
133 * <li>Es werden Zahlen in eine Zelle gesetzt, obwohl sie schon im Quadrat vorhanden sind.</li>
134 * </ul>
135 */
136 public boolean erzeugeMagischesQuadratKlausur(int zelle) {
137 int zeile = zelle / quadrat.length;
138 int spalte = zelle % quadrat.length;
139
140 for (int wert = 1; zelle < quadrat.length * quadrat.length
141 && wert <= quadrat.length * quadrat.length ; wert++) {
142 quadrat[zeile][spalte] = wert; //
143 if (true) {
144 if (true && ! isMagischesQuadrat()) {
145 if ( erzeugeMagischesQuadrat1(zelle + 1)) {
146 return true;
147 } else {
148 // nix zu tun, es wird die nächste Zahl probiert
149 }
150 } else {
151 return true;
152 }
153 }
154 }
155
156 return false;
157 }
158
159
160 /**
161 * Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
162 * Anders als bei der vorangehenden Version, wird isMagischesQuadrat() nur noch
163 * berechnet, wenn wir alle Zellen "voll" haben, aber
164 * beim Schritt wird nicht überprüft, ob die Zahl schon mal verwendet wurde.
165 * Sie ist nur für 3 x 3 Quadrate praktikabel. Es dauert spürbar Sekundenbruchteile, ist
166 * aber ca. 5-10 schneller als obige Variante.
167 */
168 public boolean erzeugeMagischesQuadrat(int zelle) {
169 int zeile = zelle / quadrat.length; //
170 int spalte = zelle % quadrat.length; //
171 for (int wert = 1; zelle < quadrat.length * quadrat.length
172 && wert <= quadrat.length * quadrat.length ; wert++) {
173 quadrat[zeile][spalte] = wert; //
174 if (true) {
175 if (zelle < quadrat.length * quadrat.length - 1 || ! isMagischesQuadrat()) {
176 if ( erzeugeMagischesQuadrat1(zelle + 1)) {
177 return true;
178 } else {
179 // nix zu tun, es wird die nächste Zahl probiert
180 }
181 } else {
182 return true;
183 }
184 }
185 }
186
187 return false;
188 }
189
190 /**
191 * Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
192 * Es ist eine optimierte Version, die bei jedem Schritt prüft, ob die Zahl
193 * bereits verwendet wurde. Sie ist trotz dieser Optimierung nur für 3 x 3 Quadrate praktikabel,
194 * allerdings im geringen Millisekundenbereich.
195 */
196 public boolean erzeugeMagischesQuadrat1(int zelle) {
197 int zeile = zelle / quadrat.length;
198 int spalte = zelle % quadrat.length;
199 for (int wert = 1; zelle < quadrat.length * quadrat.length
200 && wert <= quadrat.length * quadrat.length ; wert++) {
201 quadrat[zeile][spalte] = wert;
202 if (! zahlIstVerwendet[wert]) {
203 zahlIstVerwendet[wert] = true;
204 if (zelle < quadrat.length * quadrat.length - 1 || ! isMagischesQuadrat()) {
205 if ( erzeugeMagischesQuadrat(zelle + 1)) {
206 return true;
207 } else {
208 zahlIstVerwendet[wert] = false; //
209 }
210 } else {
211 return true;
212 }
213 }
214 }
215
216 return false;
217 }
218
219
220 /**
221 * Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
222 * Es ist eine optimierte Version, bei der:
223 * <ul>
224 * <li>in jedem Schritt geprüft wird, ob die Zahl
225 * bereits verwendet wurde und </li>
226 * <li>ob die Summe einer neu erzeugten Zeile eine Mindestgrösse hat</li>
227 * </ul>
228 * Da der grösste Wert n * n - 1 auftreten muss und die nächst kleineren
229 * 1, 2, ... n - 1 sind, muss die Summe einer Spalte und Zeile mindestens
230 * 1 + 2 + ... + n - 1 + n*n - 1 = (n-1)n / 2 + n*n - 1 sein.
231 * Bei n = 3: 1 + 2 + 9 = 12.
232 * Bei n = 4: 1 + 2 + 3 + 16 = 22.
233 * Aber auch dies reicht nicht aus. Man kann allerdings zeigen,
234 * dass die Summe eines n x n Magischen Quadrats für n > 2 immer
235 * (n<sup>3</sup> + n) / 2 sein muss.
236 * Dann funktioniert es auch mit n = 4.
237 * Bei grösseren n dauert es aber wieder zu lang.
238 * Backtracking ist zur Erzeugung Magischer Quadrate also eher ungeeignet.
239 */
240 public boolean erzeugeMagischesQuadrat2(int zelle) {
241 int zeile = zelle / quadrat.length;
242 int spalte = zelle % quadrat.length;
243 for (int wert = 1; zelle < quadrat.length * quadrat.length
244 && wert <= quadrat.length * quadrat.length ; wert++) {
245 quadrat[zeile][spalte] = wert;
246 if (! zahlIstVerwendet[wert] && spalte < quadrat.length - 1 || getZeilenSumme(zeile) == summe
247 // Wenn letzte Zeile erreicht ist, prüfe dies auch bei der Spalte
248 && (zeile < quadrat.length - 1 || getSpaltenSumme(spalte) == summe)) {
249 zahlIstVerwendet[wert] = true;
250 if (zelle < quadrat.length * quadrat.length - 1 || ! isMagischesQuadrat()) {
251 if ( erzeugeMagischesQuadrat2(zelle + 1)) {
252 return true;
253 } else {
254 zahlIstVerwendet[wert] = false;
255 }
256 } else {
257 return true;
258 }
259 }
260 }
261
262 return false;
263 }
264
265
266
267 /**
268 * Gibt dieses Magisches Quadrat formatiert auf der Console aus.
269 */
270 public void print() {
271 for (int zeile = 0; zeile < quadrat.length; zeile++) {
272 for (int spalte = 0; spalte < quadrat.length; spalte++) {
273 System.out.print(quadrat[zeile][spalte] + "\t");
274 }
275 System.out.println();
276 }
277 }
278 }