Magisches Quadrat

Bitte aktiviere JavaScript!
Hallo,
ich wollte magische Quadrate durch Rekursion berechnen. Für die Seitenlänge 3 klappt es auch, als Ausgabe bekomme ich:
Java:
2 9 4 
7 5 3 
6 1 8
Ein Quadrat der Seitenlänge 4 kann aber auch nach über 2 Stunden nicht berechnet werden.
Ist die Laufzeit im Vergleich zur Seitenlänge 3 soviel höher?

Hier mal meine Lösemethode:
Java:
private boolean loese(int x, int y,int quadrat[][]) {
       
           
        if(x==quadrat.length && y == quadrat.length-1 && istMagisch(quadrat)==true) { 
            return true; // letztes Feld gefüllt und Quadrat ist magisch
        }
           
        if(x==quadrat.length) { // nächste Zeile
            y++;
            x = 0;
        }
       
        if(x < quadrat.length && y<quadrat.length && quadrat[x][y]!=0) { // Felder, die schon gefüllt sind übersrpingen
            return loese(x+1, y, quadrat);
        }
       
        for(int i=1; i<=quadrat.length * quadrat.length; i++) {
           
            if(enthalten(quadrat, i) == false) { // Zahl noch nicht gesetzt                
               
                quadrat[x][y] = i;               
               
                if(loese(x+1, y, quadrat) == true) {                   
                    return true;
                }       
               
            }
           
        }
       
        if(x < quadrat.length && y < quadrat.length) {       
            quadrat[x][y] = 0;
        }
       
        return false;
    }
Danke im Vorraus.
 
A

Anzeige




Vielleicht hilft dir unser Java-Tutorial hier weiter —> (hier klicken)
Multithreading könnte dein problem lösen ;)
Nein.
Der Backtracking-Algorithmus hat eine Komplexitätsklasse von O(n!) - wenn `n` die Anzahl der Zellen des Magic Squares darstellt. Vergleichbar etwa mit dem NQueens-Problem. Somit steigt die Laufzeit bei einer Erhöhung von `n` von 3*3=9 auf 4*4=16 um den Faktor (16! - 9!) / 9! = 57.657.599, also dauert knapp 58 Millionen mal länger! Da helfen dir auch 8 oder 16 Threads nichts mehr.
 
OK,danke. Ich hatte mich nur gewundert weil in einem Buch als Aufgabe steht,das man alle magischen Quadrate der Ordnung 4 berechnen soll, ich glaube das sind mehr als 1000 verschiedene.
 
OK macht aber auch nicht so einen Unterschied, man kann nicht alle berechnen und deswegen ist die Aufgabenstellung etwas komisch.
 
Sollst du es denn per Backtracking via Rekursion berechnen? Es gibt ja gerade in dem Wikipedia-Artikel eine lange Auflistung von anderen Algorithmen. Backtracking ist die aller-aller-ineffizienteste Methode - immer (aber auch die generischste, die am wenigsten Voraussetzungen an das zu lösende Problem stellt, weswegen z.B. die Inferenz-Engine in der logischen Programmiersprache Prolog per Backtracking funktioniert).
 
Naja, es gibt noch viele Optimierungen, die du nicht implementiert hast.
Etwa, nicht erst gaaanz am Ende zu prüfen, ob das ganze Quadrat magisch ist, sondern immer auch zwischendurch beim Setzen einer Zelle prüfen, ob dadurch die Zeile, Spalte oder Diagonale ungültig wird, also etwa die sich ergebende Summe größer als N*N ist (wenn N z.B. gleich 4 ist). Dadurch kannst du seeeehr viele Rekursionszweige von vornherein vermeiden und viel Backtracking sparen.
 
Somit steigt die Laufzeit bei einer Erhöhung von `n` von 3*3=9 auf 4*4=16 um den Faktor (16! - 9!) / 9! = 57.657.599, also dauert knapp 58 Millionen mal länger
Das stimmt.... Erhöht sich das n um nur 1....(!!!!) dann beträgt der Wachstumsfaktor x = (((n + 1)^2)!)/((n^2)!)

Sieht man sich dazu den Graphen an, dann verläuft der quasi wie ein gespiegeltes L !!!! ( So: _| )

Bei n=4 könnte es noch gehen, aber danach wird es dann astronomisch....
 
also etwa die sich ergebende Summe größer als N*N ist (wenn N z.B. gleich 4 ist)
Ist die magische Summe nicht (N*N*N+N)/2 ?

Durch vorher überprüfen in Reihen,Spalten und Diagonalen habe ich die Rekursionsaufrufe für n=3 von 187.769 auf 75.408 reduziert, immerhin fast Faktor 3. Was könnte ich sonst noch optimieren ? Für n=4 bekomme ich immer noch kein Ergebnis.
 
Soll es langsam und genau sein oder schnell und fast genau? Was anderes gibts nicht. Das hat Dir doch jetzt schon 5 Leute gesagt. :oops:
 
Ein 4*4 magisches Quadrat kann ich jetzt nach ca. 50 min berechnen, dass erscheint mir aber immer noch als recht langsam. Was könnte noch optimiert werden?
 
A

Anzeige




Hier lernst du alle wichtigen Java-Grundlagen.
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben