BackTracking

Status
Nicht offen für weitere Antworten.

manuche

Bekanntes Mitglied
Hi!
Ich versuche mich grade an einem Backtracking-Verfahren à la "Try and Error"...
Hab auch schon was auf die Beine gestellt nur hängts jetzt irgenwie nen bisschen!

Code:
  public void backtracking(){
    int[][] stackN = new int[81][2];
    String[][] stackS = new String[81][2];
    int schritt = 0;
    String versuchzahl = new String();
    boolean error = false;
    for (int a = 0; a <= 8; a++){
      for (int b = 0; b <= 8; b++){
        if (schritt < 81){
          if (schritt < 81){
            versuchzahl = vTab[a][b];
            
            //Block ermitteln
            int m = 0, n = 0;
            if (a >= 0 && a <= 2){
              m = 2;
            }else if (a >= 3 && a <= 5){
              m = 5;
            }else if (a >= 6 && a <= 8){
              m = 8;
            }
            if (b >= 0 && b <= 2){
              n = 2;
            }else if (b >= 3 && b <= 5){
              n = 5;
            }else if (b >= 6 && b <= 8){
              n = 8;
            }

            if (versuchzahl.length() > 1){
              tempzahl = versuchzahl.substring(0, 1);
              stackN[schritt][0] = a;
              stackN[schritt][1] = b;
              stackS[schritt][0] = versuchzahl;
              stackS[schritt][1] = tempzahl;
              aktzahl = tempzahl;
              vergleich = tempzahl;
              ausschlussZ(a);     //ausschlussZ, ausschlussS und ausschlussB funktionieren fehlerfrei
              ausschlussS(b);
              ausschlussB(m, n);
              schritt++;
            }else if (versuchzahl.length() == 0){
              error = true;
              schritt --;
              a = stackN[schritt][0];
              b = stackN[schritt][1];
              vTab[a][b] = stackS[schritt][0].replace(vergleich, "");
              error = false;
            }else {

              stackN[schritt][0] = a;
              stackN[schritt][1] = b;
              stackS[schritt][0] = versuchzahl;
              stackS[schritt][1] = tempzahl;

              aktzahl = versuchzahl;
              ausschlussZ(a);
              ausschlussS(b);
              ausschlussB(m, n);
              schritt++;
            }
          }
        }else{
          a = 8;
          b = 8;
        }
      }
    }
  }
Es kommt soweit kein vernünftiges Ergebnis....
 

Leroy42

Top Contributor
manuche hat gesagt.:
Es kommt soweit kein vernünftiges Ergebnis....

LOL

Und wir sollen jetzt hellsehen und herausfinden, was deine
stackN, stackS, ausschlussZ(a), ausschlussS(b), ausschlussB(m, n), ...
alle für eine Bedeutung haben und was du unter einem
vernünftigen Ergebnis verstehst? ???:L

Sorry, aber das ist, heute mittag, etwas zu heftig für mich. :(

Und was hat das ganze überhaupt mit Backtracking zu tun? :shock:
 

Leroy42

Top Contributor
Na gut, dann fang' ich mal an (die andern müssen jetzt aber auch mitraten):

Vermutung 1: Das ganze hat höchstwahrscheinlich etwas mit Sudoku zu tun.
Entweder ein Lösungs- oder ein Erstellungsprogramm.

So, jetzt seid ihr dran...
 
J

_Jürgen_

Gast
schau am besten unter FAQ'S, Scripts, etc. :###

und es wäre hilfreich wenn du es uns besser erklären könntest ....
 

manuche

Bekanntes Mitglied
Jap das ganze hat mit Sudoku zu tun...
Die eingebauten Methoden funktionieren einwandfrei!
Also Backtracking weil alle heisst doch der Algorythmus oder nich?
Auf jeden Fall versuche setzt das Programm die erste Zahl die in den Lösungsmöglichkeiten ist ein schliesst dann in Zeile, Spalte und Block diese Zahl aus den Möglichkeite aus (die besagten Methoden). Wenn irgendwann keine Lösungsmöglichkeit mehr vorhanden ist, geht es ein Schritt zurück und eine andere Möglichkeit probieren. In StackS und StackN sind die Koordinaten ect zu den vorherigen Aktionen.
Das ganze soll soweit geschehen, bis alle 81 Zahlen eindeutig glöst sind....

In den Methoden wird die aktzahl aus dem Lösungsstring gelöscht sofern sie vorhanden ist...
 

Leroy42

Top Contributor
manuche hat gesagt.:
Wenn irgendwann keine Lösungsmöglichkeit mehr vorhanden ist, geht es ein Schritt zurück und eine andere Möglichkeit probieren.

Und wo bitte geschieht das? :shock:

Dein Programmausschnitt hat überhaupt nichts mit Backtracking zu tun;
du rufst ja noch nicht mal irgendeine Methode rekursiv auf.

Das du zur (automatischen) Lösung eines Sudoku Backtracking
brauchst ist schon richtig, aber an deiner Stelle würde ich mich
überhaupt erst einmal in die Grundlagen des Backtrackings einarbeiten,
z.b. bei Backtracking erklärt

oder wikipedie einfach mal nach backtracking.
 
J

_Jürgen_

Gast
Ich seh da keine rekursiven Methoden daher würd ich nicht von backtracking sprechen...

und deine schleifen sind auch zu kompliziert für meinen geschmack...
 
J

_Jürgen_

Gast
oh sry meinte nich die schleifen sonder die if abfragen *gähn* :D
 

manuche

Bekanntes Mitglied
Na deswegen schreib ich ja auch den kompletten Quellcode damit ihr mir zeigen könnt wies besser geht! xD
Naja, ist halt so nen try and error Ding...

@Leroy: Er merkt sich ja mit der variable schritt wie weit er gegangen ist und legt sich zu jedem schritt daten in ein array an dem er nachvollziehen wo zuvor alles war...
 

manuche

Bekanntes Mitglied
Na deswegen schreib ich ja auch den kompletten Quellcode damit ihr mir zeigen könnt wies besser geht! xD
Naja, ist halt so nen try and error Ding...

@Leroy: Er merkt sich ja mit der variable schritt wie weit er gegangen ist und legt sich zu jedem schritt daten in ein array an dem er nachvollziehen wo zuvor alles war...

btw:
backtracking erklärt hat gesagt.:
Meistens funktioniert das so: man sucht die Lösung für ein Problem schrittweise. Wenn man in einer Sackgasse steckt, geht man wieder einen Schritt zurück, und versucht dort einen andere Möglichkeit. Das wiederholt man so lange, bis man entweder eine Lösung gefunden hat, oder alle Möglichkeiten durchprobiert hat.
soll jetzt aber nicht vom thema ablenken!
 

Leroy42

Top Contributor
manuche hat gesagt.:
Die eingebauten Methoden funktionieren einwandfrei!
Schön, aber was tun die überhaupt?-

manuche hat gesagt.:
schliesst dann in Zeile, Spalte und Block diese Zahl aus den Möglichkeite aus (die besagten Methoden).

Und wie werden die Möglichkeiten ausgeschlossen? Deine Methoden ausschluss... liefern keine
Rückgabewerte. Die einzige Möglichkeit, überhaupt etwas zu probieren, besteht
dann wenn deine ausschluss-Methoden direkt in deiner Instanzvariable vTab etwas verändern.

Außerdem versuchst du nur Backtracking durch deinen Stack zu simulieren.

Was steht in vTab[0][0] denn zu Anfang drin? ""? Wenn ja, würde
er durch das Dekrementieren von schritt gleich zu Beginn eine IndexOutOfBoundsException
werfen.

Ich denke, daß du dich auf diesem Wege vollständig verfranst und so
nie zum Ziel kommen wirst, und kann dir nur erneut nahelegen, dich zuerst
in die Basics des Backtracking anhand eines einfachen Beispiels, wie das 8-Damen-Problem
einzuarbeiten. Erst wenn du, einer der im Netz zu hauf zu findenden Programme,
vollständig verstanden hast, kannst du dich an etwas komplizierteres wie
deinen Sudoku-Solver herantrauen.
 

manuche

Bekanntes Mitglied
Also das ist ja hier nur ein Codeschnipsel... Im vorfeld passiert ja so einiges... die keine eindeutigen zahlen beinhalten werden mit dem String "123456789" gefüllt... die mehtoden AusschlussZ, S und B sorgen dafür, dass eine gefundene eindeutige zahl aus dem lösungsstring der anderen felder in zeile spalte und block gelöscht werden.
Was ich bei meinem Codeschnipsel allerdings nicht bedacht habe ist, dass die ausgeschlossenen zahle auch wieder irgendwo drangehängt werden müssen wenn sich der lösungsweg als falsch herausstellt...
 

Leroy42

Top Contributor
Ein richtiger Backtracking-Algorithmus wäre wesentlich kürzer und
eleganter und würde ungefähr so aussehen:

Code:
void solve() {solve(0);}

boolean solve(int field) {
  if (field==81) return true;
  int x = field % 9;
  int y = field / 9;
  for (int j=1; j <=9; ++j) {
    sudoku[y][x] = j;
    if (isOk(x, y) && solve(field+1))
      return true;
  }
  return false;
}

wobei isOk(int x, int y) prüft, ob die bei x,y eingefügte
Zahl das bisherige (<=x, <=y) Sudoku-Feld nicht verletzt.
 

Leroy42

Top Contributor
Ach so, ein Fehler:

Es dürfen ja nur dann Werte in ein Sudoku-Feld
eingesetzt werde, wenn nicht bereits ein Wert
vorgegeben ist. Also:
Code:
void solve() {solve(0);} 

boolean solve(int field) { 
  if (field==81) return true; 
  int x = field % 9; 
  int y = field / 9; 
  for (int j=1; j <=9; ++j) { 
    if (sudoku[y][x] == 0) {
      sudoku[y][x] = j; 
      if (isOk(x, y) && solve(field+1)) 
        return true; 
    }
  } 
  return false; 
}
 

Leroy42

Top Contributor
field durchläuft die Werte von 0 bis 80, und der Modulo-Operator,
sowie die Division, bestimmen daraus die Zeile und Spalte:

Beispiele:

Code:
field=8 ==> field/9 = 0, field%9 = 8, also Zeile 0, Spalte 8
field=9 ==> field/9 = 1, field%9 = 0, also Zeile 1, Spalte 0
:D
 

Leroy42

Top Contributor
Himmel! Noch ein Fehler!

(Das kommt davon, wenn man neben der Arbeit programmiert)

Die Leerfelder müssen natürlich wieder zurückgesetzt werden:
Code:
void solve() {solve(0);} 

boolean solve(int field) { 
  if (field==81) return true; 
  int x = field % 9; 
  int y = field / 9; 
  for (int j=1; j <=9; ++j) { 
    if (sudoku[y][x] == 0) { 
      sudoku[y][x] = j; 
      if (isOk(x, y) && solve(field+1)) 
        return true; 
      sudoku[y][x] = 0; 
    } 
  } 
  return false; 
}

Jetzt stimmts aber endlich! :cool:
 

Leroy42

Top Contributor
Jetzt aber wirklich die allerletzte Version:

Code:
void solve() {solve(0);} 

boolean solve(int field) { 
  if (field==81) return true; 
  int x = field % 9; 
  int y = field / 9; 
  if (sudoku[y][x] == 0) { 
    for (int j=1; j <=9; ++j) { 
      sudoku[y][x] = j; 
      if (isOk(x, y) && solve(field+1)) 
        return true; 
      sudoku[y][x] = 0; 
    } 
  } 
  return false; 
}
(Ich weiß, ich kann ein ganz schöner Pedant sein)
 

manuche

Bekanntes Mitglied
Ok ich werde das ganze jetzt mal Schritt für Schritt testen...
Das einzige was mit aufgefallen ist, in Zeile 10 rufst du solve mit (field +1) auf... Soweit nichts schlimmes! Jedoch nimmt die methode solve garkeine werte entgegen!
 

Murray

Top Contributor
manuche hat gesagt.:
Das einzige was mit aufgefallen ist, in Zeile 10 rufst du solve mit (field +1) auf... Soweit nichts schlimmes! Jedoch nimmt die methode solve garkeine werte entgegen!
Es gibt zwei solve-Methoden...
 

manuche

Bekanntes Mitglied
Alles klar... Mir war nicht bewusst, dass es zwei gleichnamige Methoden geben darf...

Alse... Fürs verständnis:
Code:
void solve() {solve(0);}   //ruft den Algo auf???

boolean solve(int field) {          //holt aktuelles feld
  if (field==81) return true;      //wenn bei feld 81 methode = true
  int x = field % 9;                   //erkennt feld nummer
  int y = field / 9;                    // "
  if (sudoku[y][x] == 0) {        //wenn feld leer
    for (int j=1; j <=9; ++j) {   //dann such die nächste einsetzbare zahl
      sudoku[y][x] = j;             //und setze sie ein
      if (isOk(x, y) && solve(field+1)) //wenn die zahl nicht in spalte, zeile oder block
        return true;                   //methode = true 
      sudoku[y][x] = 0;            //sonst setze zurück
    } 
  } 
  return false; 
}

Da kommen mir gleich noch drei verständnisfragen:
1. warum genau muss die methode vom typ boolean sein?
2. beendet "return" sofort eine methode?
3.
Leroy42 hat gesagt.:
Code:
field=8 ==> field/9 = 0, field%9 = 8, also Zeile 0, Spalte 8
field=9 ==> field/9 = 1, field%9 = 0, also Zeile 1, Spalte 0
müsste es dann nich später beim array aufruf sudoku[x][y] heissen statt sudoku[y][x]
 

Murray

Top Contributor
manuche hat gesagt.:
1. warum genau muss die methode vom typ boolean sein?
Weil sie in diesem rekursiven Aufruf
Code:
 if (isOk(x, y) && solve(field+1)) //wenn die zahl nicht in spalte, zeile oder block
so verwendet wird. Irgendwann muss es mit der Rekursion ja mal ein Ende haben ( -> Stichwort: Abbruchbedingung)

manuche hat gesagt.:
2. beendet "return" sofort eine methode?
Ja
(Es sei denn, es gibt in einer Methode noch einen finally-Zweig, dann wird der zuerst noch abgearbeitet)

manuche hat gesagt.:
3.
Leroy42 hat gesagt.:
Code:
field=8 ==> field/9 = 0, field%9 = 8, also Zeile 0, Spalte 8
field=9 ==> field/9 = 1, field%9 = 0, also Zeile 1, Spalte 0
müsste es dann nich später beim array aufruf sudoku[x][y] heissen statt sudoku[y][x]
Ist Geschmackssache, solange man das überall konsistent durchhält. sudoku[y][x] ist aber irgendwie naheliegender, wenn man so ein Spielfeld als Array von Zeilen ansieht, bei dem jede Zeile wieder ein Array von Feldern darstellt. sudoku[y] verweist dann auf eine Zeile in diesem Feld. Wenn du das Speilfeld aber als Array von Spalten ansiehst, dann wäre sudoku[x][y] richtig; sodoku[x] wäre dann eine Spalte. Aufgrund der Symmetrie des Spielfelds ist das aber eigentlich egal.
 

manuche

Bekanntes Mitglied
Ich hab da noch ein Problem...:
Also das ist der Ablauf des Programms in Methoden:
Code:
  public void buttonsolveActionPerformed(ActionEvent evt) {
    //Sudoku lösen...
    fuellen();            //interessiert hier nicht
    eingabetest();     //interessiert ebenfalls nicht
    lösen();               //Lösungsverfahren durch Ausschluss
    if (ai.getState()){ //Checkbox ob Backtracking benutzt werden soll (nach Ausschlussverfahren)
      backtracking();  //ruft die rekursive Methode auf
    }
    ergaenzen();       //markiert die Felder, die nicht gelöst wurden rot
  }

Ist ja so recht simpel aufgebaut und hat bis vor kurzem auch funktioniert. Wenn jetzt bei einem leeren Sudoku das Backtracking durchläuft werden allerdings die Felder rot markiert bevor der Algo überhaupt durchgelaufen ist... Für mich sieht das ganz deutlich so aus, als würde er erst den Algo abarbeiten und anschlißend die Felder markieren oder halt nicht... Was könnte da schief laufen?

Hat sich erledigt!!!!
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Max246Sch 3D Box Filler BAcktracking Java Basics - Anfänger-Themen 1
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 2
districon Backtracking Java Basics - Anfänger-Themen 14
districon Dynamisch Programmierung/Backtracking/Memoization Java Basics - Anfänger-Themen 3
districon Backtracking funktioniert nicht ganz Java Basics - Anfänger-Themen 3
V Backtracking und Rekursion Java Basics - Anfänger-Themen 15
G Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
O Backtracking Java Basics - Anfänger-Themen 5
C Rekursives Backtracking beim Spiel Peg Java Basics - Anfänger-Themen 22
A Backtracking Java Basics - Anfänger-Themen 56
R Backtracking Java Basics - Anfänger-Themen 1
V Feld sortieren mit Backtracking Java Basics - Anfänger-Themen 1
A Sudoku mit Backtracking lösen Java Basics - Anfänger-Themen 3
L Sudoku Backtracking Pseudocode Java Basics - Anfänger-Themen 3
N Backtracking - Labyrinth/Irrgarten Java Basics - Anfänger-Themen 14
I Backtracking Schach Java Basics - Anfänger-Themen 5
L Magisches Quadrat und Backtracking Java Basics - Anfänger-Themen 19
M Backtracking/Solve Methode Java Basics - Anfänger-Themen 7
P Labyrinth, Backtracking, verzögerte Anzeige Java Basics - Anfänger-Themen 15
D Sudoku lösen mit Backtracking Java Basics - Anfänger-Themen 20
E backtracking und Induktionsprinzip Java Basics - Anfänger-Themen 2
D Backtracking Waage Problem Java Basics - Anfänger-Themen 23
N Backtracking Solohalma Java Basics - Anfänger-Themen 2
W Backtracking und Frustration Java Basics - Anfänger-Themen 6
X Sudoku Backtracking Java Basics - Anfänger-Themen 6
J Solitaire via Backtracking Java Basics - Anfänger-Themen 7
A Backtracking - kennt Java keine Rücksprungmarken? Java Basics - Anfänger-Themen 15
G Backtracking mit globaler Variable Java Basics - Anfänger-Themen 5
J Backtracking Algorithmus Java Basics - Anfänger-Themen 16

Ähnliche Java Themen

Neue Themen


Oben