backtracking anhand eines mag. Quads.

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • 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 :

    Quellcode

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


    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

  • 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?


    Quellcode

    1. public void versuche(int n, int[][] quadrat, int ziffer){
    2. if ((ziffer > (n*n)) && isMagisch(quadrat)){
    3. zeige(quadrat);
    4. System.exit(0);
    5. } else {
    6. for (int x = 0;x<n; x++){
    7. for (int y = 0; y <n; y++){
    8. if (quadrat[x][y] == 0) {
    9. quadrat[x][y] = ziffer;
    11. versuche(n, quadrat, ziffer++);
    13. quadrat[x][y] = 0;
    14. }
    15. }
    16. }
    17. }
    18. }
    Alles anzeigen



    cya

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von ali g ()

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

  • Hallo,

    sorry, hätte ich vielleicht auch erwähnen können :S
    -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? ->

    Quellcode

    1. if(!isLegal) {ziffer++}


    ?

    Danke

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

  • So in etwa?


    Quellcode

    1. public void versuche(int n, int[][] quadrat, int ziffer){
    2. if ((ziffer > (n*n)) && isMagisch(quadrat)){
    3. zeige(quadrat);
    4. System.exit(0);
    5. } else {
    6. for (int x = 0;x<n; x++){
    7. for (int y = 0; y <n; y++){
    8. if (quadrat[x][y] == 0) {
    9. if(!isLegal(quadrat, ziffer)) {
    10. versuche(n, quadrat, ziffer++);
    11. }
    12. else{
    13. quadrat[x][y] = ziffer;
    14. versuche(n, quadrat, ziffer);
    15. quadrat[x][y] = 0;
    16. }
    17. }
    18. }
    19. }
    20. }
    21. }
    Alles anzeigen



    so sieht mein check aus:

    Quellcode

    1. static boolean isLegal( int[][] quadrat, int ziffer ){
    2. boolean erg = false;
    3. int n = 4;
    4. for (int k = 0; k < n; k++ ) {
    5. for (int j = 0; j < n; j++) {
    6. if( Math.abs(quadrat[k][j]) == Math.abs(ziffer)) {
    7. erg = true;
    8. }
    9. }
    10. }System.out.println(erg);
    11. return erg;
    13. }
    Alles anzeigen




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

    Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von ali g ()