Magisches Quadrat

Diskutiere Magisches Quadrat im Allgemeine Java-Themen Forum; 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...

  1. member42
    member42 Mitglied
    Hallo,
    ich wollte magische Quadrate durch Rekursion berechnen. Für die Seitenlänge 3 klappt es auch, als Ausgabe bekomme ich:
    Code (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:
    Code (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.
     
  2. Vielleicht hilft dir dieses Training hier weiter.
  3. Fabian321
    Fabian321 Neues Mitglied
    Multithreading könnte dein problem lösen ;)
     
  4. httpdigest
    httpdigest Aktives Mitglied
    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 gefällt das.
  5. member42
    member42 Mitglied
    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.
     
  6. httpdigest
    httpdigest Aktives Mitglied
  7. member42
    member42 Mitglied
    OK macht aber auch nicht so einen Unterschied, man kann nicht alle berechnen und deswegen ist die Aufgabenstellung etwas komisch.
     
  8. httpdigest
    httpdigest Aktives Mitglied
    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).
     
  9. member42
    member42 Mitglied
    Die Aufgabe steht im Kapitel über Backtracking, deswegen bin ich davon ausgegangen.
     
  10. httpdigest
    httpdigest Aktives Mitglied
    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.
     
    member42 gefällt das.
  11. DerWissende
    DerWissende Bekanntes Mitglied
    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....
     
  12. Wenn du Java lernen möchtest, empfehlen wir dir dieses Online-Training hier
Passende Stellenanzeigen aus deiner Region:





Die Seite wird geladen...

Magisches Quadrat - Ähnliche Themen

Magisches Quadrat Rechts Formatieren
Magisches Quadrat Rechts Formatieren im Forum Java Basics - Anfänger-Themen
Magisches Quadrat und Backtracking
Magisches Quadrat und Backtracking im Forum Java Basics - Anfänger-Themen
Magisches Quadrat
Magisches Quadrat im Forum Hausaufgaben
Laufzeitproblem: magisches Quadrat
Laufzeitproblem: magisches Quadrat im Forum Allgemeine Java-Themen
magisches Quadrat
magisches Quadrat im Forum Hausaufgaben
Thema: Magisches Quadrat