Рекурсивный решатель задач лабиринта Java

Теперь я заставил его перестать повторяться бесконечно, но он просто продолжает пробовать один и тот же неверный путь снова и снова. Кто-нибудь знает способ заставить его попробовать разные пути?

Ключ к цифрам: 0 открыт 1 стена 2 часть пути 3 конец лабиринта

    public class Maze{
  public static void main(String[] args){
    int[][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
      {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1},
      {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
      {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1},
      {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
      {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1},
      {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
      {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1},
      {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},
      {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1},
      {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1},
      {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1},
      {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1},
      {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1},
      {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1},
      {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1},
      {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1},
      {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}};
    boolean[][] posCheck = new boolean[maze.length][maze[0].length];
    int r = 0;
    int c = 0;
    for(int row = 0; row < maze.length; row++){
      for(int col = 0; col < maze[row].length; col++){
        if(maze[row][col]==0){
          r = row;
          c = col;
        }
      }
    }
    maze[r][c] = 3;
    mazeSolver(1, 0, maze, posCheck);
  }

  public static boolean mazeSolver(int r, int c, int[][]maze, boolean[][] posCheck){
    posCheck[r][c] = true;
    maze[r][c] = 2;

    if(maze[r][c] == 3){
      print(maze);
      return true;
    }

    if((c+1 < maze.length) && maze[r][c+1]==0 && !posCheck[r][c+1] && (mazeSolver(r, c + 1, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && (mazeSolver(r - 1, c, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && (mazeSolver(r, c - 1, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && (mazeSolver(r + 1, c, maze, posCheck))){
      maze[r][c] = 2;
      return true;
    }

    print(maze);
    return false;
  }

  public static void print(int[][] maze){
    for(int row = 0; row<maze.length; row++){
      for(int col = 0; col<maze[row].length; col++)
        System.out.print(maze[row][col]);
      System.out.println();
    }
  }
}

java recursion solver maze
person user3390133    schedule 06.03.2014    source источник
comment
когда вы проходите через узел, отметьте его как специальное значение «5», чтобы вы знали, посещался ли он, при повторении вы узнаете, были ли вы там раньше. Обязательно помечайте всегда0 узлы, которые не нуждаются в другом обходе, скажем, «листья».   -  person Bogdan M.    schedule 07.03.2014
comment
Требуется ли для этого рекурсия?   -  person Solace    schedule 07.03.2014
comment
Если лабиринт позволяет вам перейти в место, которое вы уже прошли на своем пути, не возвращаясь после обнаружения тупика, вы должны иметь возможность обнаружить это в своем коде.   -  person Thorbjørn Ravn Andersen    schedule 07.03.2014
comment
Первая проблема, которую я заметил: вы устанавливаете maze[r][c] = 2;, затем тестируете if(maze[r][c] == 3).....   -  person CiaPan    schedule 30.03.2014
comment
Еще один: можно ли протестировать (c+1 < maze.length)? Переменная c, похоже, применяется к строкам лабиринта, а не к самому лабиринту.   -  person CiaPan    schedule 30.03.2014
comment
Откуда вы знаете, что ваша программа «снова и снова пробует один и тот же неправильный путь»? Я боюсь, что вы ошибаетесь в этом, и вы просто не ждали достаточно долго и не читали выгруженные изображения достаточно внимательно, чтобы быть уверенным... Ваш лабиринт составляет примерно 1700 ячеек, «неправильный путь» может быть, скажем, в сотню шагов long, и вы заставили свою программу печатать весь лабиринт с каждым return false из рекурсии.   -  person CiaPan    schedule 30.03.2014
comment
stackoverflow.com/questions/13294848/   -  person Anonymous    schedule 25.11.2014

Ответы (2)


arrow_upward
0
arrow_downward

Допустим, у вас есть: НАЧАЛЬНОЕ СОСТОЯНИЕ

SW00WW
00W0WW
W000WW
W0WWWW
00000E

w - стена 0 - непройденный путь S - начальная точка E - конечная точка (X - пройденная точка)

Объяснение:

Что мы делаем? Мы повторяем 0 и помечаем их X, когда достигаем листа. Если у вас есть из одной точки другой 0, вы не отмечаете его как X, только если вы уверены, что вам не нужно возвращаться снова.

www00W     (see 'P' as an '0') we must go from 'S' to 'E' when we reach 'P' we have 2 moves from that point 
S00Pww      when iterating. As conclusion you let it be stil '0', and when we meet a first node 
www00E      that wont need another visit mark it as X.

Пример:

SW00WW
x0W0WW
W000WW
W0WWWW
00000E

SW00WW
xxW0WW
W000WW
W0WWWW
00000E

SW00WW
xxW0WW
W000WW
W0WWWW
00000E

SW00WW
x0W0WW
W000WW
W0WWWW
00000E

SW00WW
xxW0WW
W0x0WW
W0WWWW
00000E

SW00WW
xxW0WW
W0xxWW
W0WWWW
00000E

SWxxWW   (made 3 steps on a first ipotetical choise)
xxWxWW
W0xxWW
W0WWWW
00000E

    SWxxWW   (made 4 steps on last row to the end)
    xxWxWW
    WxxxWW
    WxWWWW
    0xxxxE

Надеюсь, это поможет, извините за длинный пример, но я попытался прояснить ситуацию.

PS: альтернативный поиск в глубину

person Bogdan M.    schedule 06.03.2014

arrow_upward
0
arrow_downward

Рекурсивная функция будет гораздо более «читабельной», если вы поместите все проверки правильности позиции в одном месте:

public static boolean mazeSolver(int r, int c, int[][]maze){
  if( ! isPositionValid(r, c, maze))
    return false;       // tried to flow outside the maze

  if(maze[r][c] == 3){  // is it a destination point?
    print(maze);        // solved
    return true;
  }

  if( maze[r][c] != 0)  // a wall, a path or already checked?
    return false;

  maze[r][c] = 2;       // mark position as a part of the path

  if( mazeSolver(r, c + 1, maze)))  // try to extend the path and
    return true;                    // return if solution found
  if( mazeSolver(r, c - 1, maze)))
    return true;
  if( mazeSolver(r + 1, c, maze)))
    return true;
  if( mazeSolver(r - 1, c, maze)))
    return true;

  maze[r][c] = 4;     // dead-end - mark the position 'checked'
  return false;
}


public static boolean isPositionValid(int r, int c, int[][]maze){
  return r >= 0 && c >= 0 && r < maze.size && c < maze[r].size;
}
person CiaPan    schedule 30.03.2014