# Laufzeitproblem: magisches Quadrat



## ernst (8. Jan 2012)

Hallo allerseits,
1)
Ein magisches Quadrat ist eine nxn Matrix, die aus lauter _verschiedenen_ , ganzen Zahlen 1, 2, .., n 
besteht und deren Reihensummen (d.h. Zeilen, Spalten,. Diagonalen) gleich sind.
Beispiel (n=3):
2 7 6
9 5 1
4 3 8

2)
Ich habe dazu ein Programm rekursives geschrieben (siehe unten)
Es funktioniert auch.
Nur braucht es (für n=3) auf meinem ca. 10  Jahr alten Rechner
(AMD 1,80 Ghz, 768 MB RAM) ca. 5 Minuten.
Deswegen getraue ich mich nicht, es auf n=4 zu erweitern.

3)
Ich will keine weiteren - die man mathematisch beweisen kann - Informationen benutzen 
[z.B. könnte  man eine Formel für die Reihensumme benutzen: ich glaube (n*(n*n+1))/2)], 
um das Problem zu vereinfachen.

4)
Fragen:
a) Warum ist das Laufzeitverhalten so schlecht (liegt es am Rechner oder an meinem Algorithmus)?
b) Wie kann man es optimieren?

nfg
Ernst


```
package magischesquadrat2;
import java.util.*;
import java.util.Date;

public class MainMagischesQuadrat2 {

    public static void main(String[] args) {
        int b;
        Feld feld=new Feld();
        Feld ergebnisFeld=new Feld();
        long start, stop, dauer;
        // Wert in Millisekunden
        start = new Date().getTime();

        b=feld.N(ergebnisFeld);
        ergebnisFeld.printFeld();
        // Wert in Millisekunden
        stop = new Date().getTime();

        // Wert in Sekunden
        dauer = (stop -start)/1000;
        System.out.println("Laufzeit des Programms="+dauer+" Sekunden");
    }
}

class Feld {
    public int feld[];

    public Feld() {
        feld = new int[9];
    }

    public void set(int stelle, int wert) {
        feld[stelle] = wert;
    }

    public int get(int stelle) {
        return feld[stelle];
    }

    public void kopieren(Feld pFeld){
        for(int i=0;i<9;i++){
            this.set(i,pFeld.get(i));
        }
    }

    public void kopieren(int z){
        for(int i=0;i<9;i++){
            feld[i]=z;
        }
    }

/*
prueft, ob jede Zelle des Feldes mit einer ganzen Zahl zwischen
0 und 9 belegt ist.
*/
    public boolean istVollbelegt(){
        int zaehler=0;
        int i;
        boolean back;
        for (i = 0; i < 9; i++) {
            if (feld[i] != 0) {
                zaehler++;
            }
        }
        if(zaehler==9){
            back=true;
        }
        else{
            back=false;
        }
        return back;
    }

/**
prueft nach, ob ein Feld magisch ist, d.h. voll belegt
und alle Zeilen, Spalten und Diagonalensummen gleich sind.
*/
   public boolean istMagisch(){
        int zaehler=0;
        int i;
        boolean back;
        boolean b;
        b=istSummenKorrekt();
        if(b==true){
            for (i = 0; i < 9; i++) {
                if (feld[i]!= 0) {
                    zaehler++;
                }
            }
        }
        if(zaehler==9){
            back=true;
        }
        else{
            back=false;
        }
        return back;
    }

/*
prueft, ob die Zeilen, Spalten und Diagonalensummen aller
Reihen, die keine unbelegten Zellen enthalten, gleich sind.
*/
    public boolean istSummenKorrekt(){
        int i;
        int[] temp = new int[9];
        int len=0;
        boolean korrekt = true;

        if(feld[0]!=0 && feld[1]!=0 && feld[2]!=0){
            temp[len]=feld[0]+feld[1]+feld[2];
            len++;
        }

        if(feld[3]!=0 && feld[4]!=0 && feld[5]!=0){
            temp[len]=feld[3]+feld[4]+feld[5];
            len++;
        }

        if(feld[6]!=0 && feld[7]!=0 && feld[8]!=0){
            temp[len]=feld[6]+feld[7]+feld[8];
            len++;
        }

        if(feld[0]!=0 && feld[3]!=0 && feld[6]!=0){
            temp[len]=feld[0]+feld[3]+feld[6];
            len++;
        }

        if(feld[1]!=0 && feld[4]!=0 && feld[7]!=0){
            temp[len]=feld[1]+feld[4]+feld[7];
            len++;
        }

        if(feld[2]!=0 && feld[5]!=0 && feld[8]!=0){
            temp[len]=feld[2]+feld[5]+feld[8];
            len++;
        }

        if(feld[0]!=0 && feld[4]!=0 && feld[8]!=0){
            temp[len]=feld[0]+feld[4]+feld[8];
            len++;
        }

        if(feld[2]!=0 && feld[4]!=0 && feld[6]!=0){
            temp[len]=feld[2]+feld[4]+feld[6];
            len++;
        }

        // Testen ob alle Summen gleich sind
        if(len==0){
            korrekt=true;
        }
        else{
            for(i=0;i<len;i++){
                if(temp[0]!=temp[i]){
                    korrekt=false;
                    break;
                }
            }
        }
        return korrekt;
    }

/**
prueft, ob ein Feld vollbelegt ist, oder mindestens zwei Reihen
(d.h. Zeilen, Spalten, Diagonalen) drin sind, deren Reihensumme
verschieden ist.
*/
    public boolean istEndfeld(){
        boolean back=false;
        if(this.istVollbelegt()){
            back=true;
        }
        else{
            if(this.istSummenKorrekt()==false)
                back=true;
        }
        return back;
    }

/*
Die Berechnung des Erloeses bei einem Endfeld, d.h. ob es magisch ist
*/
    public int S(){
        int back=1;
        if(this.istEndfeld()){
            if(this.istMagisch()){
                back=1;
            }
            else{
                back=-1;
            }
        }
        else{
            if(this.istSummenKorrekt()==false)
                back=-1;
        }
        return back;
    }

/*
Belegt ein vorhandenes Feld an einer bestimmten Stelle mit
einer Zahl
*/
    public Feld berechneNext(int pStelle, int pZahl) {
        Feld feldneu = new Feld();
        // altes Feld in das neue kopieren
        for(int i=0;i<9;i++)
            feldneu.set(i, this.get(i));
        feldneu.set(pStelle, pZahl);
            return feldneu;
    }

/**
prueft, ob ein Feld (das z.B. aus lauter Nullen besteht)
magisch ergänzt werden kann.
Beispiele:
1)
0 0 0
0 0 0
0 0 0
dieses Feld kann magisch ergaenzt werden z.B. zu:
2 7 6
9 5 1
4 3 8

2)
1 2 3
4 5 0
6 0 0
dieses Feld kann nicht magisch ergaenzt werden,
da zwei Reihensummen schon verschieden sind.
Es ist ein Endfeld.
*/
    public int N(Feld ergebnisFeld){
        int pos;
        int value;
        boolean erg;
        int b;
        int back=-1;
        Feld feldneu = new Feld();
        Feld temp = new Feld();
        // Feld ist vollbelegt
        if(this.istEndfeld()){
            back = this.S();
            if(this.istMagisch()){
                ergebnisFeld.kopieren(this);
            }
            else{ // ist vollbelegt aber nicht magisch
                ergebnisFeld.kopieren(-1);
            }
        }
        // Feld hat Nachfolger
        else{
            for(pos=0; pos<9; pos++){
                for(value=1; value<10; value++){
                    erg=sindZahlenkorrekt(pos, value);
                    // Neuer Nachfolger
                    if(erg==true){
                        feldneu=berechneNext(pos, value);
                        b=feldneu.N(temp);
                        if(b==1){
                            back=1;
                            ergebnisFeld.kopieren(temp);
                            // VorgÃ¤nger ist magisch ergÃ¤nzbar
                            return back;
                        }
                    }
                }
            }
            ergebnisFeld.kopieren(-1);
            back=-1;
        }
        return(back);
    }

/*
prueft, ob das Feld am Feldindex pos mit der Wert value
belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
ganze Zahl zwischen 1 und 9 steht, oder dadurch das Feld
2 gleiche Zahlen hat.
*/
    boolean sindZahlenkorrekt(int pos, int value){
        boolean back=true;
        int i;
        if(feld[pos]!=0){
            back=false;
        }
        else{
            for(i=0;i<9;i++){
                if(feld[i]==value){
                    back=false;
                    break;
                }
            }
        }
        return back;
    }

    // Ausgabe auf Bildschirm
    public void printFeld(){
        for(int k=0;k<9;k++){
            if(k%3==0)
                System.out.println();
                System.out.print(" "+feld[k]);
            }
            System.out.println();
    }
}
```


----------



## GUI-Programmer (8. Jan 2012)

Erfolgreich getestet! Mein System: Windows 7 HomePremium 64 Bit; Intel(R) Core(TM) i5 CPU 650 3.20 GHz, 4Gb RAM

Resultat: 30 Sekunden. Am Pc liegts nicht, irgenwo hängt dein Programm in ner Schleife oder ne Rekursion für ne ganze Zeit lang fest.


----------



## Paddelpirat (8. Jan 2012)

Hmm ich würde den Code an deiner Stelle auch mal auf überflüssigen Code überprüfen.

Nur so als Beispiel fallen mir da die Methoden 
	
	
	
	





```
istVollbelegt()
```
, 
	
	
	
	





```
istMagisch()
```
 und 
	
	
	
	





```
istSummenKorrekt
```
auf.

Hier macht es Sinn zuerst zu überprüfen, ob überhaupt alle Felder belegt sind. Dann brauchst du in der Methode keine Abfragen mehr die das für dich überprüfen. Und in der Methode 
	
	
	
	





```
istMagisch
```
 solltest du die Reihenfolge verändern. Z.B. so:


```
/*
prueft, ob jede Zelle des Feldes mit einer ganzen Zahl zwischen
0 und 9 belegt ist.
*/
    public boolean istVollbelegt(){
        int zaehler=0;
        int i;
        boolean back;
        for (i = 0; i < 9; i++) {
            if (feld[i] != 0) {
                zaehler++;
            }
        }
        if(zaehler==9){
            back=true;
        }
        else{
            back=false;
        }
        return back;
    }
 
/**
prueft nach, ob ein Feld magisch ist, d.h. voll belegt
und alle Zeilen, Spalten und Diagonalensummen gleich sind.
*/
   public boolean istMagisch(){
        boolean back;

        if(istVollbelegt()){
            back = istSummenKorrekt();
        }
        else{
            back=false;
        }
        return back;
    }
```

Gibt aber bestimmt noch andere Dinge die man performanter machen könnte.
Edit: meine 
	
	
	
	





```
istSummenKorrekt()
```
-Methode taugte nichts.


----------



## Stelufl (9. Jan 2012)

Guten morgen,

ohne meinen ersten Kaffee getrunken zu haben, bin ich spontan auf diesen -wenn auch eher kleinen- Performancegewinn gestoßen:
Es ist unnötig die ganze Matrix zu durchlaufen, um zu gucken, ob sie "voll" ist. Wenn ein Element leer ist, ist sie nicht voll:


```
public boolean istVollbelegt(){        
        for (i = 0; i < 9; i++) {
            if (feld[i] == 0) {
                return false;
            }
        }
        return true;
    }
```

Ich weiß nun nicht, wo und wie oft die Methode aufgerufen wird. Aber du könntest dir die theoretisch komplett sparen, indem du beim Setzen eines Feldes um 1 hochzählst. Entspricht der Counter der Anzahl der Felder, sind alle Felder gesetzt. So sparst du die ganze Methode.

Als Anfänger auf Performance zu programmieren und das mit einem relativ schweren Problem ist vielleicht etwas zu viel verlangt. Das kommt ganz von alleine. Ich empfehle Dir das Buch Effective Java von Joshua Bloch. Das ist ein must-read!


----------



## Sonecc (9. Jan 2012)

Dein Konzept ist leider nicht so besonders gut.
Du erstellst dauernd neue Felder und prüfst dann mit den neuen Weiter und so weiter.
Dabei kopierst du dauernd felder und belegst alle neu und so weiter und so fort.

Das ganze lässt sich relativ einfach per Backtracking lösen (hab eben mal eine Lösung zusammengetippelt und hab nicht lange dafür gebraucht, meine Methode benötigt aber vorbelegte Felder, sonst kommt immer das gleiche Ergebnis)

Deine Methode N() wird z.B. ganze 194.514.253 mal aufgerufen. (Bei meinem Test)


----------



## ernst (3. Apr 2012)

Sonecc hat gesagt.:


> Dein Konzept ist leider nicht so besonders gut.
> Du erstellst dauernd neue Felder und prüfst dann mit den neuen Weiter und so weiter.
> Dabei kopierst du dauernd felder und belegst alle neu und so weiter und so fort.
> 
> ...



Wie soll ein Programm aussehen, das irgendein magisches Quadrat erzeugt ?
(d.h. in einem 3x3 Feld alle verschiedenen Zahlen von 1 - 9 unterbringt mit gleicher Reihensumme)

Habe jetzt verschiedene Lösungen ausprobiert, doch leider wird das Laufzeitverhalten nicht besser.
(mein letzter Versuch benötigte ca. 9 Minuten).
Kann mir jemand sagen, wie lange seine Lösung (sein Programm) mit Backtracking benötigt und falls möglich. den Quellcode dazu ?
(Mein 3x3 Feld wird mit 9 Nullen vorbelegt, was bedeutet, dass es 9 unbelegte Elemente in diesem Feld gibt).


mfg
Ernst


----------



## Sonecc (3. Apr 2012)

Kleiner Tipp: Such mal nach einem Quellcode für das lösen von Sudokus. Die sind vom Prinzip her ähnlich aufgebaut.
Du musst dann halt nur die Bedingungen ändern.

Soweit ich mich erinnere hatte ich das damals mithilfe meines Sudoku Codes gelöst und dafür eben einfach meine check Methode angepasst (die prüft, ob der gegebene Wert eingesetzt werden kann)


----------



## ernst (3. Apr 2012)

Sonecc hat gesagt.:


> Kleiner Tipp: Such mal nach einem Quellcode für das lösen von Sudokus. Die sind vom Prinzip her ähnlich aufgebaut.
> Du musst dann halt nur die Bedingungen ändern.
> 
> Soweit ich mich erinnere hatte ich das damals mithilfe meines Sudoku Codes gelöst und dafür eben einfach meine check Methode angepasst (die prüft, ob der gegebene Wert eingesetzt werden kann)



1) Habe leider die Backtracking-Lösungen nicht verstanden.

2) Ist die Lösung (siehe unten) von mir auch backtracking?


```
package magischesquadrat5;
import java.util.*;
import java.util.Date;

public class MainMagischesQuadrat5 {

    public static void main(String[] args) {
        boolean b;
        int  back;
        Neunerfeld feld=new Neunerfeld();
        feld.kopieren(0,0,0,0,0,0,0,0,0);
        feld.kopieren(0,0,0,0,0,0,0,0,2);
        feld.kopieren(0,0,0,0,0,0,0,0,0);
        //feld.kopieren(8,3,4,1,5,9,6,7,2);
        //feld.kopieren(0,0,0,1,5,9,6,7,2);
        MyMath m = new MyMath();

        long start, stop, dauer;
        // Wert in Millisekunden
        start = new Date().getTime();

        b=feld.korrekt();
        System.out.println("Das Feld muss korrekt sein, sonst wird die Berechnung falsch");
        System.out.println("Das Feld ist: " +b);
        back=m.N(feld);
        System.out.println("back="+back);
        //back.array9.printFeld();
        // Wert in Millisekunden
        stop = new Date().getTime();

        // Wert in Sekunden
        dauer = (stop -start)/1000;
        System.out.println("Laufzeit des Programms="+dauer+" Sekunden");
    }

}





class MyMath{
/**
* prueft, ob ein Neunerfeld (das z.B. aus lauter Nullen besteht)
* magisch ergänzt werden kann. Magisch ergänzt werden bedeutet, daß ein Neunerfeld
* weiter so mit verschiedenen Zahlen belegt werden kann,
* bis es vollbelegt und magisch wird.
* <b>Beispiel:</b><br>
* 1)
* 0 0 0
* 0 0 0
* 0 0 0
* dieses Neunerfeld kann magisch ergaenzt werden z.B. zum
* magisch zu ergaenzenden Neunerfeld:
* 2 7 6
* 9 5 1
* 4 3 8
*
* 2)
* 1 2 3
* 4 5 0
* 6 0 0
* dieses Neunerfeld kann nicht magisch ergaenzt werden,
* da zwei Reihensummen schon verschieden sind.
* Es ist ein Endfeld.
* Wenn es nicht magisch ergaenzt werden kann, wird das
* magisch zu ergaenzenden Neunerfeld gesetzt auf:
* -1 -1 -1
* -1 -1 -1
* -1 -1 -1
* @param feld (i) ist das auf magische Ergänzbarkeit zu prüfende Feld
* @return (o) B.1 : Neunerfeld ist magisch ergänzbar mit magisch
*                   ergänztem Feld B.array9
*             B.-1: Neunerfeld ist nicht magisch ergänzbar
*/

    public int N(Neunerfeld feld){
        int pos;
        int value;
        int tempValue;
        boolean erg;
        int back;

        pos = feld.firstUnbelegtePosition();
        while(pos<9){
            for(value=1; value<10; value++){
                // prüft, ob im Neunerfeld "feld" noch feld[pos]=value gesetzt
                // werden könnte
                erg=feld.istNachfolger(pos, value);
                if(erg==true){
                    tempValue=feld.feld9[pos];
                    feld.feld9[pos]=value;
                    back=N(feld);
                    if(back==1){
                        return 1;
                    }
                    feld.feld9[pos]=tempValue;
                }
            }
            pos=feld.nextUnbelegtePosition(pos);
        }
        // Es gibt keine Nachfolger:
        if(feld.istMagisch()){
            feld.printFeld();
            back = 1;
        }
        else{
            //System.out.println("nicht Magisch");
            back = -1;
        }
        return(back);
    }
}





class Neunerfeld {
    public int feld9[];

    public Neunerfeld() {
        feld9 = new int[9];
    }

    public void set(int stelle, int wert) {
        feld9[stelle] = wert;
    }

    public int get(int stelle) {
        return feld9[stelle];
    }

    public void kopieren(Neunerfeld pFeld){
        for(int i=0;i<9;i++){
            this.set(i,pFeld.get(i));
        }
    }

    public void kopieren(int z){
        for(int i=0;i<9;i++){
            feld9[i]=z;
        }
    }

    public void kopieren(int z1, int z2, int z3, int z4, int z5, int z6, int z7, int z8, int z9){
        feld9[0]=z1;
        feld9[1]=z2;
        feld9[2]=z3;
        feld9[3]=z4;
        feld9[4]=z5;
        feld9[5]=z6;
        feld9[6]=z7;
        feld9[7]=z8;
        feld9[8]=z9;
    }


    public int nextUnbelegtePosition(int posAlt){
        for(int i=posAlt+1;i<9;i++){
            if(feld9[i]==0){
                return i;
            }
        }
        return 9;
    }

    public int firstUnbelegtePosition(){
        for(int i=0;i<9;i++){
            if(feld9[i]==0){
                return i;
            }
        }
        return 9;
    }


/**
* Eine Zelle eines Feldes ist unbelegt, wenn sie den Wert 0 hat.
* Sie ist belegt, wenn sie als Wert 1, 2, 3, 4, 5, 6, 7, 8 oder 9 hat
* Es wird geprüft, ob jede Zelle des Feldes mit einer ganzen Zahl zwischen
* 1 und 9 belegt ist.
* @return (o) true : Neunerfeld ist voll belegt
*             false: Neunerfeld ist nicht voll belegt
*/
    public boolean istVollbelegt(){
        int zaehler=0;
        int i;
        boolean back;
        for (i = 0; i < 9; i++) {
            if (feld9[i] != 0) {
                zaehler++;
            }
        }
        if(zaehler==9){
            back=true;
        }
        else{
            back=false;
        }
        return back;
    }

/**
* prueft nach, ob ein Neunerfeld magisch ist, d.h. voll belegt
* und alle Zeilen, Spalten und Diagonalensummen gleich sind.
* @return (o) true : Neunerfeld ist magisch
*             false: Neunerfeld ist nicht magisch
*/
   public boolean istMagisch(){
        boolean back;

        if(istVollbelegt()){
            back = sindSummenKorrekt();
        }
        else{
            back=false;
        }
        return back;
    }


/**
* Ein Neunerfeld, das kein Endfeld ist, hat noch weiter(e) Nachfolger, kann also
* noch weiter mit Zahlen 1, 2, 3, .., 9 an einer bestimmten vorgegeben,
* Stelle belegt werden. Stellt fest, ob dies dann ein Nachfolger ist.
* @param pStelle (i) an dieser Stelle wird das Neunerfeld belegt
* @param pZahl   (i) an der Stelle pStelle wird das Neunerfeld mit dem Wert
*                    pZahl belegt
* @return (o) true:  Das Feld feld9+feld9[pStelle]=pZahl ist ein Nachfolger
*             false: sonstdas Neunerfeld, das um den Wert feld[pStelle]=pZahl
*/
    public boolean  istNachfolger(int pStelle, int pZahl) {
        boolean erg;
        erg=korrekt(pStelle, pZahl);
        return erg;
    }


/**
* prueft, ob das Neunerfeld an der Stelle (=Index) pos mit der Wert value
* belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
* ganze Zahl zwischen 1 und 9 steht, oder dadurch das Neunerfeld
* zwei gleiche Zahlen bekommen würde.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos würde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen
*             false: sonst
*/
    boolean sindZahlenKorrekt(int pos, int value){
        boolean back=true;
        int i;
        if(feld9[pos]!=0){
            back=false;
        }
        else{
            for(i=0;i<9;i++){
                if(feld9[i]==value){
                    back=false;
                    break;
                }
            }
        }
        return back;
    }


/**
* prueft, ob alle unbelegten Felder des Neunerfeldes verschieden sind.
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen
*             false: sonst
*/
    boolean sindZahlenKorrekt(){
        int i, j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                if(i!=j && feld9[i]!=0 && feld9[j]!=0){
                    if(feld9[i]==feld9[j]){
                        return false;
                    }
                }
            }
        }
        return true;
    }


/**
* prueft, ob die Zeilen, Spalten und Diagonalensummen aller
* Reihen, die keine unbelegten Zellen enthalten, gleich sind.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos würde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Zeilen, Spalten und Diagonalensummen aller Reihen,
*                    die keine unbelegten Zellen enthalten, gleich sind.
*             false:  sonst
*/
    public boolean sindSummenKorrekt(int pStelle, int pZahl){
        int pZahlAlt=this.feld9[pStelle];

        int i;
        int[] temp = new int[9];
        int len=0;
        boolean korrekt = true;

        if(feld9[0]!=0 && feld9[1]!=0 && feld9[2]!=0){
            temp[len]=feld9[0]+feld9[1]+feld9[2];
            len++;
        }

        if(feld9[3]!=0 && feld9[4]!=0 && feld9[5]!=0){
            temp[len]=feld9[3]+feld9[4]+feld9[5];
            len++;
        }

        if(feld9[6]!=0 && feld9[7]!=0 && feld9[8]!=0){
            temp[len]=feld9[6]+feld9[7]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[3]!=0 && feld9[6]!=0){
            temp[len]=feld9[0]+feld9[3]+feld9[6];
            len++;
        }

        if(feld9[1]!=0 && feld9[4]!=0 && feld9[7]!=0){
            temp[len]=feld9[1]+feld9[4]+feld9[7];
            len++;
        }

        if(feld9[2]!=0 && feld9[5]!=0 && feld9[8]!=0){
            temp[len]=feld9[2]+feld9[5]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[4]!=0 && feld9[8]!=0){
            temp[len]=feld9[0]+feld9[4]+feld9[8];
            len++;
        }

        if(feld9[2]!=0 && feld9[4]!=0 && feld9[6]!=0){
            temp[len]=feld9[2]+feld9[4]+feld9[6];
            len++;
        }

        // Testen ob alle Summen gleich sind
        if(len==0){
            korrekt=true;
        }
        else{
            for(i=0;i<len;i++){
                if(temp[0]!=temp[i]){
                    korrekt=false;
                    break;
                }
            }
        }
        this.feld9[pStelle]=pZahlAlt;
        return korrekt;
    }

/**
* prueft, ob die Zeilen, Spalten und Diagonalensummen aller
* Reihen, die keine unbelegten Zellen enthalten, gleich sind.
* @return (o) true : Zeilen, Spalten und Diagonalensummen aller Reihen,
*                    die keine unbelegten Zellen enthalten, gleich sind.
*             false:  sonst
*/
    public boolean sindSummenKorrekt(){
        int i;
        int[] temp = new int[9];
        int len=0;
        boolean korrekt = true;

        if(feld9[0]!=0 && feld9[1]!=0 && feld9[2]!=0){
            temp[len]=feld9[0]+feld9[1]+feld9[2];
            len++;
        }

        if(feld9[3]!=0 && feld9[4]!=0 && feld9[5]!=0){
            temp[len]=feld9[3]+feld9[4]+feld9[5];
            len++;
        }

        if(feld9[6]!=0 && feld9[7]!=0 && feld9[8]!=0){
            temp[len]=feld9[6]+feld9[7]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[3]!=0 && feld9[6]!=0){
            temp[len]=feld9[0]+feld9[3]+feld9[6];
            len++;
        }

        if(feld9[1]!=0 && feld9[4]!=0 && feld9[7]!=0){
            temp[len]=feld9[1]+feld9[4]+feld9[7];
            len++;
        }

        if(feld9[2]!=0 && feld9[5]!=0 && feld9[8]!=0){
            temp[len]=feld9[2]+feld9[5]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[4]!=0 && feld9[8]!=0){
            temp[len]=feld9[0]+feld9[4]+feld9[8];
            len++;
        }

        if(feld9[2]!=0 && feld9[4]!=0 && feld9[6]!=0){
            temp[len]=feld9[2]+feld9[4]+feld9[6];
            len++;
        }

        // Testen ob alle Summen gleich sind
        if(len==0){
            korrekt=true;
        }
        else{
            for(i=0;i<len;i++){
                if(temp[0]!=temp[i]){
                    korrekt=false;
                    break;
                }
            }
        }
        return korrekt;
    }



/**
* prueft, ob das Neunerfeld an der Stelle (=Index) pos mit der Wert value
* belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
* ganze Zahl zwischen 1 und 9 steht, oder dadurch das Neunerfeld
* zwei gleiche Zahlen bekommen würde.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos würde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen und
*                    alle Summen sind gleich
*             false: sonst
*/
    boolean korrekt(int pos, int value){
        boolean back=true;
        back=sindSummenKorrekt(pos,value) && sindZahlenKorrekt(pos,value);
        return back;
    }

/**
* prueft, ob alle Zahlen des Neunerfeld korrekt sind.
* @return (o) true : keine zwei gleiche Zahlen an unbelegten Elementen.
*                    und alle Summen gleich
*             false: sonst
*/
    boolean korrekt(){
        boolean back=true;
        back=sindSummenKorrekt() && sindZahlenKorrekt();
        return back;
    }



// Ausgabe auf Bildschirm
/**
* Gibt alle Zellen des Feldes auf dem Bildschirm aus
*/

    public void printFeld(){
        for(int k=0;k<9;k++){
            if(k%3==0)
                System.out.println();
                System.out.print(" "+feld9[k]);
            }
            System.out.println();
    }
}
```


----------



## Sonecc (3. Apr 2012)

1. Bitte niemals englisch und deutsch vermischen. Liest sich schrecklich, lenkt ab und verwirrt.
2. Hier mal der Quellcode, den ich damals zusammen getippelt habe. Zwar ist auch der in manchen Punkten verbesserungswürdig, aber er ist zumindest nicht schlecht.

Versuch ihn mal zu verstehen und verfolge mal, was bei einem durchlauf passiert.


```
public class Magic {
	
	public static void main(String[] args) {
		int s = 9;
		int[][] feld = new int[s][s];
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				feld[i][j] = 0;
			}
		}
		feld[2][1] = 6;
		feld[1][0] = 3;
		Magic magic = new Magic(feld);
		magic.generate();
		System.out.println(magic.toString());
	}
	
	private int[][] feld;
	private int size;
	
	public Magic(int size) {
		this(new int[size][size]);
	}
	
	public Magic(int[][] feld) {
		if (feld.length > 9 || feld.length < 2) {
			throw new IllegalArgumentException("Invalid starting field");
		}
		this.feld = feld;
		this.size = feld.length;
	}
	
	public boolean generate() {
		return generate(0,0);
	}
	
	private boolean generate(int i, int j) {
		if (j == size) {
			i++;
			if (i == size) {
				return true;
			}
			j = 0;
		}
		if (feld[i][j] > 0) {
			return generate(i,j+1);
		}
		for (byte val = 1; val < 10; val++) {
			if (check(i, j, val)) {
				feld[i][j] = val;
				if (generate(i, j+1)) {
					return true;
				}
			}
		}
		feld[i][j] = 0;
		return false;
	}

	private boolean check(int i, int j, byte val) {
		for (int row = 0; row < size; row++) {
			if (feld[row][j] == val) {
				return false;
			}
		}
		for (int col = 0; col < size; col++) {
			if (feld[i][col] == val) {
				return false;
			}
		}
		int sum = 0;
		for (int col = 0; col < size; col++) {
			if (feld[0][col] != 0) {
				sum+= feld[0][col];
			} else {
				return true;
			}
		}
		int rowSum = 0;
		int colSum = 0;
		for (int col = 0; col < size; col++) {
			if (col == j) {
				rowSum += val;
			} else if (feld[i][col] != 0) {
				rowSum += feld[i][col];
			} else {
				return true; 
			}
		}
		for (int row = 0; row < size; row++) {
			if (row == i) {
				colSum += val;
			} else if (feld[row][j] != 0) {
				colSum += feld[row][j];
			} else {
				colSum = -1;
				break;
			}
		}
		if (rowSum == sum) {
			if (colSum > 0 && colSum == sum) {
				return true;
			} else if (colSum == -1) {
				return true;
			}
		}
		return false;
	}
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int row = 0; row < size; row++) {
			for (int col = 0; col < size; col++) {
				sb.append(" " + feld[row][col]);
			}
			sb.append("\n");
		}
		sb.append("\n");
		return sb.toString();
	}
}
```


----------



## Landei (3. Apr 2012)

Hier eine Version, die auch für 4x4 läuft:


```
import java.util.HashSet;
import java.util.Set;

public class Magic {

    public static void main(String... args) {
        int n = 4;
        int[] array = magic(n);
        for(int i = 0; i < n*n; i++) {
            System.out.printf("%2d ",array[i]);
            if ((i+1) % n == 0) System.out.println();
        }
    }

    private static int[] magic(int n) {
        int[] array = new int[n*n];
        int s = (n*n*n+n)/2;
        Set<Integer> numbers = getNumbers(n);
        if(! magic(n, s, 0, array,numbers)) {
            throw new RuntimeException("No solution for magic square.");
        }
        return array;
    }

    private static boolean magic(int n, int s, int i, int[] array, Set<Integer> numbers) {
        if (i == array.length) return true;
        for(int k : numbers) {
            array[i] = k;
            if (isValid(n, s, array)) {
                Set<Integer> newNumbers = new HashSet<Integer>(numbers);
                newNumbers.remove(k);
                if(magic(n, s, i+1, array, newNumbers)) return true;
            }
        }
        array[i] = 0;
        return false;
    }

    private static boolean isValid(int n, int s, int[] array) {
        for(int i = 0; i < n; i++) {
            if(! test(n,s,n*i,1,array) || ! test(n,s,i,n,array)) return false;
        }
        return test(n,s,0,n+1,array) && test(n, s,(n-1),n-1,array);
    }

    private static boolean test(int n, int s, int start, int step, int[] array){
        int sum = 0;
        for(int i = start; n > 0; i+=step, n--) {
            int v = array[i];
            sum += v;
            if(v == 0) {
                return true;
            }
        }
        return sum == s;
    }

    private static Set<Integer> getNumbers(int n) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 1; i <= n*n; i++) {
            set.add(i);
        }
        return set;
    }
}
```

5x5 scheint aber zu dauern...


----------



## ernst (3. Apr 2012)

>
>2. Hier mal der Quellcode, den ich damals zusammen getippelt habe. Zwar ist auch der in manchen 
>Punkten verbesserungswürdig, aber er ist zumindest nicht schlecht.
>Versuch ihn mal zu verstehen und verfolge mal, was bei einem durchlauf passiert.
>
Danke für den Quellcode

2) 
Die folgende Lösung ist kein magisches Quadrat
7 8 9 5 2 3 4 6 1
bedeutet
7 8 9 
5 2 3 
4 6 1
Hier sind nicht alle Reihensummen gleich.
(bei der Lösung soll mathematisches Wissen nicht berücksichtigt werden, wie z.B. dass
die Reihensummen gleich 15 sein müssen).


3) Mir würde genügen:
Was ist das _Prinzip_ des Backtracking beim Magischen Quadrat?


mfg
Ernst


----------



## Landei (3. Apr 2012)

Das Prinzip des Backtracking ist immer gleich: Der Problembereich wird als Entscheidungsbaum aufgefasst. Auf diesem startet man eine Tiefensuche, nur dass man immer einen Knoten zurückgeht und weitere Lösungen sucht, wenn man einmal nicht weiterkommt.

Die Reihensumme braucht man für eine effektive Beschränkung der Suche. Man braucht dafür auch keine Formel, sondern kann einfach die Zahlen von 1 bis n*n aufsummieren und durch n teilen.


----------



## ernst (3. Apr 2012)

Landei hat gesagt.:


> Hier eine Version, die auch für 4x4 läuft:



Hallo Landei,
Danke für den Quellcode.

1) Dein Programm verwendet mathematisches Wissen:
Reihensumme im 4x4 Feld ist z.B. 34
Kannst du den Quellcode angeben, der kein "mathematisches Wissen" verwendet?

2) Wie wirkt sich dies auf die Laufzeit aus ?

3) Mir würde genügen, wenn du mir verbal das _Prinzip_ des Backtracking beim Magischen Quadrat angibst.

mfg
Ernst


----------



## Landei (3. Apr 2012)

Hast du gelesen, was ich geschrieben habe? 

Statt [c]int s = (n*n*n+n)/2;[/c] einfach...


```
int s = 0;
        for(int i = 1; i <= n*n; i++) {
            s += i;
        }            
        s /= n;
```

Die Forderung, auf "mathematisches Wissen" zu verzichten, ist übrigens absurd, weil man dafür keine genaue Grenze angeben kann. Ist mein Test auf Reihensumme der Diagonalen schon "mathematisches Wissen"? Oder der Zugriff auf ein 1D-Array, als ob es ein 2D-Array wäre?


----------



## Sonecc (3. Apr 2012)

[EDIT]Nochmal eine verbesserte Version. Diese funktioniert nun auch mit 4x4, braucht dafür aber ziemlich lange. 5x5 würde ich nicht ausprobieren[/EDIT]

```
import java.util.Random;


public class Magic {
	
	public static int counter;
	
	public static void main(String[] args) {
		int s = 4;
		int[][] feld = new int[s][s];
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				feld[i][j] = 0;
			}
		}
		Random rand = new Random();
		int val = rand.nextInt(9)+1;
		feld[0][0] = val;
		Magic magic = new Magic(feld);
		long start = System.currentTimeMillis();
		magic.generate();
		long end = System.currentTimeMillis();
		long time = end - start;
		System.out.println("Needed " + time + " ms with " + counter + " recursive calls");
		System.out.println(magic.toString());
	}
	
	private int[][] feld;
	private int size;

	public Magic(int size) {
		this(new int[size][size]);
	}
	
	public Magic(int[][] feld) {
		if (feld.length > 9 || feld.length < 2) {
			throw new IllegalArgumentException("Invalid starting field");
		}
		this.feld = feld;
		this.size = feld.length;
	}
	
	public boolean generate() {
		return generate(0,0);
	}
	
	private boolean generate(int i, int j) {
		counter++;
		if (j == size) {
			i++;
			if (i == size) {
				return true;
			}
			j = 0;
		}
		if (feld[i][j] > 0) {
			return generate(i,j+1);
		}
		for (byte val = 1; val < size*size+1; val++) {
			if (check(i, j, val)) {
				feld[i][j] = val;
				if (generate(i, j+1)) {
					return true;
				}
			}
		}
		feld[i][j] = 0;
		return false;
	}

	private boolean check(int i, int j, byte val) {
		counter++;	
		for (int col = 0; col < size; col++) {
			for (int row = 0; row < size; row++) {
				if (feld[row][col] == val) {
					return false;
				}
			}
		}
		int sum = 0;
		for (int col = 0; col < size; col++) {
			if (feld[0][col] != 0) {
				sum+= feld[0][col];
			} else {
				return true;
			}
		}
		int rowSum = 0;
		int colSum = 0;
		for (int col = 0; col < size; col++) {
			if (col == j) {
				rowSum += val;
			} else if (feld[i][col] != 0) {
				rowSum += feld[i][col];
			} else {
				return true; 
			}
		}
		for (int row = 0; row < size; row++) {
			if (row == i) {
				colSum += val;
			} else if (feld[row][j] != 0) {
				colSum += feld[row][j];
			} else {
				colSum = -1;
				break;
			}
		}
		if (rowSum == sum) {
			if (colSum > 0 && colSum == sum) {
				return true;
			} else if (colSum == -1) {
				return true;
			}
		}
		return false;
	}
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int row = 0; row < size; row++) {
			for (int col = 0; col < size; col++) {
				sb.append(" " + feld[row][col]);
			}
			sb.append("\n");
		}
		sb.append("\n");
		return sb.toString();
	}
}
```


----------



## ernst (3. Apr 2012)

Landei hat gesagt.:


> Die Reihensumme braucht man für eine effektive Beschränkung der Suche. Man braucht dafür auch keine Formel, sondern kann einfach die Zahlen von 1 bis n*n aufsummieren und durch n teilen.



Bei mir braucht mein Programm für ein 3x3-Feld ca. 9 Minuten.
Ich verwende allerdings kein mathematisches Wissen.
Deswegen interessiert mich, ob bei mir die hohe Laufzeit davon herrührt.
Deshalb würde mich interessieren, was bei dir passiert, wenn du diese Formel nicht verwendest?

mfg
Ernst


----------



## Landei (3. Apr 2012)

Nochmal, "mathematisches Wissen" lässt sich nicht klar abgrenzen. Wenn ich die Zahlen von 1 bis n*n gleichmäßig auf n Zeilen aufteile, ergibt sich nun einmal eine Reihensumme von sum(1..n*n)/n, das kann man ganz anschaulich mit Bauklötzchen nachbauen. Egal was du für ein Programm du schreibst, du verwendest immer "mathematisches Wissen" - bewusst oder unbewusst, implizit oder explizit.


----------



## ernst (3. Apr 2012)

Sonecc hat gesagt.:


> Hier eine verbesserte Version für 3x3 mit korrekter Berechnung. Sorry für den falschen Code vorher:



 5 9 1
 2 7 6
 3 4 8

Diese Lösung ist nicht korrekt:
5+2+3 != 5+7+8



mfg
Ernst


----------



## ernst (3. Apr 2012)

Landei hat gesagt.:


> Nochmal, "mathematisches Wissen" lässt sich nicht klar abgrenzen. Wenn ich die Zahlen von 1 bis n*n gleichmäßig auf n Zeilen aufteile, ergibt sich nun einmal eine Reihensumme von sum(1..n*n)/n, das kann man ganz anschaulich mit Bauklötzchen nachbauen. Egal was du für ein Programm du schreibst, du verwendest immer "mathematisches Wissen" - bewusst oder unbewusst, implizit oder explizit.



Mit "mathematischem Wissen" meine ich hier ganz konkret informal spezifiziert:
Die Nichtverwendung dieser Formel.
Wie wirkt sich diese auf die Laufzeit aus?

mfg
Ernst


----------



## Sonecc (3. Apr 2012)

ernst hat gesagt.:


> 5 9 1
> 2 7 6
> 3 4 8
> 
> ...




Richtig. die Diagonalen werden nicht verarbeitet... Wie wäre es, wenn du das einbaust?


----------



## ernst (3. Apr 2012)

Sonecc hat gesagt.:


> Richtig. die Diagonalen werden nicht verarbeitet... Wie wäre es, wenn du das einbaust?


Auch die Spaltensummen sind nicht gleich.

mfg
Ernst


----------



## ernst (3. Apr 2012)

Landei hat gesagt.:


> Hast du gelesen, was ich geschrieben habe?
> 
> Statt [c]int s = (n*n*n+n)/2;[/c] einfach...
> 
> ...



Ich will ein Programm, in dem die Nichtverwendung dieser Formel benutzt wird bzw. auch nicht 
die (wie du es vorgeschlagen hast) Berechnung durch ein Unterprogramm.
Also NICHT:

```
int s = 0;
        for(int i = 1; i <= n*n; i++) {
            s += i;
        }            
        s /= n;
```
oder eine anderes Unterprogramm, das die Formel (n*n*n+n)/2 berechnet.

Wie wirkt sich diese auf die Laufzeit aus?

mfg
Ernst


----------



## Landei (3. Apr 2012)

Enorm. Mit der Formel kannst du schon bei drei Zahlen erkennen, dass es damit nicht weitergeht, ohne die Formel könntest du theoretisch erst nach fünf Zahlen einige (aber nicht alle) falschen Fälle ausschließen. Beim Backtracking ist es enorm wichtig, Sackgassen möglichst frühzeitig zu erkennen.

Alles was du machen musst, ist in meinem Code die isValid-Methode so zu ändern, dass sie kein s mehr verwendet (das dann ganz wegfallen kann). Im Prinzip brauchst du nur beim "Füllstand" 2n, 3n... zu testen, ob die gerade fertige Zeile die gleiche Summe hat wie die vorhergehende, und dann noch ganz am Ende Spalten und Diagonalen. 

Allerdings wäre wahrscheinlich eine andere Füllstrategie etwas schneller (z.B. erste Zeile, dann den Rest erste Spalte, den Rest zweite Zeile u.s.w.).


----------



## Landei (3. Apr 2012)

Ein für 4x4 recht schneller Algorithmus, allerdings durch Zufallsauswahl statt Backtracking:


```
import java.util.Random;

public class Magic {

    private static Random random = new Random();

    public static void main(String[] args) {
        int n = 4;
        int[] array = magic(n);
        for (int i = 0; i < n * n; i++) {
            System.out.printf("%2d ", array[i]);
            if ((i + 1) % n == 0) System.out.println();
        }
    }

    private static int[] magic(int n) {
        int[] array = getArray(n);
        for (int v = value(n, array); v > 0; ) {
            int x = random.nextInt(n * n);
            int y = random.nextInt(n * n);
            swap(array, x, y);
            int w = value(n, array);
            if (w < v || random.nextInt(v * v * v) == 0) {
                v = w;
            } else {
                swap(array, x, y);
            }
        }
        return array;
    }

    private static void swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }

    private static int value(int n, int[] array) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int row = 0; row < n; row++) {
            int s = 0;
            for (int x = 0; x < n; x++) s += array[x + row * n];
            if (s < min) min = s;
            if (s > max) max = s;
        }
        for (int col = 0; col < n; col++) {
            int s = 0;
            for (int y = 0; y < n; y++) s += array[n * y + col];
            if (s < min) min = s;
            if (s > max) max = s;
        }
        int s = 0;
        for (int i = 0; i < n; i++) {
            s += array[n * i + i];
        }
        if (s < min) min = s;
        if (s > max) max = s;
        s = 0;
        for (int i = 0; i < n; i++) {
            s += array[n * i + (n - i - 1)];
        }
        if (s < min) min = s;
        if (s > max) max = s;
        return max - min;
    }

    private static int[] getArray(int n) {
        int[] array = new int[n * n];
        for (int i = 0; i < n * n; i++)
            array[i] = i + 1;
        return array;
    }
}
```


----------



## mohrenkopf (4. Apr 2012)

Kannst du das brauchen?
Die checkMagic-methode ist sehr hart auf 3x3-Quadrate kodiert, aber das sollte das kleinste Problem darstellen, das zu ändern.

Gruß mohrenkopf


[Java]
package MagischesQuadrat;

/**
 *
 * @author mohrenkopf
 */
public class Quadrat
{
    static long counterChecks = 0;
    static long counterMagic = 0;
    static int EMPTY = 0;
    static int[] a = new int[9];

    //Alle Felder leer
    static void initQuadrat()
    {
        for ( int i = 0; i < a.length; i++ )
        {
            a_ = EMPTY;
        }
    }

    public static void plaziereZifferAufAlleFreienPlätze( int ziffer )
    {
        for ( int platz = 0; platz < 9; platz++ )
        {
            if ( platzFrei( platz ) )
            {
                plaziereZifferAufPlatz( ziffer, platz );
            }
        }
    }

    private static void plaziereZifferAufPlatz( int ziffer, int platz )
    {
        a[platz] = ziffer;

        //Wenn das die letze Ziffer ist:
        if ( ziffer == 9 )
        {
            checkMagic();
        }
        else
        {
            //andere Ziffern auch noch...
            plaziereZifferAufAlleFreienPlätze( ziffer + 1 );
        }
        //Und dann Ziffer wieder wegnehmen
        a[platz] = EMPTY;
    }

    private static boolean platzFrei( int platz )
    {
        return a[platz] == EMPTY;
    }

    private static void checkMagic()
    {
        counterChecks++;

        int summeErsteReihe = a[0] + a[1] + a[2];

        if ( ( summeErsteReihe == a[3] + a[4] + a[5] )
                && ( summeErsteReihe == a[6] + a[7] + a[8] )
                && ( summeErsteReihe == a[0] + a[3] + a[6] )
                && ( summeErsteReihe == a[1] + a[4] + a[7] )
                && ( summeErsteReihe == a[2] + a[5] + a[8] )
                && ( summeErsteReihe == a[0] + a[4] + a[8] )
                && ( summeErsteReihe == a[2] + a[4] + a[6] ) )
        {
            counterMagic++;
            for ( int i = 0; i < a.length; i++ )
            {
                System.out.print( a );
            }
            System.out.println();
        }
    }

    public static void main( String[] args )
    {
        initQuadrat();
        plaziereZifferAufAlleFreienPlätze( 1 );
        System.out.printf( "Berechnet %d quadrate, davon %d magisch.%n", counterChecks, counterMagic );
    }
}
[/code]_


----------



## Sonecc (4. Apr 2012)

ernst hat gesagt.:


> Auch die Spaltensummen sind nicht gleich.
> 
> mfg
> Ernst



Stimmt, hab ich übersehen..


----------



## ernst (4. Apr 2012)

Landei hat gesagt.:


> Enorm. Mit der Formel kannst du schon bei drei Zahlen erkennen, dass es damit nicht weitergeht, ohne die Formel könntest du theoretisch erst nach fünf Zahlen einige (aber nicht alle) falschen Fälle ausschließen. Beim Backtracking ist es enorm wichtig, Sackgassen möglichst frühzeitig zu erkennen.
> 
> Alles was du machen musst, ist in meinem Code die isValid-Methode so zu ändern, dass sie kein s mehr verwendet (das dann ganz wegfallen kann). Im Prinzip brauchst du nur beim "Füllstand" 2n, 3n... zu testen, ob die gerade fertige Zeile die gleiche Summe hat wie die vorhergehende, und dann noch ganz am Ende Spalten und Diagonalen.
> 
> Allerdings wäre wahrscheinlich eine andere Füllstrategie etwas schneller (z.B. erste Zeile, dann den Rest erste Spalte, den Rest zweite Zeile u.s.w.).



Mein etwas abgeändertes Programm (siehe unten) braucht jetzt (bei meinem AMD 1,8 GHz 768 MB RAM) nur noch 46 Sekunden.
Ist das (ohne die Formel zu benutzen) bei einem 3x3 Feld eine akzeptable Zeit, oder bekommst du es mit Backtracking schneller hin ?

mfg
Ernst




```
package magischesquadrat5;
import java.util.*;
import java.util.Date;

public class MainMagischesQuadrat5 {

    public static void main(String[] args) {
        boolean b;
        int  back;
        Neunerfeld feld=new Neunerfeld();
        feld.kopieren(0,0,0,0,0,0,0,0,0);
        feld.kopieren(0,0,0,0,0,0,0,0,2);
        feld.kopieren(0,0,0,0,0,0,0,0,0);
        //feld.kopieren(8,3,4,1,5,9,6,7,2);
        //feld.kopieren(0,0,0,1,5,9,6,7,2);
        MyMath m = new MyMath();

        long start, stop, dauer;
        // Wert in Millisekunden
        start = new Date().getTime();

        b=feld.korrekt();
        System.out.println("Das Feld muss korrekt sein, sonst wird die Berechnung falsch");
        System.out.println("Das Feld ist: " +b);
        back=m.N(feld);
        System.out.println("back="+back);
        //back.array9.printFeld();
        // Wert in Millisekunden
        stop = new Date().getTime();

        // Wert in Sekunden
        dauer = (stop -start)/1000;
        System.out.println("Laufzeit des Programms="+dauer+" Sekunden");
    }

}





class MyMath{
/**
* prueft, ob ein Neunerfeld (das z.B. aus lauter Nullen besteht)
* magisch ergÃ¤nzt werden kann. Magisch ergÃ¤nzt werden bedeutet, daÃŸ ein Neunerfeld
* weiter so mit verschiedenen Zahlen belegt werden kann,
* bis es vollbelegt und magisch wird.
* <b>Beispiel:</b><br>
* 1)
* 0 0 0
* 0 0 0
* 0 0 0
* dieses Neunerfeld kann magisch ergaenzt werden z.B. zum
* magisch zu ergaenzenden Neunerfeld:
* 2 7 6
* 9 5 1
* 4 3 8
*
* 2)
* 1 2 3
* 4 5 0
* 6 0 0
* dieses Neunerfeld kann nicht magisch ergaenzt werden,
* da zwei Reihensummen schon verschieden sind.
* Es ist ein Endfeld.
* Wenn es nicht magisch ergaenzt werden kann, wird das
* magisch zu ergaenzenden Neunerfeld gesetzt auf:
* -1 -1 -1
* -1 -1 -1
* -1 -1 -1
* @param feld (i) ist das auf magische ErgÃ¤nzbarkeit zu prÃ¼fende Feld
* @return (o) B.1 : Neunerfeld ist magisch ergÃ¤nzbar mit magisch
*                   ergÃ¤nztem Feld B.array9
*             B.-1: Neunerfeld ist nicht magisch ergÃ¤nzbar
*/

    public int N(Neunerfeld feld){
        int pos;
        int value;
        int tempValue;
        boolean erg;
        int back;

        pos = feld.firstUnbelegtePosition();
        while(pos<9){
            for(value=1; value<10; value++){
                // prÃ¼ft, ob im Neunerfeld "feld" noch feld[pos]=value gesetzt
                // werden kÃ¶nnte
                erg=feld.istNachfolger(pos, value);
                if(erg==true){
                    tempValue=feld.feld9[pos];
                    feld.feld9[pos]=value;
                    back=N(feld);
                    if(back==1){
                        return 1;
                    }
                    feld.feld9[pos]=tempValue;
                }
            }
            pos=feld.nextUnbelegtePosition(pos);
        }
        // Es gibt keine Nachfolger:
        if(feld.istMagisch()){
            feld.printFeld();
            back = 1;
        }
        else{
            //System.out.println("nicht Magisch");
            back = -1;
        }
        return(back);
    }
}





class Neunerfeld {
    public int feld9[];

    public Neunerfeld() {
        feld9 = new int[9];
    }

    public void set(int stelle, int wert) {
        feld9[stelle] = wert;
    }

    public int get(int stelle) {
        return feld9[stelle];
    }

    public void kopieren(Neunerfeld pFeld){
        for(int i=0;i<9;i++){
            this.set(i,pFeld.get(i));
        }
    }

    public void kopieren(int z){
        for(int i=0;i<9;i++){
            feld9[i]=z;
        }
    }

    public void kopieren(int z1, int z2, int z3, int z4, int z5, int z6, int z7, int z8, int z9){
        feld9[0]=z1;
        feld9[1]=z2;
        feld9[2]=z3;
        feld9[3]=z4;
        feld9[4]=z5;
        feld9[5]=z6;
        feld9[6]=z7;
        feld9[7]=z8;
        feld9[8]=z9;
    }


    public int nextUnbelegtePosition(int posAlt){
        for(int i=posAlt+1;i<9;i++){
            if(feld9[i]==0){
                return i;
            }
        }
        return 9;
    }

    public int firstUnbelegtePosition(){
        for(int i=0;i<9;i++){
            if(feld9[i]==0){
                return i;
            }
        }
        return 9;
    }


/**
* Eine Zelle eines Feldes ist unbelegt, wenn sie den Wert 0 hat.
* Sie ist belegt, wenn sie als Wert 1, 2, 3, 4, 5, 6, 7, 8 oder 9 hat
* Es wird geprÃ¼ft, ob jede Zelle des Feldes mit einer ganzen Zahl zwischen
* 1 und 9 belegt ist.
* @return (o) true : Neunerfeld ist voll belegt
*             false: Neunerfeld ist nicht voll belegt
*/
    public boolean istVollbelegt(){
        int zaehler=0;
        int i;
        boolean back;
        for (i = 0; i < 9; i++) {
            if (feld9[i] != 0) {
                zaehler++;
            }
        }
        if(zaehler==9){
            back=true;
        }
        else{
            back=false;
        }
        return back;
    }

/**
* prueft nach, ob ein Neunerfeld magisch ist, d.h. voll belegt
* und alle Zeilen, Spalten und Diagonalensummen gleich sind.
* @return (o) true : Neunerfeld ist magisch
*             false: Neunerfeld ist nicht magisch
*/
   public boolean istMagisch(){
        boolean back;

        if(istVollbelegt()){
            back = sindSummenKorrekt();
        }
        else{
            back=false;
        }
        return back;
    }


/**
* Ein Neunerfeld, das kein Endfeld ist, hat noch weiter(e) Nachfolger, kann also
* noch weiter mit Zahlen 1, 2, 3, .., 9 an einer bestimmten vorgegeben,
* Stelle belegt werden. Stellt fest, ob dies dann ein Nachfolger ist.
* @param pStelle (i) an dieser Stelle wird das Neunerfeld belegt
* @param pZahl   (i) an der Stelle pStelle wird das Neunerfeld mit dem Wert
*                    pZahl belegt
* @return (o) true:  Das Feld feld9+feld9[pStelle]=pZahl ist ein Nachfolger
*             false: sonstdas Neunerfeld, das um den Wert feld[pStelle]=pZahl
*/
    public boolean  istNachfolger(int pStelle, int pZahl) {
        boolean erg;
        erg=korrekt(pStelle, pZahl);
        return erg;
    }


/**
* prueft, ob das Neunerfeld an der Stelle (=Index) pos mit der Wert value
* belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
* ganze Zahl zwischen 1 und 9 steht, oder dadurch das Neunerfeld
* zwei gleiche Zahlen bekommen wÃ¼rde.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos wÃ¼rde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen
*             false: sonst
*/
    boolean sindZahlenKorrekt(int pos, int value){
        boolean back=true;
        int i;
        if(feld9[pos]!=0){
            back=false;
        }
        else{
            for(i=0;i<9;i++){
                if(feld9[i]==value){
                    back=false;
                    break;
                }
            }
        }
        return back;
    }


/**
* prueft, ob alle unbelegten Felder des Neunerfeldes verschieden sind.
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen
*             false: sonst
*/
    boolean sindZahlenKorrekt(){
        int i, j;
        for(i=0;i<9;i++){
            for(j=0;j<9;j++){
                if(i!=j && feld9[i]!=0 && feld9[j]!=0){
                    if(feld9[i]==feld9[j]){
                        return false;
                    }
                }
            }
        }
        return true;
    }


/**

* prueft, ob die Zeilen, Spalten und Diagonalensummen aller
* Reihen, die keine unbelegten Zellen enthalten, gleich sind, falls
* das Neunerfeld an der Stelle (=Index) pos mit dem Wert value
* belegt werden wÃ¼rde.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos wÃ¼rde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Zeilen, Spalten und Diagonalensummen aller Reihen,
*                    die keine unbelegten Zellen enthalten, gleich sind.
*             false:  sonst
*/
    public boolean sindSummenKorrekt(int pos, int zahl){
        int zahlAlt=this.feld9[pos];
        this.feld9[pos]=zahl;
        int i;
        int[] temp = new int[9];
        int len=0;
        boolean korrekt = true;

        if(feld9[0]!=0 && feld9[1]!=0 && feld9[2]!=0){
            temp[len]=feld9[0]+feld9[1]+feld9[2];
            len++;
        }

        if(feld9[3]!=0 && feld9[4]!=0 && feld9[5]!=0){
            temp[len]=feld9[3]+feld9[4]+feld9[5];
            len++;
        }

        if(feld9[6]!=0 && feld9[7]!=0 && feld9[8]!=0){
            temp[len]=feld9[6]+feld9[7]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[3]!=0 && feld9[6]!=0){
            temp[len]=feld9[0]+feld9[3]+feld9[6];
            len++;
        }

        if(feld9[1]!=0 && feld9[4]!=0 && feld9[7]!=0){
            temp[len]=feld9[1]+feld9[4]+feld9[7];
            len++;
        }

        if(feld9[2]!=0 && feld9[5]!=0 && feld9[8]!=0){
            temp[len]=feld9[2]+feld9[5]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[4]!=0 && feld9[8]!=0){
            temp[len]=feld9[0]+feld9[4]+feld9[8];
            len++;
        }

        if(feld9[2]!=0 && feld9[4]!=0 && feld9[6]!=0){
            temp[len]=feld9[2]+feld9[4]+feld9[6];
            len++;
        }

        // Testen ob alle Summen gleich sind
        if(len==0){
            korrekt=true;
        }
        else{
            for(i=0;i<len;i++){
                if(temp[0]!=temp[i]){
                    korrekt=false;
                    break;
                }
            }
        }
        this.feld9[pos]=zahlAlt;
        return korrekt;
    }



/**
* prueft, ob die Zeilen, Spalten und Diagonalensummen aller
* Reihen, die keine unbelegten Zellen enthalten, gleich sind.
* @return (o) true : Zeilen, Spalten und Diagonalensummen aller Reihen,
*                    die keine unbelegten Zellen enthalten, gleich sind.
*             false:  sonst
*/
    public boolean sindSummenKorrekt(){
        int i;
        int[] temp = new int[9];
        int len=0;
        boolean korrekt = true;

        if(feld9[0]!=0 && feld9[1]!=0 && feld9[2]!=0){
            temp[len]=feld9[0]+feld9[1]+feld9[2];
            len++;
        }

        if(feld9[3]!=0 && feld9[4]!=0 && feld9[5]!=0){
            temp[len]=feld9[3]+feld9[4]+feld9[5];
            len++;
        }

        if(feld9[6]!=0 && feld9[7]!=0 && feld9[8]!=0){
            temp[len]=feld9[6]+feld9[7]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[3]!=0 && feld9[6]!=0){
            temp[len]=feld9[0]+feld9[3]+feld9[6];
            len++;
        }

        if(feld9[1]!=0 && feld9[4]!=0 && feld9[7]!=0){
            temp[len]=feld9[1]+feld9[4]+feld9[7];
            len++;
        }

        if(feld9[2]!=0 && feld9[5]!=0 && feld9[8]!=0){
            temp[len]=feld9[2]+feld9[5]+feld9[8];
            len++;
        }

        if(feld9[0]!=0 && feld9[4]!=0 && feld9[8]!=0){
            temp[len]=feld9[0]+feld9[4]+feld9[8];
            len++;
        }

        if(feld9[2]!=0 && feld9[4]!=0 && feld9[6]!=0){
            temp[len]=feld9[2]+feld9[4]+feld9[6];
            len++;
        }

        // Testen ob alle Summen gleich sind
        if(len==0){
            korrekt=true;
        }
        else{
            for(i=0;i<len;i++){
                if(temp[0]!=temp[i]){
                    korrekt=false;
                    break;
                }
            }
        }
        return korrekt;
    }



/**
* prueft, ob das Neunerfeld an der Stelle (=Index) pos mit der Wert value
* belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
* ganze Zahl zwischen 1 und 9 steht, oder dadurch das Neunerfeld
* zwei gleiche Zahlen bekommen wÃ¼rde.
* @param pos   (i) an dieser Stelle wird das Neunerfeld belegt
* @param value (i) an der Stelle pos wÃ¼rde das Neunerfeld mit dem Wert
*                  value belegt
* @return (o) true : Das mit value an der bis dahin noch unbelegten Stelle
*                    pos belegte Neunerfeld hat keine zwei gleiche Zahlen und
*                    alle Summen sind gleich
*             false: sonst
*/
    boolean korrekt(int pos, int value){
        boolean back=true;
        back=sindZahlenKorrekt(pos,value) && sindSummenKorrekt(pos,value);
        return back;
    }

/**
* prueft, ob alle Zahlen des Neunerfeld korrekt sind.
* @return (o) true : keine zwei gleiche Zahlen an unbelegten Elementen.
*                    und alle Summen gleich
*             false: sonst
*/
    boolean korrekt(){
        boolean back=true;
        back=sindSummenKorrekt() && sindZahlenKorrekt();
        return back;
    }



// Ausgabe auf Bildschirm
/**
* Gibt alle Zellen des Feldes auf dem Bildschirm aus
*/

    public void printFeld(){
        for(int k=0;k<9;k++){
            if(k%3==0)
                System.out.println();
                System.out.print(" "+feld9[k]);
            }
            System.out.println();
    }
}
```


----------



## Landei (4. Apr 2012)

Schlecht. 

Diese Variante läuft deutlich unter einer Sekunde:


```
import java.util.HashSet;
import java.util.Set;

public class Magic {

    public static void main(String... args) {
        int n = 3;
        int[] array = magic(n);
        for(int i = 0; i < n*n; i++) {
            System.out.printf("%2d ",array[i]);
            if ((i+1) % n == 0) System.out.println();
        }
    }

    private static int[] magic(int n) {
        int[] array = new int[n*n];
        Set<Integer> numbers = getNumbers(n);
        if(! magic(n, 0, array,numbers)) {
            throw new RuntimeException("No solution for magic square.");
        }
        return array;
    }

    private static boolean magic(int n, int i, int[] array, Set<Integer> numbers) {
        if (i == array.length) return isValid(n,array);
        for(int k : numbers) {
            array[i] = k;
            Set<Integer> newNumbers = new HashSet<Integer>(numbers);
            newNumbers.remove(k);
            if(magic(n, i+1, array, newNumbers)) return true;
        }
        array[i] = 0;
        return false;
    }

    private static boolean isValid(int n, int[] array) {
        int s = sum(n,0,n+1,array);
        if (s != sum(n, (n-1),n-1,array)) return false;
        for(int i = 0; i < n; i++) {
            if(sum(n,n*i,1,array) != s || sum(n,i,n,array) != s) return false;
        }
        return true;
    }

    private static int sum(int n, int start, int step, int[] array){
        int sum = 0;
        for(int i = start; n > 0; i+=step, n--) {
            int v = array[i];
            sum += v;
        }
        return sum;
    }

    private static Set<Integer> getNumbers(int n) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 1; i <= n*n; i++) {
            set.add(i);
        }
        return set;
    }
}
```

Aber für 4x4 ist sie schon zu "brute force".


----------



## ernst (4. Apr 2012)

Landei hat gesagt.:


> Schlecht.
> 
> Diese Variante läuft deutlich unter einer Sekunde:
> 
> Aber für 4x4 ist sie schon zu "brute force".



Glückwunsch zu dieser performanten Lösung.

Warum ist aber meine Lösung sooo schlecht ?

mfg
Ernst


----------



## timbeau (4. Apr 2012)

Naja, ich würde Landei nicht als Maßstab für eine gute Lösung nehmen. 

Was ich hier gelernt habe:
<----Landei ---------- andere langjährige Java-Cracks ------------ irgendwer -------------- ich

Du hast einfach viel mehr Kopiervorgänge. Lesbarer aber eben nicht performanter.


----------



## ernst (5. Apr 2012)

Landei hat gesagt.:


> Schlecht.
> Diese Variante läuft deutlich unter einer Sekunde:



Habe den Quellcode angeschaut.
So wie ich die Lösung verstanden habe, funktioniert diese nur für ein beliebiges, unbelegtes Anfangsfeld.
Funktioniert diese auch für ein mit Ziffern vorbelegtes Anfangsfeld?
D.h. Ist z.B. das Feld
145
600
000

magisch ergänzbar?

Wird die Performance schlechter, wenn du dies auch noch in deiner Lösung (mit Backtracking) berücksichtigst

mfg
Ernst


----------



## Landei (5. Apr 2012)

Mit kleinen Änderungen, ja. Du müsstest die erste [c]magic[/c]-Methode ändern:


```
private static int[] magic(int n) {
        int[] array = new int[]{1,4,5,6,0,0,0,0,0};
        Set<Integer> numbers = getNumbers(n);
        for(int i = 0; i < array.length; i++) {
           numbers.remove(array[i]);
        }   
        if(! magic(n, 4, array,numbers)) {
            throw new RuntimeException("No solution for magic square.");
        }
        return array;
    }
```

Da ich die Korrektheit einer Lösung nur ganz am Ende teste, macht das keinen Unterschied.


----------



## ernst (5. Apr 2012)

Landei hat gesagt.:


> Mit kleinen Änderungen, ja. Du müsstest die erste [c]magic[/c]-Methode ändern:
> 
> 
> ```
> ...



Wenn ich das Feld wie folgt mit lauter Nullen vorbelege:
int[] array = new int[]{0,0,0,0,0,0,0,0,0};
liefert das Programm die Ausgabe: "No solution for magic square."
Und das ist nicht korrekt.

mfg
Ernst


----------



## Landei (5. Apr 2012)

Das zweite Argument bei [c]if(! magic(n, 4, array,numbers)) [/c] gibt den nächsten Index an, der belegt werden soll, also müsste das dann zu  [c]if(! magic(n, 0, array,numbers)) [/c] geändert werden. Wenn du es ganz allgemein mit beliebiger Vorbelegung haben willst, könnte man die zweite magic-Methode auch so ändern, dass sie selbsttätig nach der ersten 0 sucht, so dass man keinen Index braucht (auch wenn das einen Tick langsamer ist).


----------



## ernst (6. Apr 2012)

Landei hat gesagt.:


> Das zweite Argument bei [c]if(! magic(n, 4, array,numbers)) [/c] gibt den nächsten Index an, der belegt werden soll, also müsste das dann zu  [c]if(! magic(n, 0, array,numbers)) [/c] geändert werden. Wenn du es ganz allgemein mit beliebiger Vorbelegung haben willst, könnte man die zweite magic-Methode auch so ändern, dass sie selbsttätig nach der ersten 0 sucht, so dass man keinen Index braucht (auch wenn das einen Tick langsamer ist).



Nach deiner Erklärung wäre der nächste Index der belegt werden soll 
beim Feld 0,0,0,1,5,9,6,7,2) die 0, also:

int[] array = new int[]{0,0,0,1,5,9,6,7,2};
und 
if(! magic(n, 0, array,numbers)) {
    throw new RuntimeException("No solution for magic square.");
}

liefert aber ein falsches Ergebnis, auch wenn man einen beliebigen anderen Wert statt 0 wählt.
Das Feld
0,0,0,
1,5,9,
6,7,2

läßt sich aber magisch ergänzen.

mfg
Ernst


----------



## Landei (6. Apr 2012)

Du bist wie ein Kunde: Ständig die Anforderungen ändern 


```
import java.util.HashSet;
import java.util.Set;

public class Magic {

    public static void main(String... args) {
        int n = 3;
        int[] array = magic(3,   0,0,0,1,5,9,6,7,2);
        for(int i = 0; i < n*n; i++) {
            System.out.printf("%2d ",array[i]);
            if ((i+1) % n == 0) System.out.println();
        }
    }

    private static int[] magic(int n, int... array) {
        if (n*n != array.length) {
            throw new IllegalArgumentException("need an array of length n*n");
        }
        Set<Integer> numbers = getNumbers(n);
        for(int k : array) {
            numbers.remove(k);
        }
        if(! magic(n, array,numbers)) {
            throw new RuntimeException("No solution for magic square.");
        }
        return array;
    }

    private static boolean magic(int n, int[] array, Set<Integer> numbers) {
        int i = -1;
        for(int j = 0; j < array.length; j++) {
            if (array[j] == 0) {
                i = j;
                break;
            }
        }
        if (i == -1) return isValid(n,array);
        for(int k : numbers) {
            array[i] = k;
            Set<Integer> newNumbers = new HashSet<Integer>(numbers);
            newNumbers.remove(k);
            if(magic(n, array, newNumbers)) return true;
        }
        array[i] = 0;
        return false;
    }

    private static boolean isValid(int n, int[] array) {
        int s = sum(n,0,n+1,array);
        if (s != sum(n, (n-1),n-1,array)) return false;
        for(int i = 0; i < n; i++) {
            if(sum(n,n*i,1,array) != s || sum(n,i,n,array) != s) return false;
        }
        return true;
    }

    private static int sum(int n, int start, int step, int[] array){
        int sum = 0;
        for(int i = start; n > 0; i+=step, n--) {
            int v = array[i];
            sum += v;
        }
        return sum;
    }

    private static Set<Integer> getNumbers(int n) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 1; i <= n*n; i++) {
            set.add(i);
        }
        return set;
    }
}
```


----------



## ernst (7. Apr 2012)

Landei hat gesagt.:


> Du bist wie ein Kunde: Ständig die Anforderungen ändern


Der "Kunde" dankt recht herzlich.
Habe jetzt entdeckt, warum bei mir das Programm so langsam ist.
Ich versuche mathematisch ganz allgemein einen Zusammenhang zwischen induktiv definierten Mengen und einer Rekursion darzustellen.
Das geht bis jetzt einigermassen, nur gab es bei der Umsetzung in ein Programm schlechte Laufzeiten.
Das magische Quadrat war dafür ein Beispiel.

mfg
Ernst


----------

