Backtracking

Backtracking is a great tool to have especially if you are working on a game that requires re-tracing steps and trying something different. I wanted to refresh myself on some of working mechanics of this algorithm so I did a bit of digging and noticed there is tons more information on the recursive version and not much on the iterative version.

The iterative version definitely frowned upon during in a homework or during an interview however I believe it more clearly lays out the mechanisms at play to solve a problem.

Problem Statement

Write a program that can find a path from an arbitrary entry point in a maze to an exit.

+--+--+--+
|0  1  2 |
+  +--+--+
|3  4  5 |
+--+   +--+
|6  7  8 |
+--+--+--+

We will make a class that will initialize necessary variables and then use a method called solve_maze to begin solving the maze.

Initialize

We initialize the class with the following variables that will enable us to keep track of the activities that the class will perform. This is an important concept here. It is important to keep close track of what is going us as the program runs.

Here is what our initialize looks like

  def initialize
    @path = []
    @visited = []
    @current = nil
     ...
  end

@path an array that will keep track of our our live solution. We will be editing this path as the application tries various solutions and keeps only the ones that worked well.

@visited is an array that holds ALL the solutions the algorithm has tried. It will be used as a reference to ensure that the algorithm does not repeat a solution.

@current is simply a pointer to where the algorithm is within the maze at any given time.

Build the Maze

For this entire thing to work we will need to build a maze. The code for that appears here:

 def build_maze
    @maze = {}
    @maze[0] = [1, 2]
    @maze[1] = [0, 3]
    @maze[2] = [0]
    @maze[3] = [1, 4]
    @maze[4] = [3 ,5, 7]
    @maze[5] = [4]
    @maze[6] = [7]
    @maze[7] = [ 6, 8]
    @maze[8] = [ 7 ]
  end

As shown above we will be representing the maze as a hash. The key will be a point in the maze and the value holds all the points that the point in the key touches.

Solving the maze ( iterative solution )

while (@current != finish)
      maze[@current].each do |node|
        if @visited.include?(node)
          if node == maze[@current].last
            @path.pop
            @current = @path.last
            break
          end
          next
        else
          @path << node
          @visited << node
          @current = node
          break
        end
      end
   end

Before we start this loop we need to set a few more variables. finish is the point we will set as the maze exit. The most tricky part of getting the algorithm correct for me was the order in which the arrays were appended to the @path and @visited arrays. Once I had the concept figured out the remaining the work flowed.

START

You can set a start point. In my code I simply set @current we could have a less hard-coded solution for sure but I was more focused on getting the code working. The arrays at this point are all empty . We jump to a point in the maze and grab all the connected points and begin traversing. Here what is important is we start tracking our steps buy updating the various variables we setup.

FOUND

Given we land on a node we have already seen before we simply skip to the next node in the current path that we are on.

BLOCKED

Given we find that the current path has already by discovered and we have reached the very end of the path. Then we have the do the the most intesting part of the algorithm: We have have to remove that node from out @path variable as it no longer qualifies as a solution to our problem. Here we need to set @current again and we abandon the current path. Given we are not finished yet the out loop will be take control and move to the next node and another path will be explored.

Finished

As we exhaust the various nodes we will eventually reach the point where @current will be equal to finish and here the loop terminates and we have solve the entire maze.