backtracking anhand eines mag. Quads.

Intermediate

Monday, January 12th 2009, 9:35pm

backtracking anhand eines mag. Quads.

Hallo beisammen,

ich habe es mir zur Aufgabe machen lassen, ein magisches Quadrat mit der Länge n = 4 zu füllen.
Ich bin zuerst den Weg mit der Brechstange gegangen und habe versucht alles per Zufallszahlen zu füllen. Wie erwartet dauert es seeeehr lange, bis da was Brauchbares bei raus kommt.

im Prinzip steht als mein Gerüst aus befülle() und isMagic(), aber wie gesagt, will ich die befüllen()- Methode austauschen. Bei meinen Recherchen bin ich auf 2 Ansätze gestoßen.
1) bix X : das ist mit System. Von wegen "gehe zu Pos. X, schreib da die n/2 rein, geh ein Feld höher.." so in die Richtung und
2) Backtracking

da ich 1) irgendwie langweilig finde, wollte ich das Ganze mittels Backtracking lösen, aber irgendwie finde ich da nicht mal nen Ansatz (programmiertechnisch).
Diesen theoretischen Teil habe ich mir ausgedacht :

Java Quellcode

Do{
	do{
		-falls Wert in aktueller Zeile < 16 ist; Wert inkrementieren und auf gültiges ZEILE/SPALTE prüfen ( x > 0)
		-falls Wert in aktueller Zeile == 16;
			Rückschritt erforderlich
	}while (!Zeile  && kein Rückschritt erforderlich)
 
	if (Zeile gültig)
		 -nächste Zeile
	}
	else{
	-zurück und ggf. Zellen auf Null setzen (nur bei wert > 0)
	-prüfen, ob es noch eine Lösung geben kann (d.h. ob aktuelle Zelle >= 0 ist)
	}
}while (noch nicht alle Zellen besetzt)

Klar, so wie ich das aufgeschrieben habe, habe ich es auch versucht umzusetzen, aber irgendwo klemmts noch.

Kann mich vielleicht jemand an die Hand nehmen?

Danke

ali g

Intermediate

Posts: 143

Tuesday, January 13th 2009, 11:07pm

Okaaaay, hier ist mal eine kleine Methode. allerdings braucht sie >30min um zu einem Ergebnis zu kommen, was natürlich sehr unvorteilhaft ist.
habt ihr ein paar tipps?

Java Quellcode

public void versuche(int n, int[][] quadrat, int ziffer){
                if ((ziffer > (n*n)) && isMagisch(quadrat)){
                        zeige(quadrat);
                        System.exit(0);
                } else {
                        for (int x = 0;x<n; x++){
                                for (int y = 0; y <n; y++){
                                        if (quadrat[x][y] == 0) {
                                                quadrat[x][y] = ziffer;
 
                                                        versuche(n, quadrat, ziffer++);
 
                                                quadrat[x][y] = 0;
                                        }
                                }
                        }
                }
        }

cya

This post has been edited 1 times, last edit by "ali g" (Jan 18th 2009, 9:37pm)

Torben Brodt

Administrator

Posts: 8,454

Wednesday, January 14th 2009, 8:55pm

Hi,
ach bin ich froh, dass wir die einfachste Variante mit ungeradem n verwendet haben: magisches Quadrat der Ordnung n ?
Was hältst du davon eine Backtracking JavaScript Lösung auf Java zu übertragen? http://www.hbmeyer.de/backtrack/mag4de.htm

Bei deinem Algorithmus fehlt definitiv eine Abbruchbedingung.
Ich würde mal als Startpunkt den Sudoku Generator benutzen: Backtracking
Wenn ich das in der Schnelle überblicke musst du nur die legal() Methode auf deine Bedingungen anpassen.

Latest blogs: Neuer EX4 Server, Java EE Summit im Juni in München, Kostenlos zur Cebit + Windows 8 Entwickler Schulung

ali g

Intermediate

Posts: 143

Wednesday, January 14th 2009, 9:23pm

jeaha,

eine Antwort

so eine Methode habe ich mir heute gebastelt. bringt leider nicht soo viel.

Das mit JS werd ich mir mal angucken, danke!

This post has been edited 1 times, last edit by "ali g" (Jan 14th 2009, 9:48pm)

ali g

Intermediate

Posts: 143

Friday, January 16th 2009, 7:37pm

Kann keiner helfen?

Torben Brodt

Administrator

Posts: 8,454

Saturday, January 17th 2009, 10:36am

Was hat dir denn an meiner Hilfe nicht gefallen?

Latest blogs: Neuer EX4 Server, Java EE Summit im Juni in München, Kostenlos zur Cebit + Windows 8 Entwickler Schulung

ali g

Intermediate

Posts: 143

Sunday, January 18th 2009, 9:33pm

Hallo,

sorry, hätte ich vielleicht auch erwähnen können

-also der C-Code bringt mir nischt, da a) ungerade und b) nach Schema gearbeitet wird.
-ebenso bei der JS Version, soweit ich das durchschaue.

So eine isLegal Funktion habe ich mir gebaut, Problemos ist aber, dass ich nicht wirklich weiß, wie ich diese verwenden soll.
vor der Zuweisung? ->

	Java Quellcode
1	if(!isLegal) {ziffer++}

?

Danke

Torben Brodt

Administrator

Posts: 8,454

Sunday, January 18th 2009, 11:12pm

korrekt.
Du machst erst die Zuweisung und rufst dann die rekursive Funktion aus. Diese nimmt die Zuweisung als gegeben an und versucht eine Lösung zu finden.
99% der Prozesse laufen in eine Sackgasse und einer returned auf einmal eine richtige Lösung ;)

Bezogen auf den Sudoku Code würde ich die check Methode belassen und nur die legal Methode umschreiben.

Latest blogs: Neuer EX4 Server, Java EE Summit im Juni in München, Kostenlos zur Cebit + Windows 8 Entwickler Schulung

ali g

Intermediate

Posts: 143

Sunday, January 18th 2009, 11:19pm

So in etwa?

Java Quellcode

public void versuche(int n, int[][] quadrat, int ziffer){
                if ((ziffer > (n*n)) && isMagisch(quadrat)){
                        zeige(quadrat);
                        System.exit(0);
                } else {
                        for (int x = 0;x<n; x++){
                                for (int y = 0; y <n; y++){
                                        if (quadrat[x][y] == 0) {
                                         if(!isLegal(quadrat, ziffer)) {
                                             versuche(n, quadrat, ziffer++);
                                           }
                                           else{
                                               quadrat[x][y] = ziffer;
                                             versuche(n, quadrat, ziffer);
                                              quadrat[x][y] = 0;
                                         }
                                        }
                                }
                        }
                }
        }

so sieht mein check aus:

Java Quellcode

static boolean isLegal( int[][] quadrat, int ziffer ){
    boolean erg = false;   
    int n = 4;     
    for (int k = 0; k < n; k++ ) {
        for (int j = 0; j < n; j++) {
            if( Math.abs(quadrat[k][j]) == Math.abs(ziffer)) {
                erg = true;
            }
        }
    }System.out.println(erg);
    return erg;
 
  }

Dauert jetzt aber 1000 mal so lange, weil er ja bei jeder Zahl erstmal 16 Vergleiche anstellen muss. nicht unbedingt sehr praktikabel ;/

This post has been edited 7 times, last edit by "ali g" (Jan 19th 2009, 1:19am)

ali g

Intermediate

Posts: 143

Monday, January 19th 2009, 11:26am

an könnte doch versuchen, die benutzen Zahlen in ein Array zu stecken und im Prinzip einfach nur gucken, ob array[x-1] == x ist.
Problem hierbei ist, dass ich nicht genau weiß, wann ich eine Zahl tatsächlich (bzw fix) ins Array packe und wann sie wieder zurück auf 0 gesetzt wird.