使用左手规则解决迷宫

Question

我正在尝试使用左手出口规则使用以下SUDO代码来解决迷宫一个正方形的情况，其顶部是真实的，但在第一阶段左，底部和右墙是错误的，我的代码从输入到底部或右2中的两个中都正确移动，但是当它返回时，它会选择左方向而不是底部，如何使其选择底部）。

有人可以建议我如何选择新的方向吗？

Set int entr to LEFT;
Set int exit to-1;
Set boolean backtrack to false;
Set currentSquare to startingSquare;
Set previousSquare to null;
Set currentSquare.onpath to true;
While (currentSquare != endingSquare) {
    **Set exit to currentSquare.getLeftHandExit(entr);**
    Set previousSquare to currentSquare;
    Set currentSquare to currentSquare.adjacentSquare(exit);
    If (backtracking is false and exit is same as entrance)
        Set backtracking to true;
        Remove previousSquare from path;
    }
    Else if backtracking is true and currentSquare is not on the path
        Set backtracking to false;
        Add previousSquare to path;
    }
    If backtracking is true, remove currentSquare from path;
    else add currentSquare to path;
    entr = currentSquare.oppositeSide(exit);
} // end of While

Answer 1

如果您始终向左转动，则只需转身，就应该改变方向，因此左侧会更改为右侧的方向。

当您到达下一个走廊时，您仍然会向左转。

我认为这只是将左手放在墙上，您最终会找到出路。

根据您的迷宫的复杂程度，可以设计一个迷宫，最终会循环循环，因此您可能想更改所处位置的颜色我再次重复您的道路。

Answer 2

使用回溯系统；无论是使用递归方法（不优选）还是堆栈来回去步骤。理想情况下，您还会在算法选择方法的每个连接点中设置标记，因此您不会再次选择相同的路径（仅在给定的连接处选择未标记的路径）

维基百科有一些 不错的伪代码 关于如何实现这一目标。请注意“递归背带”算法，通过“从一个未访问的邻居中选择左转转弯”（意味着从左键选择时钟，从左键选择左转），将“随机选择一个无访问的邻居之一”替换为“选择左转”。

另外，查看 这本电子书 关于递归。

我会选择（未经测试的代码）之类的东西：

maze.clearAllVisited();
Stack<Point> paths = new Stack<Point>();
int x = maze.getStartX();
int y = maze.getStartY();
while (!maze.isExit(x, y)) {
   maze.setVisited(x, y);
   if (maze.canGoWest(x, y)) {    // check if west cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      x--;
   } else if (maze.canGoNorth(x, y)) { // check if north cell is accessible from x,y and has not been visited
      paths.push(new Point(x, y));
      y--;
   } else if (maze.canGoEast(x, y)) {  // ...
      paths.push(new Point(x, y));
      x++;
   } else if (maze.canGoSouth(x, y)) { // ...
      paths.push(new Point(x, y));
      y++;
   } else {
      if (paths.isEmpty()) {
         break;  // no more path for backtracking, exit (aka no solution for maze)
      }
      // dead end! go back!
      Point last = stack.pop();
      x = last.x;
      y = last.y;
   }   
}