Magisches Quadrat

[member42]

Hallo,
ich wollte magische Quadrate durch Rekursion berechnen. Für die Seitenlänge 3 klappt es auch, als Ausgabe bekomme ich:

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:

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.

 

[x46]

Multithreading könnte dein problem lösen

 

[httpdigest]

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.

 

[member42]

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.

 

[httpdigest]

ich glaube das sind mehr als 1000 verschiedene.

Nee, es gibt ganz genau 880 (ohne rotations- und reflektionssymmetrische): https://en.wikipedia.org/wiki/Magic_square#Number_of_magic_squares_of_a_given_order

 

[member42]

OK macht aber auch nicht so einen Unterschied, man kann nicht alle berechnen und deswegen ist die Aufgabenstellung etwas komisch.

 

[httpdigest]

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).

 

[member42]

Die Aufgabe steht im Kapitel über Backtracking, deswegen bin ich davon ausgegangen.

 

[httpdigest]

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.

 

[Xyz1]

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....

 

[member42]

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.

 

[Xyz1]

Soll es langsam und genau sein oder schnell und fast genau? Was anderes gibts nicht. Das hat Dir doch jetzt schon 5 Leute gesagt.

 

[member42]

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?