# Magisches Quadrat



## shock.digital (5. Feb 2011)

Hey Leute,

ich habe folgendes 'Progrämmchen' erstellt, das mir im Backtracking-Verfahren ein Magisches Quadrat der Größe n*n liefert. Es gibt mir auch für n=3 die magischen Quadrate aus, bei n=4 kommt jedoch auch nach ca. 12 Stunden Laufzeit keine Ausgabe zustande. Wisst ihr vielleicht weiter und könnt mir sagen woran es evtl. liegen kann? Hier das Programm:


```
/**
 *
 * Das Programm berechnet eine 2-Dimensionale Matrix der Groesse n*n unter Beachtung, dass es sich um ein magisches Quadrat handelt
 *
 */

import java.util.Scanner; 

public class Quadrat {

	int n;
	int hoechsteZahl=n*n;
	
	Quadrat(int n, int hoechsteZahl) {
		
		this.n=n;
		this.hoechsteZahl=n*n;
	}
	/**
	 * Guckt ob das Quadrat magisch ist
	 * @param magischZahl,
	 *					  berechnet die Magische Zahl eines Quadrats	 
	 * @param diag_links,
	 *					 beschreibt die Summe aller Zahlen der linken Diagonale im Quadrat [Start: Feld 1, Ende: Feld n*n]	
	 * @param diag_rechts,
	 *					  beschreibt die Summe aller Zahlen der rechten Diagonale im Quadrat [Start: Feld n, Ende: Feld (n*2+1 | bei n=3) ; Feld (n*3+1) | bei n=4) ...	 
	 * @param zeile,
	 *				beschreit die Summe aller Zahlen der jeweils betrachteten Zeile
	 * @param spalte,
	 *				 beschreibt die Summe aller Zahlen der jeweils betrachteten Spalte
	 * @return true | false
	 */
	public boolean istMagisch(int quad[][]) {
		
		int magischZahl=(((n*n*n)+n)/2);
		int diag_links=0;
		int diag_rechts=0;
		
		for (int i=0; i<quad.length; i++) {
			int zeile=0;
			int spalte=0;
			
			for (int j=0; j<quad[i].length; j++) {
				if (quad[i][j]==0) {
					return false;
				}
				zeile += quad[i][j];
				spalte += quad[j][i];
			}
			
			if (zeile!=magischZahl || spalte!=magischZahl)
				return false;
			
			diag_links += quad[i][i];
			diag_rechts += quad[(n-1)-i][i];
		}
		
		if (diag_links!=magischZahl || diag_rechts!=magischZahl) 
			return false;
		

		return true; // keine Fehler gefunden -> true wird ausgegeben -> Magisches Quadrat
	}
	
	/**
	 * Dient dem Fuellen eines bestimmten Feldes mit einem passenden Wert, sodass das Quadrat magisch ist
	 *
	 * @param: nummer, 
	 *                           zaehlt alle Felder von Links nach Rechts und von Oben nach Unten
	 */
	public void setzen(int nummer, int feld, int quad[][]) {
		quad[feld/quad.length][feld%quad.length]=nummer;
	}
	
	/**
	 * Dient dem Entfernen des jeweiligen Feldes, falls es noetig ist, es zu loeschen, falls es sich um KEIN magisches Quadraft handelt
	 *
	 * quad an der Stelle quad[][] wird gleich 0 gesetzt -> also geloescht
	 *
	 * 
	 */
	public void entfernen(int feld, int quad[][]) {
		quad[feld/quad.length][feld%quad.length]=0;
	}
	
	/**
	 * Dient der Ausgabe der gefuellten 2-Dimensionalen Matrix 
	 *
	 * @param i,
	 *			dient der Ausgabe der Zeilen
	 * @param j,
	 *			dient der Ausgabe der Spalten
	 */
	public void ausgabe(int quad[][]) {
		
		for (int i=0; i<quad.length; i++) {
			for (int j=0; j<quad[i].length; j++) {
				System.out.print(quad[i][j]+"  ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	/**
	 * Erstellt ein Array mit allen Zahlen, die noch nicht in das Quadrat eingesetzt wurden
	 *
	 * @param hoechsteZahl,
	 *					   beschreibt die hoechste, moegliche Zahl mit der die 2-Dimensionale Matrix gefuellt werden kann (n*n)
	 *
	 * @param erstesLeeresFeld,
	 *						   sucht das erste leere Feld in der erzeugten 2-Dimensionalen Matrix, welches noch nicht befuellt wurde, also keinen Wert enthaelt
	 */
	public int[] unbenutzt(int quad[][]) {
		boolean[] gefuellt = new boolean[hoechsteZahl+1];
		int erstesLeeresFeld = hoechsteZahl;
		for (int i=0; i<quad.length; i++) {
			for (int j=0; j<quad[i].length; j++) {
				if (quad[i][j]!=0) {
					gefuellt[ quad[i][j] ]=true;
					erstesLeeresFeld--;
				}
			}
		}
	
		/**
		 * Erstellt ein Array mit den Zahlen, die
		 *
		 * @param result_i,
		 *                        wenn gefüllt nicht true ist, wird i der Wert der Zahl 
                 *                        ahl an der Stelle result_i++ aus dem Array result zugewiesen
		 * @param result,
		 *                      erstellt ein Array mit den Zahlen von 1-erstesLeeresFeld
		 * @return result (Array)
		 */
		int[] result=new int[erstesLeeresFeld];
		int result_i=0;
		for (int i=1; i<gefuellt.length; i++) {
			if (!gefuellt[i])
				result[ result_i++ ]=i;
		}
		return result;
	}
	
	/**
	 * Fuellt die 2-Dimensionale Matrix magquad mit den Werten von 1 - n*n
	 * -- Zusaetzlich wird die Methode berechnen() aufgerufen um zu gucken ob es sich um ein magisches Quadrat handelt, damit es ausgegeben werden kann
	 */
	public void berechnen() {
		int[][] magquad=new int[this.n][this.n];
		pruefen(0, magquad);
	} 
	
	/**
	 * Besitzt das erste leere Feld im Quadrat den Wert der hoechsten, moeglichen Zahl (n*n), wird geguckt ob es sich um ein Magisches Quadrat handelt
	 * -> Falls die IF-Abfrage erfolgreich ist, dann wird das jeweilige magische Quadrat ausgegeben
	 */
	public void pruefen(int erstesLeeresFeld, int magquad[][]) {
		if (erstesLeeresFeld==hoechsteZahl) {
			if (istMagisch(magquad)) {
				System.out.println("Magisches Quadrat der Größe "+n+"*"+n+": ");
				ausgabe(magquad);
			}
		} else {
				int[] nummern =unbenutzt(magquad);
				for (int i=0; i<nummern.length; i++) {
					setzen(nummern[i], erstesLeeresFeld, magquad);
					pruefen(erstesLeeresFeld+1, magquad);
					entfernen(erstesLeeresFeld, magquad);
			}
		}
	}

	/**
	 * Main-Methode: Eingabe von n, Aufruf: magisches Quadrat der Groesse n*n zu berechnen 
	 *
	 * @param n,
	 *	          wird durch den Benutzer eingegeben, beschreibt Groesse des Quadrats (n*n)
	 */
	public static void main(String args[]) {
		System.out.print("Bitte geben Sie die Größe des Quadrats an: ");
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		Quadrat quad = new Quadrat(n);
		quad.berechnen();
	}
}
```

Hoffe ihr könnt mir da weiterhelfen.
Danke im vorraus..

Gruß,

shock


----------



## HoaX (5. Feb 2011)

Erkläre mal was du unter einem magischen Quadrat verstehst und kommentiere denen Code ordentlich, dann schau ichs mir heute abend mal an.


----------



## shock.digital (5. Feb 2011)

Ein magisches Quadrat ist eine n*n Matrix, bei der die Summe jeder Zeile, die Summe jeder Spalte, und die Summe jeder Diagonale, gleich ist: (gilt aber nur für n>=3)

Also z.B              


8    3    4   --> = 8+3+4 = 15
1    5    9   --> = 1+5+9 = 15
6    7    2   --> = 6+7+2 = 15

Spalte[1]=8+1+6=15
Spalte[2]=3+5+7=15
Spalte[3]=4+9+2=15

Diagonale[1]=8+5+2=15
Diagonale[2]=4+5+6=15

Magisches Quadrat ? Wikipedia

[Kommentierung hab ich nachträglich editiert]

Gruß,

shock


----------



## HoaX (5. Feb 2011)

Ich meine mit Kommentare eingentlich den Code direkt, nicht nur die Methodenköpfe. Was die machen sollen war mir schon aus dem Namen klar. Aber egal.

Hab mich grad mal n paar Minuten reingedacht. Wenn ich das richtig sehe, dann gibt es ja n! Möglichkeiten die du durchgehst. Das sind bei 16! fast schlappe ~21 Billionen Möglichkeiten. Wenn dein Rechner 100.000 Möglichkeiten pro Sekunde testet, dann brauchst er immernoch >6 Jahre... Also ich würde an deiner Stelle länger als 12h warten.


----------



## Marco13 (5. Feb 2011)

Ja, mit Brute-Force-Backtracking in dieser Form wird das nix. Bei Backtracking gibt es meistens drei Möglickeiten, das ganze (zumindest für einige Fälle) in vertretbarer Zeit lösen zu lassen:
1. Pruning
2. Pruning
3. Pruning

Wenn du anfängst und die erste Zeilen mit "1  2  3  4" gefüllt hast, dann würde er bei deinem bisherigen Ansatz schonmal ein paar Jahre brauchen um ALLE Kombinationen für die restlichen Felder durchzuprobieren - nur um festzustellen, dass keine davon zum Erfolg führt, weil ja schon die erste Zeile eine Lösung unmöglich macht. Du müßtest die "istMagisch"-Methode aufteilen: Einmal für den Fall, dass das quadrat schon fertig gefüllt ist (der tatsächliche abschließende Test), und einmal für den Fall, dass noch Felder frei sind. Sinngemäß in zwei Methoden:
istMagisch
und
istNochNichtFertigKönnteAberMagischWerden.
und die dann in der pruefe-Methode passend aufrufen.

EDIT: Für Quadrate mit ungerader Kantenlänge gibt's übrigens eine direkte Möglichkeit: http://www.java-forum.org/java-basics-anfaenger-themen/28040-magic-square.html#post316068


----------



## shock.digital (5. Feb 2011)

Wenn ich die Methode 'halbiere' dann müsste das wie folgt aussehen.

Die Methode istMagisch verändert sich ja nicht, oder?

```
public boolean istMagisch(int quad[][]) {

int magischZahl=(((n*n*n)+n)/2);
		int diag_links=0;
		int diag_rechts=0;
		
		for (int i=0; i<quad.length; i++) {
			int zeile=0;
			int spalte=0;
			
			for (int j=0; j<quad[i].length; j++) {
				if (quad[i][j]==0) {
					return false;
				}
				zeile += quad[i][j];
				spalte += quad[j][i];
			}
			
			if (zeile!=magischZahl || spalte!=magischZahl)
				return false;
			
			diag_links += quad[i][i];
			diag_rechts += quad[(n-1)-i][i];
		}
		
		if (diag_links!=magischZahl || diag_rechts!=magischZahl) 
			return false;
		
		return true;
	}
```

Methode kannNochMagischWerden:

```
public boolean kannNochMagischWerden(int magquad[][]) {

		int[] nummern =unbenutzt(magquad);
				for (int i=0; i<nummern.length; i++) {
					setzen(nummern[i], erstesLeeresFeld, magquad);
					pruefen(erstesLeeresFeld+1, magquad);
					entfernen(erstesLeeresFeld, magquad);
                                        ausgabe(magquad);
	}
```

Und die Methode pruefen, sähe dann so aus:


```
public void pruefen(int erstesLeeresFeld, int magquad[][]) {
		if (erstesLeeresFeld==hoechsteZahl) {
			if (istMagisch(magquad)) {
				System.out.println("Magisches Quadrat der Größe "+n+"*"+n+": ");
				ausgabe(magquad);
			}
} else {
kannNochMagischWerden(magquad);
}
}
```

Oder oO?


Nachtrag: Danke für den Link  Die Berechnung soll sich jedoch nicht nur auf Quadrate mit ungerader Kantenlänge beschränken.


----------



## Marco13 (5. Feb 2011)

Sehe ich das richtig, dass du jetzt vorhast, zu überprüfen, ob das Quadrat noch magisch werden kann, indem du (mit der Methode, die durch Einführung dieser Methode beschleunigen willst) nach Lösungen suchst?  

Das war nicht so gemeint.

Wenn man mit der Formulierung ein bißchen aufpasst, könnte man die beiden Methoden ("istNochNichtFertigKönnteAberMagischWerden" und "istMagisch") auch in EINER Methode machen. Ich dachte nur, dass es getrennt vielleicht leichter wäre  

Der Hauptgrund, warum man diese Abfrage ("könnteNochMagischWerden") mit deiner aktuellen istMagisch-Methode NICHT machen kann, ist die Abfrage 

```
if (quad[i][j]==0) {
    return false;
}
```
Wenn in einer Reihe (also Zeile, Spalte oder Diagonalen) eine 0 steht, heißt das ja so gesehen nicht, dass das Quadrat nicht magisch ist, sondern nur, dass es noch nicht fertig gefüllt ist. 

Bisher hat deine Methode istMagisch also sowas gemacht:
_WENN eine 0 in einer Reihe steht, DANN ist das Quadrat nicht magisch._
Das passt natürlich nicht bei "unfertigen" Quadraten. Wenn man das ändert zu
_WENN *keine* 0 in einer Reihe steht *UND * die Reihe die falsche Summe hat, DANN ist das Quadrat nicht magisch._ 
kann man die gleiche Methode für fertige und unfertige Quadrate verwenden.

Im Pseudocode würde das dann so aussehen:

```
boolean istOK()
{
    für (jede Zeile)
    {
        if (zeile enthält keine 0) 
        {
            if (zeilensumme ist != magischeSumme) return false;
        }
    }
    für (jede Spalte)
    {
        if (spalte enthält keine 0) 
        {
            if (spaltensumme ist != magischeSumme) return false;
        }
    }
    für (jede Diagonale)
    {
        if (diagonale enthält keine 0) 
        {
            if (diagonalensumme ist != magischeSumme) return false;
        }
    }
    return true;
}
```

Das sollte für alle Fälle funktionieren: Wenn eine Reihe noch eine 0 enthält, wird am Ende trotzdem "true" zurückgegeben, weil die 0 ja nicht bedeutet, dass das Quadrat nicht magisch ist, sondern nur, dass es noch nicht fertig ist. 
NUR wenn in einer Reihe KEINE 0 mehr steht, und DANN (trotzdem) die falsche Summe rauskommt, kann man mit Sicherheit sagen, dass es NICHT magisch ist. D.h. nur in diesen Fällen gibt man "false" zurück. 

Die "preufe"-Methode wäre dann sowas wie

```
pruefe()
{
    if (!istOK())
    {
        // Vielleicht ist es noch nicht fertig, aber irgendeine
        // Reihe enthält schon keine 0en mehr, aber ergibt
        // trotzdem schon die falsche summe - das KANN
        // nichts mehr werden
        System.out.println("Vergiss es");
    }
    else
    {
        // Bisher spricht nichts dagegen, dass es magisch sein könnte.

        if (keine freien Felder mehr)
        {
            // Hey, das ist OK und alle Felder sind belegt. Also ...
            System.out.println("It's a kind of magic...");
        }     
        else
        {
            // Weitersuchen... 
            backtacking()...
        }
    }
}
```


----------



## Gusti (6. Feb 2011)

Ich hab eine kleine Frage wegen dem new-Operator,.. wenn ich zB deinen Quellcode ganz oben nehme und compiliere, dann kommt eine Fehlermeldung: 
Quadrat.java:178: cannot find symbol
symbol  : constructor Quadrat(int)
location: class Quadrat
             Quadrat quad = new Quadrat(n);
                              (Pfeil zeigt auf new)
1 error


```
...
public static void main(String args[]) {
        System.out.print("Bitte geben Sie die Größe des Quadrats an: ");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Quadrat quad = new Quadrat(n);
        quad.berechnen();
    }
}
```

Woran kann das liegen?..


----------



## Marco13 (6. Feb 2011)

Zusätzlich n*n übergeben.

EDIT @shock.digital: Notfalls den, der für das Testieren der Aufgabe verantwortlich ist, auf diesen Thread verweisen.


----------



## chalkbag (6. Feb 2011)

@offtopic

Das erinnert mich, als wir für die "ki" von Schiffeversenken einen Backtracking-Algorithmus implementiert haben, und ich mich gewundert habe, wieso er für ein 15x15 Feld einfach nicht fertig werden wollte


----------

