Backtracking - Labyrinth

[Tensei]

hallo alle zusammen!
wie der titel schon sagt soll ich durch ein rekursives programm einen weg durch ein labyrinth, in form eines 2d arrays, finden. landet das programm in einer sackgasse soll "der pc" an den ort zurückspringen, wo er einen alternativen weg nehmen kann. mein problem ist: er springt nicht zurück. er landet in eine sackgasse und will einfach nicht zurückt >.<
müsste es nicht automatisch, da es rekursiv ist, alle durchgegangenen felder zurückspringen? weil es ja wieder aufgeschachtelt wird ...
irgendwer von euch einen lösungsansatz für das problem?

 

[Firephoenix]

Ich denke der Fehler liegt irgendwo zwischen Zeile 10 und 12 in deinem Code - ist allerdings nur eine Vermutung, da du ihn nicht mit gepostet hast und man daher nur schwer sagen kann warum es nicht funktioniert

 

[Gast2]

Also "automatisch" passiert beim Programmieren relativ wenig.
Ohne Code kann man da nichts zu sagen.

 

[Tensei]

    public static void main(String[] args) {
      int[][] lab = {{1,0,1,0,1,1,1,1,1,1},{1,0,1,0,1,0,0,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,0,0,0,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,1,0,1},
        {1,1,1,1,1,1,0,1,0,1}, {1,0,0,1,1,1,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,1,0,0,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,0,0,1,1,1,1,1,1,1},{1,0,0,1,0,1,1,1,1,1},
        {1,0,0,1,0,0,0,0,0,1},{1,0,0,1,0,0,1,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,1,0,1,0,1},{1,0,0,1,0,1,0,1,0,1},{1,0,0,1,1,1,0,1,0,1},{1,0,0,0,0,0,0,1,0,1},
        {1,1,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,0,1,1,0,1,1,1,1,1},{1,0,1,0,0,1,0,0,0,1},{1,0,1,0,1,1,0,1,0,1},{1,1,1,0,0,0,0,1,0,1},{1,0,0,0,1,1,1,1,0,1},
        {1,0,1,0,0,0,0,1,0,1},{1,1,1,1,1,1,0,1,1,1}};
      
      int i = 0;
      int j = 1;
      
      boolean end = navigate(lab , i, j);
      
      if(end){
          System.out.println("Es wurde ein Ausweg gefunden!");
      }
      else{
          System.out.println("Es wurde kein Ausweg gefunden!");
      }
      
      for(int k = 0; k < lab.length; k++){
          for(int l = 0; l < lab[k].length; l++){
              System.out.print(lab[k][l] + "  ");
          }
          System.out.println();
      }
    }
    public static boolean navigate(int [][] lab, int i, int j){
        boolean way = true;
        
        int right = j+1;
        int left  = j-1;     
        int down = i+1;
        int up = i-1;
        
        if(i == lab.length-1 || j == lab[0].length-1){
            return way;
        }
   
        else{
        if (lab[i][right]==0){
            lab[i][right]=2;
            return navigate(lab, i, right);
        }
        if (lab[down][j]==0){
            lab[down][j]=2;
            return navigate(lab, down, j);
        }
        if (lab[i][left]==0){
            lab[i][left]=2;
            return navigate(lab, i, left);
        }
        if (lab[up][j]==0){
            lab[up][j]=2;
            return navigate(lab, up, j);
        }
        }
        
        return false;
    }

hier der code

ach und wir, also ich in meiner schule, haben noch keine so komplizierten sachen gelernt (klassen, etc.). wir benutzen derzeit nur die "standardwerkzeuge" (schleifen, if-else,... das wars eigentlich auch schon xD)

 

[chalkbag]

Hallo,

was mir fehlt ist das wenn du einen Schritt wieder zurück gehst, dass du die Wegmarkierung (2) auch wieder entfernt. Ich gebe zu aber deinen Code jetzt nicht komplett durchdacht zu haben.

Backtracking-Probleme werden schnell sehr sehr aufwändig.

Versuche mal ein ganz kleines Spielfeld

111
000
111

Das kannst du dann auch debuggen und sehen wo er nicht agiert wie er sollte.

 

[Tensei]

so. danke an alle die eventuell versucht haben mir bei dem problem zu lösen. in der schule hat mir ein guter freund von mir (echtes genie in der schule) mir erklärt wie es richtig geht.

    public static void main(String[] args) {
      int[][] lab = {{1,0,1,0,1,1,1,1,1,1},{1,0,1,0,1,0,0,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,0,0,0,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,1,0,1},
        {1,1,1,1,1,1,0,1,0,1}, {1,0,0,1,1,1,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,1,0,0,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,0,0,1,1,1,1,1,1,1},{1,0,0,1,0,1,1,1,1,1},
        {1,0,0,1,0,0,0,0,0,1},{1,0,0,1,0,0,1,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,1,0,1,0,1},{1,0,0,1,0,1,0,1,0,1},{1,0,0,1,1,1,0,1,0,1},{1,0,0,0,0,0,0,1,0,1},
        {1,1,1,1,1,1,1,1,0,1},{1,0,0,0,0,0,0,0,0,1},{1,0,1,1,0,1,1,1,1,1},{1,0,1,0,0,1,0,0,0,1},{1,0,1,0,1,1,0,1,0,1},{1,1,1,0,0,0,0,1,0,1},{1,0,0,0,1,1,1,1,0,1},
        {1,0,1,0,0,0,0,1,0,1},{1,1,1,1,1,1,0,1,1,1}};
      
      int i = 0;
      int j = 1;
      
      boolean end = navigate(lab , i, j);
      
      if(end){
          System.out.println("Es wurde ein Ausweg gefunden!");
      }
      else{
          System.out.println("Es wurde kein Ausweg gefunden!");
      }
      
      for(int k = 0; k < lab.length; k++){
          for(int l = 0; l < lab[k].length; l++){
              System.out.print(lab[k][l] + "  ");
          }
          System.out.println();
      }
    }
    public static boolean navigate(int [][] lab, int i, int j){
        boolean way = true;
        
        int right = j+1;
        int left  = j-1;     
        int down = i+1;
        int up = i-1;
        
        if(i == lab.length-1 || j == lab[0].length-1){
            return way;
        }
   
        else{
        if (lab[i][right]==0){
            lab[i][right]=2;
            if(navigate(lab,i,right)) return true;
        }
        if (lab[down][j]==0){
            lab[down][j]=2;
            if(navigate(lab,down,j)) return true;
        }
        if (lab[i][left]==0){
            lab[i][left]=2;
            if(navigate(lab,i,left)) return true;
        }
        if (lab[up][j]==0){
            lab[up][j]=2;
            if(navigate(lab,up,j)) return true;
        }
        }
        
        return false;
    }

ich muss statt einfach nur die methode erneut aufzurufen (siehe java-code von vorher), abfragen (und nicht einfach nur die methode erneut aufrufen^^) ob es auch weiterhin noch geht. so wird es RICHTIG rekursiv. das heißt, es wird, wenn das programm in eine sackgasse läuft, daran zurückgeschachtelt. bei einer rekursiven methode werden ja alle methodenaufrufe und veränderungen der variablem im stack gespeichert. und dann wenn es nicht weitergeht, geht er von oben (der letzte methodenaufruf) so lange in der liste zurück, bis er einen alternativen weg findet. und genau das wird durch die if-abfrage (zb.: if(navigate(lab,up,j)) return true gewährleistet. er hat bei seinem programm, dass er mit einer while-schleife gelöst hat, dass selbe problem gehabt.
echt cool wenn man einen art coach hat, der einem weiterhilft