Solving maze with Backtracking

Question

I am trying to solve a maze with scala using backtracking.

My problem is that I keep on getting StackOverflow errors.

I have tried qite alot of things but I always end up with a StackOverflow.

findStart() and the getWay() show two approaches I have used.

I know that it is possible to do this with Streams and calculate all possible ways in one recursion but I would like to solve it with backtracking first.

Here is my Code:

object MazeSolver {

  case class Cell(free: Boolean, start: Boolean)

  type Maze = Seq[Seq[Cell]]

  def main(args: Array[String]) = {

    val lab = lislab("laby1.rinth")

    val entrance = findStart(lab, Position(0, 0))


   println(getWay(lab, entrance(0), entrance(0), Nil))

  }

  def findStart(lab: Maze, pos: Position): List[Position] = {
    try {
      if (lab(pos.column)(pos.row).start)
        List(pos)
      else
        findStart(lab, pos.south) ::: findStart(lab, pos.north) ::: findStart(lab, pos.west) ::: findStart(lab, pos.east)
    } catch {
      case _: java.lang.IndexOutOfBoundsException => Nil
    }

  }

  def getWay(maze: Maze, pos: Position, lastPos: Position, way: List[Position]): List[Position] = {
    try {
      if (!maze(pos.column)(pos.row).free && !maze(pos.column)(pos.row).start) {
        Nil

      } else {

        if (isExit(pos, maze)) {
          pos :: way
        } else {

          val posList = List(pos.north, pos.south, pos.west, pos.east)

          posList.foreach { x => 
            val tail = getWay(maze, x, pos, way) 
            if(tail != Nil) tail :: way
            }


          Nil

        }
      }
    } catch { case _: java.lang.IndexOutOfBoundsException => way }

  }

  def lislab(fn: String): Maze = {
    try {
      (for (column <- io.Source.fromFile(fn, "UTF-8").getLines.toList)
        yield for (c <- column) yield Cell(c == ' ', c == '?')).toIndexedSeq
    } catch { case _: java.io.FileNotFoundException => Nil }
  }

  case class Position(column: Int, row: Int) {
    override def toString = "(" + column + "." + row + ")"
    def north = Position(column - 1, row)
    def south = Position(column + 1, row)
    def west = Position(column, row - 1)
    def east = Position(column, row + 1)
  }

  def isExit(pos: Position, lab: Maze): Boolean = {
    val cell = lab(pos.column)(pos.row)
    cell.free && (pos.column == 0
      || pos.column == lab.length - 1
      || pos.row == 0
      || pos.row == lab(0).length - 1)

  }
}

What am I doing wrong? How can I make the findStart() and getWay() functions work properly?

Answer 1

I'm only going to comment on findStart for now.

There are two things wrong with findStart:

1. findStart is recursively called on every adjacent cell. Unfortunately, the neighbouring cell of any neighbour is the cell itself.
2. The function never checks if you can actually walk on a given cell (I assume Cell.free means you can walk on the cell).

Let's look at an example to see why the first point leads to a StackOverflow. Assume a maze consisting of only one row of three columns:

[A] <-> [B] <-> [C (start)]

Now your algorithm starts at A. Since A.start == false, it calls findStart(A.east) which is findStart(B). Now since B.start == false it calls findStart(B.west) and findStart(B.east). The first one is the same as findStart(A), leading to infinite recursion.

To fix this, you need to keep track on which cells you have already visited. One way to achieve this is by passing a list of already visited positions.

Regarding point 2, you simply need to check whether a certain position is walkable, by checking maze(position.column)(position.row).free.

A (not tested) implementation could look as follows:

def findStart2(maze: Maze, position: Position, visited: List[Position]): List[Position] =
  if (maze(position.column)(position.row).start)
    List(position) // we reached our goal
  else {
    val explorationArea: List[Position] = List(position.north, position.east, position.south, position.west) filter (x => !visited.contains(x) && canWalkOnCell(maze, x))
    // filter the adjacent positions that have already been visited or are not walkable
    explorationArea flatMap { 
      notYetVisitedPosition =>
        findStart2(maze, notYetVisitedPosition, position :: visited) // don't forget to add the current position to the list of already visited positions
    }
  }

private def canWalkOnCell(maze: Maze, position: Position): Boolean =
  indexInBound(maze, position) && maze(position.column)(position.row).free

private def indexInBound(maze: Maze, position: Position): Boolean =
  position.column >= 0 && position.row >= 0 && position.column < maze.size && position.row < maze(position.column).size