Magisches Quadrat

[Hilti]

Guten Abend euch allen,
Ich bin durch Google auf dieses Forum hier gestoßen weil ich folgendes Problem habe:
Ich wollte einen Algorithmus implementieren der mir mit Backtracking ein magisches Quadrat schreibt.
Doch komme ich einfach nicht weiter. Mir wird bei

[JAVA=57]int zeile = zelle / quadrat.length;[/code]

immer NullPointerException ausgegeben.
Hier mal meine komplette Klasse:

public class Quadrat {
    	    public static int [] []  quadrat; //= null;
            private static boolean [] zahlIstVerwendet;
            private static int summe;
            private int zeile;
            private int spalte;

            public  Quadrat(/*int [] [] quadrat*/) {
                    //this.quadrat = quadrat;
                    quadrat = new int [2][2];
                    //int [][] quadrat = new int[2][2];
                    zahlIstVerwendet = new boolean[quadrat.length * quadrat.length + 1];
                    summe = (quadrat.length * quadrat.length * quadrat.length +  quadrat.length) / 2;
            }
            private static int getZeilenSumme(int zeile) {
                    int summe = 0;
                    for (int wert : quadrat[zeile]) {
                            summe += wert;
                    }
                    
                    return summe;
            }
            private static int getSpaltenSumme(int spalte) {
                    int summe = 0;
                    for (int zeile = 0; zeile < quadrat.length; zeile++) {
                            summe += quadrat[zeile][spalte];
                    }
                    
                    return summe;
            }
             public static boolean isMagischesQuadrat() {
                    int summe = getZeilenSumme(0);
                    for (int i = 0; i < quadrat.length; i++) {
                           if (summe != getZeilenSumme(i) || summe != getSpaltenSumme(i)) {
                                    return false;
                            } 
                    }
                    for (int i = 0; i < zahlIstVerwendet.length; i++) {
                            zahlIstVerwendet[i] = false;
                    }
                    for (int zeile = 0; zeile < quadrat.length; zeile++) {
                            for (int spalte = 0; spalte < quadrat.length; spalte++) {
                                    if ( zahlIstVerwendet[quadrat[zeile][spalte]] ) {
                                            return false;
                                    } else {
                                            zahlIstVerwendet[quadrat[zeile][spalte]] = true;
                                    }
                            }
                    }
                    for (int i = 0; i < zahlIstVerwendet.length; i++) {
                            zahlIstVerwendet[i] = false;
                    }
                    
                    return true;
            }
             public static boolean erzeugeMagischesQuadrat(int zelle) {
                    int zeile =  zelle / quadrat.length;
                    int spalte=  zelle % quadrat.length;
                    for (int wert = 1; zelle < quadrat.length * quadrat.length 
                                       && wert <= quadrat.length * quadrat.length ; wert++) {
                            quadrat[zeile][spalte] = wert;
                            if (! zahlIstVerwendet[wert] && spalte < quadrat.length - 1 ||                          getZeilenSumme(zeile) == summe 
                                    && (zeile < quadrat.length - 1 || getSpaltenSumme(spalte) == summe)) {
                            zahlIstVerwendet[wert] = true; 
                                    if (zelle < quadrat.length * quadrat.length - 1 || ! isMagischesQuadrat())  {
                                            if ( erzeugeMagischesQuadrat(zelle + 1)) {
                                                    return true;
                                            } else {
                                                    zahlIstVerwendet[wert] = false;
                                            }
                                    } else {
                                            return true;
                                    }
                            }
                    }
                   return false;
            }
              public static void print() {
                    for (int zeile = 0; zeile < quadrat.length; zeile++) {
                            for (int spalte = 0; spalte < quadrat.length; spalte++) {
                                    System.out.print(quadrat[zeile][spalte] + "\t");
                            }
                            System.out.println();
                    }
            }
    }

Ich hoffe ihr könnt mir helfen
Mfg

 

[eRaaaa]

All deine Methoden sind static, demnach gehe ich auch davon aus, dass du die Methoden auch so aufrufst? Also du erstellst kein Objekt von Quadrat? Demnach wird auch NIE der Konstruktor aufgerufen und somit auch nie quadrat initialisiert. quadrat ist also null!

 

[Hilti]

Erstmal Danke für die schnell Hilfe.
Ich brauche halt eine GUI wo ich die Knöpfe "Magisches Quadrat" "Ausgeben" etc habe.
Dann kann ich die Betreffenden Methoden nur aufrufen wenn diese static sind.
Würde es also helfen wenn ich die Methoden einfach in die Klasse "GUI" schreibe wo ich sie dann aufrufe?
Mfg

 

[eRaaaa]

Irgendwas static zu machen, nur damit man von überall darauf zugreifen kann, ist eig. der falsche Weg.
Du kannst auch einfach ein Objekt von Quadrat erstellen und dann eben mit gettern und settern arbeiten und den static Krams weglassen.

Oder du bleibst beim static-Ansatz (musst du wissen - musst dir dann abedr im Klaren sein, dass es auch nur ein quadrat geben kann usw.), dann musst du aber wie ich schon sagte, eben dafür sorgen dass quadrat eben auch initialisiert wird. Entweder direkt bei der Deklarierung, im static Block oder sonst wie

 

[Hilti]

Das es nur ein Quadrat gibt ist nicht das Problem. Im Endeffekt soll es erstmal darauf hinauslaufen, dass mir in der Konsole das magische Quadrat ausgegeben wird wenn ich auf einen Knopf drücke. Danach will ich noch dass man über zwei Zahlenfelder irgendwo im 2D-Array eine 1 setzen kann und von da aus der Algorithmus läuft, bzw er die 1 berücksichtigt. Aber wenn ich jetzt erstmal das Quadrat in der Konsole ausgegeben bekomme wäre ich schon einen riesen Schritt weiter =)
Nur versteh ich jetzt nicht wie oder besser wo ich das Quadrat jetzt initalisieren soll.
Ich glaube ich steh gerade einfach aufm Schlauch :/
Mfg

Edit: Ok, Problem ist gelöst, jetzt nurnoch n bischen rumstümpern bei der Einsetzübung mit der 1 =)
ich bedanke mich ganz herzlich bei dir eRaaaa für deine Hilfe!

Edit Edit:
Hab vergessen die Lösung zu posten, stand ja in den Forenregeln man soll es machen
Mir fehlte schlichtweg die konstruktion wie von eRaaa ja schon beschrieben, das war der ganze Zauber. Nun sieht die Deklaration/Konstruktion folgendermaßen aus:
[Java] public class Quadrat {
public static int [] [] quadrat = new int [3][3];
private static boolean [] zahlIstVerwendet = new boolean[quadrat.length * quadrat.length + 1];
private static int summe = (quadrat.length * quadrat.length * quadrat.length + quadrat.length) / 2; [/code]


Edit:
So, die Ausgabe steht nun, funktioniert auch alles. Jetzt steh ich vor einem weiteren Problem.
Es sieht halt so aus das ich irgendwo eine 1 setzen möchte. Koordinaten werden in zwei Zahlenfelder eingegeben, diese werden dann in einer SET-Methode ins quadrat gesetzt und ZahlIstVerwendet und Einsgesetzt werden auf True gestellt. Doch gibt es einfach Probleme mit dem Backtracking, die Zahl wird zwar gesetzt (was ich sehe wenn ich auf den Knopf drücke und dann Ausgeben, das gleiche Quadrat mit der Zahl an der gewünschten Stelle) doch wenn ich mit der Methode versuche das Quadrat zu erzeugen kommt nur sche... bei raus.

Ich hatte mir folgendes gedacht

if(Einsgesetzt = true){
        		for (int wert = 1; zelle < quadrat.length * quadrat.length 
        		&& wert <= quadrat.length * quadrat.length ; wert++) {
        			if(Einsgesetzt = true){
        			        wert = 2;
        				Einsgesetzt = false;
        				quadrat[zeile][spalte] = wert;
        			else{
        			quadrat[zeile][spalte] = wert;}
        			if (! zahlIstVerwendet[wert] && spalte < quadrat.length - 1 || getZeilenSumme(zeile) == summe 
        				&& (zeile < quadrat.length - 1 || getSpaltenSumme(spalte) == summe)) {
        					zahlIstVerwendet[wert] = true; 
        				if (zelle < quadrat.length * quadrat.length - 1 || ! isMagischesQuadrat())  {
        					if ( erzeugeMagischesQuadrat(zelle + 1)) {
        						return true;
        					} else {
        						zahlIstVerwendet[wert] = false;
        					}
        				} else {
        					return true;
        				}
        			}
        		}
        		return false;
        		}
        	
    		else{

nach else das normale Backtracking ohne die boolschen Abfragen falls keine 1 gesetzt wurde.
Gäb es evtl andere Kniffe das zu lösen?
Mfg

 

[Tharsonius]

Es gibt da eine Lösungsstrategie für Quadrate mit ungerader Kantenlänge:

Man beginnt am linken Rand im mittleren Feld. Dort schreibt man die 1.
Nun werden der Reihe nach alle Zahlen eingetragen, also 2,3,4...
Die Folgezahl kommt immer in das Feld, dass sich rechts oberhalb befindet.
Ist das Feld besetzt, weil dort bereits eine Zahl steht, so wird statt dessen in das Feld direkt unter der Vorgängerzahl eingetragen anstatt rechts oberhalb davon.

Für diese Regelung wird das Quadrat als an den Seiten verbunden betrachtet. Das heisst beispielsweise in einem 5x5 Quadrat ist das Folgefeld von Spalte 5 zeile 1 dann spalte 1, zeile 5.


Für gerade Kantenlänge funktioniert das nicht, kann sein, dass es geht, wenn man einen anderen Startpunkt wählt oder es generell nicht geht, das weiss ich nicht mehr... ist etwas länger her, dass ich das in der Schule in Mathe damals hatte...


Edit:
Ein 5x5 Quadrat sieht dann so aus:

19 21 3 10 12
25 2 9 11 18
1 8 15 17 24
7 14 16 23 5
13 20 22 4 6

 

[Marco13]

Oder als Code

return i>ì*ì?i-1:(ï[í][î]=f(ì,i+1,(í+(i%ì==0?0:1))%ì,(î+(i%ì==0?-1:1))%ì,ï))-1;

(Siehe http://www.java-forum.org/java-basics-anfaenger-themen/28040-magic-square.html#post316068 )